При условиях
;



.
Здесь , а переменные. Задача ЛП каноническая. Нетрудно убедиться, что r(A) = r(R), т.е. система ограничений совместна. Кроме того, r(A) = 4, n = 6. Составим исходную симплексную таблицу.
Исходная симплексная таблица
Базисные переменные
| Свободные члены
| Коэффициенты при неизвестных
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| F
|
|
|
|
|
|
|
|
|
Пустые клетки соответствуют нулям. Столбец контрольной суммы ( ) включает в себя алгебраические суммы коэффициентов каждой строки и служит для контроля арифметических действий при последующем преобразовании данной таблицы. Последняя строка таблицы называется индексной. При ее заполнении свободный член целевой функции выписывается со своим знаком, а коэффициенты при неизвестных (оценки) – с противоположным. Выберем так называемый разрешающий столбец с положительной оценкой. Но таких столбцов два. Выбираем столбец с оценкой 5. Далее выбирается так называемая разрешающая строка. Из отношений свободных членов к положительным коэффициентам разрешающего столбца ( ) выбираем наименьшее т.е. . Это отношение и соответствует разрешающей строке. Коэффициент 3, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. Выведем из базиса, а (провокатор) введем в базис. В результате получим новые наборы базисных и свободных переменных. Необходимо выразить базисные переменные и целевую функцию через свободные переменные. Для этого разрешающую строку в исходной симплексной таблице делим на разрешающий элемент. Результат заноситься в новую симплексную таблицу “Итерация 1”.
Итерация 1
Базисные переменные
| Свободные члены
| Коэффициенты при неизвестных
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -1
|
|
|
|
|
|
|
|
| -1/3
|
| 32/3
|
|
|
|
|
|
| 1/3
|
| 19/3
|
|
|
|
|
|
|
|
|
| F
| -25
|
|
|
|
| -5/3
|
| -59/3
|
Коэффициенты данной симплексной таблицы вычисляются таким образом, чтобы в разрешающем столбце исходной таблицы все элементы, кроме разрешающего, стали нулевыми. Например, для того что бы в исходной таблице в уравнении 2 +3 + =19 получить коэффициент при нуль, надо третью строку в таблице «Итерация 1» умножить на (-3) и сложить с первой строкой исходной таблицы. Результат записывается в первую строку таблицы «Итерация 1». Получим 2 + - =4, откуда базисное переменное легко можно выразить через свободные переменные. Аналогично вычисляется в этой строке и контрольная сумма: ( . Алгебраическим сложением коэффициентов строки убеждаемся, что арифметической ошибки нет. В полученной таблице «Итерация 1» выбирается положительная оценка. В частности, столбец, соответствующий оценке 7, будет разрешающим. Затем выбирается разрешающая строка и т.д. Столбец контрольной суммы для простоты можно опустить. Продолжим решение. В итоге получим следующие симплексные таблицы:
Итерация 2
Базисные переменные
| Свободные члены
| Коэффициенты при неизвестных
|
|
|
|
|
|
|
|
|
|
| 1/2
|
| -1/2
|
|
|
|
|
| -1
|
| 2/3
|
|
|
|
|
|
|
| 1/3
|
|
|
|
|
| -3/2
|
| 3/2
|
| F
| -39
|
|
| -7/2
|
| 11/6
|
|
Итерация 3
Базисные переменные
| Свободные члены
| Коэффициенты при неизвестных
|
|
|
|
|
|
|
|
|
|
| -1/4
| 3/4
|
|
|
|
|
|
| -3/2
| 3/2
|
|
|
|
|
|
| 1/2
| -1/2
|
|
|
|
|
|
| 3/4
| -9/4
|
|
| F
| -50
|
|
| -3/4
| -11/4
|
|
|
Выписав из последней симплексной таблицы выражение для целевой функции убедимся, что базисное решение является оптимальным (все оценки в индексной строке отрицательны), а .
Решая задачу максимизации при тех же условиях, что и раньше, получим . Оптимальное решение этой задачи оптимизации совпадает с оптимальным решением задачи минимизации . 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | Поиск по сайту:
|