Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович




Скачать 446.07 Kb.
НазваниеЭкономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович
страница3/6
Дата публикации05.08.2013
Размер446.07 Kb.
ТипМетодические указания
lit-yaz.ru > Математика > Методические указания
1   2   3   4   5   6
^

3. Нахождение решения задачи линейного программирования


Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду.

Для применения симплекс-метода с естественным базисом ЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план.

Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные записать в таблицу:
БазисСбР0с1с2...сmcm+1...cnР1Р2...РmРm+1...РnР1с1b110...0a1m+1...a1nР2с2b201...0a2m+1...a2n........................Рmсmbm00...1amm+1...amnF0000Δm+1Δn

В первом столбце таблицы "Базис" записывают базисные векторы данного опорного плана. Во втором столбце - коэффициенты целевой функции (с1, с2,…, сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу). В третьем столбце Р0 - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы второго столбца таблицы со столбцом Р0, и суммируя эти произведения, мы получаем значение целевой функции (F01*b1 + с2*b2+…+ сm*bm).

Первая строка симплексной таблицы содержит коэффициенты целевой функции нашей задачи и остается неизменной на протяжении всего решения (с1, с2,…, сm).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи. При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу. Последнюю оценочную строку рассчитывают по формуле .

После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы последней (оценочной) строки. Возможны три варианта:

  1. Все оценки , значит на основании признака оптимальности получен оптимальный план.

  2. для некоторого j, и все соответствующие этому индексу величины , значит целевая функция не ограничена сверху на множестве планов.

  3. для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел , значит можно перейти к новому опорному плану, при котором значение целевой функции увеличится.

Переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вводимого в базис вектора берётся один из векторов, для которых . Пусть это будет вектор Рk.

Для определения вектора, подлежащего исключению из базиса находят . Тогда выполняется условие неотрицательности значений опорного плана. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор Рr, а число называют разрешающим элементом.

Элементы новой симплекс-таблицы получают методом Жордана-Гаусса по формулам:

для i = r;

.

Значения нового опорного плана рассчитываются по формулам:

для i = r;

.

Процесс решения продолжают либо до получения оптимального плана, либо до установления неограниченности целевой функции. Если среди оценок оптимального плана нулевые только оценки, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.

Если единичной подматрицы не обнаруживается, то либо придется перебирать все подсистемы m уравнений с m неизвестными в надежде обнаружить неотрицательные решения, либо прибегнуть к методу искусственного базиса.

Метод искусственного базиса заключается в том, что для получения единичной подматрицы коэффициентов мы вводим в исходную задачу неотрицательные так называемые искусственные переменные и включаем их в целевую функцию с коэффициентом +М для задачи минимизации и с коэффициентом -М для задачи максимизации, где М>0 - сколь угодно большое число. Полученная задача называется расширенной по отношению к исходной. Искусственные переменные образуют начальное базисное решение. Применив симплекс-метод, необходимо вывести из базиса все искусственные переменные. Если удается доказать (или показать), что искусственные переменные полностью вывести из базиса невозможно, то это означает, что задача не имеет решения, то есть ее ограничения противоречивы.

Если на текущей итерации из базиса выводится искусственная переменная, то в следующей симплекс-таблице соответствующий ей столбец можно удалить, в дальнейших итерациях он не будет участвовать.


1   2   3   4   5   6

Похожие:

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconОтчет по лабораторной работе №1 по предмету «Экономико-математические...
Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению 6

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания по дисциплине «Экономика организации»
Методические указания составлены в соответствии с примерной программой по дисциплине

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по выполнению курсового проекта с использованием...
Изложены общие указания по курсовому проектированию, приведены задания на проекты, даны методические указания по отдельным этапам...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к контрольной работе по дисциплине «Экономический...
Методические указания предназначены для обучающихся по специальности 051800 «Учет и аудит (по отраслям)»

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания для студентов заочной...
Методические указания составлены в соответствии с Учебно-методическим комплексом дисциплины на основе требований Государственного...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по контрольно-курсовой работе по дисциплине эксплуатацияэвми систем
Методические указания по ккр составлены доц каф ЭВМ лебеденко Ю. И. и обсуждены на заседании кафедры ЭВМ факультета кибернетики

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к лабораторным работам по курсу «Информатика»
Методические указания предназначены для выполнения лабораторных работ по написанию программ на языке C. Работы проводятся с использованием...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и задания к выполнению курсовой работы по курсу «базы данных»
Методические указания и задания к выполнению курсовой работы по курсу «Базы данных» (направление подготовки 050103 ”Программная инженерия”)....



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница