Оптимальное решение исходной задачи получаем отбрасыванием из компонент, связанных с балансовыми переменными ,,, т. е. , при этом значение не изменится.

Двойственность в линейном программировании

Каждой задаче линейного программирования можно поставить в соответствие другую задачу линейного программирования, так называемую двойственную задачу.

Рассмотрим задачу об оптимальном выпуске продукции (12)-(13):

  (12) 

 

  (13) 

Каждому ограничению ставится в соответствие переменная двойственной задачи . Двойственная задача имеет вид: 

  (18)

 

  (19)

Для составления  модели двойственной задачи необходимо учесть следующие свойства:

1.Число ограничений  исходной задачи равно числу неизвестных двойственной.

2. Матрица коэффициентов при неизвестных одной задачи транспонируется для неизвестных  другой задачи.

3. Знаки в неравенствах исходной задачи и двойственной имеют противоположный смысл, в исходной знак “”, в двойственной знак  “”.

4. Свободные члены ограничений исходной задачи  становятся коэффициентами  целевой функции двойственной задачи,  коэффициенты целевой функции исходной задачи  ─ свободными членами неравенств двойственной задачи.

5. В исходной задаче  целевая функция ,  в двойственной задаче  .

Задачи (12)–(13) и (18)–(19) называются симметричными взаимно двойственными задачами. Модель двойственной задачи к исходной (14)–(15) имеет вид:

НЕ нашли? Не то? Что вы ищете?

 

 

 

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

, ,.

.

Задание 7.  Транспортная задача

В пунктах производства ,,имеется однородный груз в количестве соответственно , ,,. Данный груз необходимо доставить в 3 пункта назначения ,, в количестве соответственно ,,. Стоимость перевозки единицы груза (тариф) из пункта в пункт равна . Требуется составить план перевозок, при котором все грузы будут вывезены с минимальными затратами.

Таблица 8 – Данные задания 7 «Транспортная задача»

№

15

3

5

4

2

8

7

6

3

4

5

3

7


Таблица 9 – Данные задания 7 «Транспортная задача»

№

15

28

25

10

15

34

25

25

Пример 7. Решить транспортную задачу, используя следующие данные:

 

Решение:  Транспортная задача называется закрытой если .

Проверим модель на сбалансированность:

Так как , условие баланса не выполняется,  данная модель является открытой. Приведём задачу к закрытому виду; введём фиктивного потребителя , потребность которого равна ед. груза. Стоимости перевозки единицы груза (тарифы) для фиктивного потребителя (поставщика) принимаются равными 0. 

Составим исходный план перевозок методом «наименьшего элемента» (минимальной стоимости). Поставки в клетки с нулевыми тарифами осуществляются в последнюю очередь. 

Выбираем клетку (2,2) с наименьшим «реальным» тарифом равным 1.  Записываем в эту клетку максимально возможную поставку 45 ед. груза, т. е. наименьшее из чисел и . Исключаем при этом из дальнейшего рассмотрения поставщика (его возможности полностью исчерпаны). Запомним, что  потребитель еще нуждается в 70−45=25 ед. груза. Минимальный тариф равный 2 соответствует двум клеткам (3,1) и (3,3) выбираем любую, например клетку (3,1), помещаем в эту клетку 40 ед.  груза  (, ) и исключаем  из рассмотрения потребителя (его потребности полностью удовлетворены). У поставщика ещё имеется в 50−40=10 ед. груза. Заполним клетку (3,3), которой соответствует минимальный тариф равный 2, поставка в этой клетке равна 10 (, ), исключаем из рассмотрения . У потребителя еще имеется потребность в 30−10=20 ед. груза. В оставшейся части таблицы наименьший  тариф  3  соответствует клеткам (1,2) и (4,2), выберем клетку (4,2) и поместим поставку  25 ед. груза ().  Исключаем из рассмотрения  два пункта и одновременно, поэтому в клетку (4,3), стоящую рядом  с клеткой (4,2) запишем 0. В клетку (1,3) помещаем 20 ед. груза (), исключаем  потребителя . При этом у поставщика еще имеется в 30−20=10 ед. груза. Заполним  последнюю оставшуюся клетку (1,4) поставкой 10 единиц груза. Все запасы распределены, а потребности удовлетворены.

В опорном плане число занятых поставками клеток должно быть равно числу .

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6