Пример проверки вектора на оптимальность

Исследовать вектор на оптимальность в задаче ЛП.

Вначале нужно проверить, является ли вектор допустимым. Для этого подставляем координаты вектора в ограничения:

Так как второе ограничение выполняется как строгое неравенство, то в силу УДН для оптимальности вектора необходимо выполнение равенства .

Построим двойственную задачу:

Поскольку , то из третьего и четвертого ограничений получаем . Но по УДН из условия следует, что должно выполняться равенство в первом ограничении двойственной задачи:

Подставляя значения получим Следовательно, УДН не выполняются и вектор не является оптимальным в исходной задаче.

Пример решения задачи ЦЛП

Решить задачу ЦЛП.

Решаем задачу ЛП симплекс-методом. Оптимальная таблица имеет вид

  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
=  
   

Стоимость перевозок по плану этой таблицы Так как в последней таблице все псевдостоимости не превосходят соответствующих стоимостей, то полученный опорный план является оптимальным. Стоимость перевозок при этом

.

Наши рекомендации