й этап: Проверка оптимальности и улучшение исходного решения




Критерий оптимальности решения:

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

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

Для этого:

а) основные переменные выражаем через неосновные;

б) положив неосновные переменные равными нулю, находим базисное решение и проверяем его на допустимость (все основные переменные должны быть неотрицательными);

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

Для сохранения неотрицательности всех переменных задачи должно выполняться ограничение на максимум переменной, переводимой в состав основных:

. (4)

Уравнение, где выполняется условие (4), называется разрешающим и определяет основную переменную, которую надо перевести в неосновные.

г) Определяем новый состав основных и неосновных переменных.

Затем повторяются пункты а, б, в и г 2-го этапа при новых основных переменных до тех пор, пока не выполнится условие оптимальности решения.

Пример 2. Использование симплекс-метода рассмотрим на примере решения задачи об оптимальном плане мебельного цеха.

Решение

Приведем ЗЛП к каноническому виду: обратим систему ограничений – неравенств в систему равенств, вводя в каждое неравенство соответствующую неотрицательную переменную:

Все дополнительные переменные введены со знаком «+», т.к. рассматриваемые неравенства имеют знак «≤».

1-й этап. В соответствии с вышеизложенным правилом нахождения исходного допустимого базисного решения разобьем переменные на две группы - основные и неосновные:

основные переменные – х3, х4, х5;

неосновные переменные – х1, х2.

2-й этап. Последовательно повторяем пункты а, б, в и г 2-го этапа, пока не получим оптимальное решение.

Шаг 1

а) Выражаем основные переменные через неосновные:

 

б) Положив неосновные переменные равными нулю, получим первое базисное решение:

Х1=(0;0;8;20;5),

которое оказалось допустимым, т.к. все его координаты положительны.

в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:

F1 = x1 + 2x2.

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

Чтобы новое базисное решение, с одной стороны, по крайней мере, не ухудшало значение целевой функции, а с другой – было бы допустимым, необходимо определить:

· максимум переменной х2, вошедшей в новый состав основных переменных;

· какая переменная из «бывших» основных должна перейти в состав неосновных переменных при переходе от старого базисного решения к новому.

Для определения максимум переменной х2, при котором каждая из «старых» основных переменных остается неотрицательной, должны выполняться неравенства:

Каждое из неравенств этой системы определяет возможные границы изменения переменной х2. В частности, из последнего неравенства системы следует, что переводимая переменная может возрастать неограниченно. Очевидно, допустимость нового базисного решения будет обеспечена, если будут выполнены все ограничения системы:

х2 = min{8;5;∞} = 5.

При х2 = 5 переменная х4 обращается в нуль и переходит в состав неосновных. Второе уравнение, где достигается наибольшее возможное значение переменной х2, называется разрешающим.

г) Определяем новый состав основных и неосновных переменных:

основные переменные – х2, х3, х5;

неосновные переменные – х1, х4.

Далее переходим к шагу 2.

Шаг 2

а) Выражаем основные переменные через неосновные, воспользовавшись соотношением из разрешеющего уравнения:

б) Положив неосновные переменные равными нулю, получим второе базисное решение:

Х2=(0;5;3;0;5).

Х2 допустимо, т.к. все его координаты положительны.

в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:

F2 = 10 + 1/2x1 -1/2x4.

Критерий оптимальности не выполняется, переходим к следующему базисному решению, переведя переменную х1 в состав основных. Для этого определим допустимое значение x1 и разрешающее уравнение:

х1 = min{20;4;5} =4.

При х1 = 4 переменная х3 обращается в нуль и переходит в состав неосновных. Второе уравнение, где достигается наибольшее возможное значение переменной х1, будет разрешающим.

г) Определяем новый состав основных и неосновных переменных:

основные переменные – х1, х2, х5;

неосновные переменные – х3, х4.

Далее переходим к шагу 3.

Шаг 3

а) Выражаем основные переменные через неосновные, воспользовавшись соотношением из разрешеющего уравнения:

б) Положив неосновные переменные равными нулю, получим третье базисное решение:

Х3=(4;4;0;0;1).

Х3 допустимо, т.к. все его координаты положительны.

в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:

F3 = 12 – 2/3x3 -1/3x4.

Критерий оптимальности выполняется, найденное решение Х3=(4;4;0;0;1) оптимально, при этом целевая функция F3 = 12.

Заметим, что значение дополнительной переменной х5=1 в оптимальном решении означает: при оптимальном плане третий ресурс Р3 расходуется неполностью, его остаток равен х5=1.

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

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

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

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-10-25 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: