Решения задачи планирования производства симплекс методом

В нашем случае:

Таблица 2. Исходная симплекс таблица поставленной задачи

Составленная симплекс-таблица соответствует начальному базису и начальной опорной точке ОДР. Переход к очередной опорной точке в процессе поиска оптимального решения сопровождается составлением новой симплекс-таблицы.

Каждая симплекс-таблица анализируется по критериям допустимости и оптимальности базиса.

3.3.4 Проверка признака допустимости и оптимальности базиса

Признак допустимости базиса:

в опорной точке в соответствии с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому признак допустимости базиса формулируется как условие bi0, i=6,…,10.

Признак оптимальности базиса:

Если для то найденное решение оптимально и единственно.

Если для то найденное решение оптимально, но не единственно.

Если то решение неоптимально. В этом случае поиск оптимального решения продолжается и необходимо перейти к новой опорной точке.

Перейдем к конкретному случаю. В нашем случае выполняется условие допустимости базиса, так как b=(600, 590, 750, 670, 495)T<0 и bi<0 (i=6,…,10).

Выбранный нами начальный базис XБО=(x6, x7, x8, x9, x10)T не является оптимальным, так как c1=-60<0, c2=-50<0, c3=-37<0, c4=-45<0 и c6=56<0. Таким образом, необходимо осуществить переход к новой опорной точке (новому базису).

3.3.5 Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса

В соответствии с симплекс-методом новая опорная точка выбирается только среди соседних, то есть новый базис лишь одной переменной отличается от прежнего. Таким образом, формирование нового базиса осуществляется на базе прежнего посредством выведения из него одной из базисных переменных xs и введения одной из свободных переменных xr.

Выбор переменной xr. Выбор переменной xr осуществляется по результатам анализа коэффициентов cj симплекс-таблицы. Найдем cr=.

В нашем случае min{c1, c2, c3, c4, c5}=c1=-60 и xr=x1.

Столбец, который соответствует переменной xr=x1 в симплекс-таблице, будем называть разрешающим.

Выбор переменной xs. Выбор переменной xs проводится по результатам анализа коэффициентов air i=1,2,3,4,5 разрешающего столбца.

Если , это означает, что ОДР такова, что неограниченное увеличение свободной переменной xr приводит к неограниченному возрастанию целевой функции (ОДР не замкнута).

Если , то соответствующие базисные переменные xi (i=6,7,8,9,10) получают отрицательные приращения при увеличении xr=x1. Среди этих переменных xi необходимо отыскать xs, достигающую нуля при минимальном значении приращения xr. Нужно найти

.

В нашем случае min{600/1, 590/2, 750/4, 670/3, 495/1}=min{600,295,187.5,223.3,495}=187.5 и xs=x8. Строка, которая соответствует переменной xs=x8 в симплекс-таблице, называется разрешающей. Элемент asr=a81=4 называется разрешающим элементом симплекс-таблицы.

Выбор разрешающего элемента завершает формирование нового базиса XБ1, отличающегося от прежнего базиса одной переменной xr=x1, то есть вместо переменной x8 в базис XБ1 будет включена переменная x1: XБ1=(x6, x7, x1, x9, x10)T.

Для нового базиса (новой опорной точки) снова заполняется симплекс-таблица, в которой новые базисные переменные выражены через новые свободные.

3.3.6 Пересчет симплекс-таблицы

Правила пересчета:

Разрешающий элемент заменяется на 1.

Элементы разрешающего столбца за исключением asr переписываются без изменений.

Элементы разрешающей строки за исключением asr изменяют знак на противоположный.

Оставшиеся элементы новой симплекс-таблицы вычисляются согласно следующему правилу: произведение соответствующего элемента прежней таблицы на разрешающий элемент asr минус произведение элементов, находящихся на другой диагонали таблицы. В соответствии с этим правилом имеем:

 Скачать реферат