13. Переход к новому, нехудшему опорному плану (третий пункт алгоритма)
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: для того чтобы затраты были минимальными необходимо, чтобы оборудование А1 выпускало 3 ч продукцию Р1, оборудование А2 выпускало 4 ч продукцию Р1 и 6 ч продукцию Р2. При этом продукция будет выпущена с минимальными затратами, равными 52 усл. ден. ед. и в заданный срок.
| < Предыдущая | Следующая > |
|---|
