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