Исследование на оптимальность опорного плана при минимизации целевой функции (второй пункт алгоритма)

Заполним Жорданову таблицу, исходя из задачи, записанной в виде:

;

где – предпочтительные переменные.

Или воспользуемся конечной таблицей при нахождении начального опорного плана методом Жордановых исключений (таблица 5).

1. Если в Z-строке нет положительных элементов (не считая свободного члена) – план оптимален. Если в Z-строке нет также и нулевых элементов, то оптимальное решение единственное, если же есть хотя бы один нулевой элемент, то оптимальных планов бесконечное множество.

2. Если в Z-строке есть хотя бы один положительный элемент, а в соответствующем ему столбце нет положительных элементов, то целевая функция является неограниченной в ОДР (вследствие неограниченности ОДР). В этом случае задача не разрешима. (Проверить правильность составления экономико-математической модели).

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

Переход к новому, нехудшему опорному плану (третий пункт алгоритма)

1 В таблице 5 выбираем разрешающий элемент, руководствуясь следующими правилами:

а) выбрать в Z-строке симплекс-таблицы наибольший положительный элемент. Пусть это будет , тогда столбец будет разрешающим;

б) найти отношения для положительных элементов ( ) столбца ;

в) выбрать среди этих отношений наименьшее, скажем , тогда элемент разрешающий (генеральный).

2 Перейти от данной таблицы к следующей таблице по правилам работы с симплекс-таблицей (см. шаг Жордановых исключений).

Замечание: При решении задачи ЛП на максимум целевой функции ее можно преобразовать в эквивалентную ей задачу на минимум и решать вышеизложенным методом.

Пример 7

Воспользуемся результатами, полученными в предыдущем примере (см. таблицу 11). Так как в Z – строке есть положительный элемент, то найденный опорный план не оптимален. Поскольку максимальный положительный элемент Z-строки находится в столбце , то этот столбец будет разрешающим. Составим отношения свободных членов к соответствующим положительным элементам этого столбца (см. таблицу 12). По наименьшему отношению выберем разрешающую строку. Так как , то -строка будет разрешающей. На пересечении разрешающего столбца и разрешающей строки найдем разрешающий элемент 1 (таблица 12).

Таблица 12

		СП
БП	1	x12	x21	отношения
x11=	6,2	0	0,8	6,2/0,8
x22=	6	0,5	0
x3=	3,8	1	–0,8
x4=	4	–0,5	1	4/1
Z	61,6	–6	2,4

Шаг Жордановых исключений переводит из таблицы 12 в таблицу 13.

Таблица 13

		СП
БП	1	x12	x4
x11=	3	0,4	–0,8
x22=	6	0,5	0
x3=	7	0,6	0,8
x21=	4	–0,5	1
Z	52	–4,8	–2,4

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

СП:

БП: ,

следовательно, и .

Так как в Z-строке нет нулевых элементов, то полученный оптимальный план единственен.

Экономический смысл полученного решения задачи примера 2: для того чтобы затраты были минимальными необходимо, чтобы оборудование А₁ выпускало 3 ч продукцию Р₁, оборудование А₂ выпускало 4 ч продукцию Р₁ и 6 ч продукцию Р₂. При этом продукция будет выпущена с минимальными затратами, равными 52 усл. ден. ед. и в заданный срок.