Пример проверки вектора на оптимальность
Исследовать вектор на оптимальность в задаче ЛП.
Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:
Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора необходимо выполнение равенства .
Построим двойственную задачу:
Поскольку , то из третьего и четвертого ограничений получаем . Но по УДН из условия следует, что должно выполняться равенство в первом ограничении двойственной задачи:
Подставляя значения получим Следовательно, УДН не выполняются и вектор не является оптимальным в исходной задаче.
Пример решения задачи ЦЛП
Решить задачу ЦЛП.
Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид
| b | |||
| L | -14/3 | -4/3 | -2/3 |
| 5/3 | 1/3 | 2/3 | |
| 4/3 | 2/3 | -2/3 |
Оптимальное решение не является целочисленным. Выберем среди нецелочисленных переменных переменную с максимальной дробной частью и построим соответствующее отсечение:
Приписывая это ограничение к симплексной таблице и проводя стандартное преобразование двойственным симплекс-методом, получим:
| b | |||
| L | -14/3 | -4/3 | -2/3 |
| 5/3 | 1/3 | 2/3 | |
| 4/3 | 2/3 | -2/3 | |
| -2/3 | -1/3 | -2/3 |
| b | |||
| L | -4 | -1 | -1 |
| -1 | |||
| 1/2 | -3/2 |
Полученная таблица является оптимальной. Соответствующее оптимальное решение является целочисленным. Значение функции на этом решении .
Пример построения опорного плана методом
Северо-западного угла
| = | ||||||||||||
В таблице, обведенной снизу и справа двойной чертой, указаны объемы перевозок, полученные методом северо-западного угла. При этом небазисные нулевые перевозки не проставлены. Справа и внизу таблицы содержатся объемы возможных запасов и спросов. В число базисных перевозок вошла перевозка , так как на предыдущем шаге и по п.3 метода считается выбывшим только поставщик, а неудовлетворенный спрос второго потребителя равен .
Пример построения опорного плана методом
Минимальной стоимости
| 9 | 57 | 301 | |||||||||||
| 152 | 153 | 8 | |||||||||||
| = | |||||||||||||
Пример решения транспортной задачи методом
Потенциалов
| 3 | 8 | 2 | ||
| 7 | 4 | 8 | ||
| = |
Опорный план этой задачи найден методом северо-западного угла.
Приписываем к таблице строку для платежей и столбец для платежей . Псевдостоимости записываем в левом углу клетки, а стоимости – в правом.
Из условий в базисных клетках получаем систему уравнений:
Полагая , находим последовательно платежи и псевдостоимости для свободных клеток. Получаем таб-лицу
| [-] 20 | 12 2 [+] | ||||
| -1 7 | [+] 0 | [-] 30 | -4 | ||
| = | |||||
Стоимость перевозок по плану этой таблицы
.
Так как клетка (1,3) имеет отрицательную цену , то план не является оптимальным. Строим для клетки (1,3) цикл. Цена цикла . По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1,2) не стали отрицательными). При этом стоимость плана изменяется на . Для нового плана вычисляем новые значения платежей и псевдостоимостей:
| [-] 15 | -2 8 | [+] 20 | |||
| 9 7 [+] | [-] 10 | ||||
| = | |||||
| -2 |
Стоимость перевозок по плану этой таблицы
.
Полученная таблица имеет клетку (2,1) с отрицательной ценой . По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается на единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:
| 0 8 | |||||
| 5 8 | |||||
| = | |||||
Стоимость перевозок по плану этой таблицы Так как в последней таблице все псевдостоимости не превосходят соответствующих стоимостей, то полученный опорный план является оптимальным. Стоимость перевозок при этом
.