Лекции.Орг


Поиск:




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




 

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

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

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

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

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

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

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

 

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

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

 

  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    
      =  
         

 

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

.

 





Поделиться с друзьями:


Дата добавления: 2016-10-27; Мы поможем в написании ваших работ!; просмотров: 1254 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Так просто быть добрым - нужно только представить себя на месте другого человека прежде, чем начать его судить. © Марлен Дитрих
==> читать все изречения...

1000 - | 811 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.