Пример проверки вектора на оптимальность
Исследовать вектор на оптимальность в задаче ЛП.
Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:
Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора необходимо выполнение равенства
.
Построим двойственную задачу:
Поскольку , то из третьего и четвертого ограничений получаем
. Но по УДН из условия
следует, что должно выполняться равенство в первом ограничении двойственной задачи:
Подставляя значения получим
Следовательно, УДН не выполняются и вектор
не является оптимальным в исходной задаче.
Пример решения задачи ЦЛП
Решить задачу ЦЛП.
Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид
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 | |||||
![]() | = | ||||
![]() |
Стоимость перевозок по плану этой таблицы Так как в последней таблице все псевдостоимости не превосходят соответствующих стоимостей, то полученный опорный план
является оптимальным. Стоимость перевозок при этом
.