Оптимальное решение двойственной задачи

1 Я (осн.) 1000 — 78, 6 6, 47 0 -1, 84 0, 844 0 -0, 012

2 у_г (осн.) 11000 — 35, 7 5, 88 0 0, 16 -0, 16 0 -0, 024

3 у₄ (осн.) 1400 - 8, 57 1, 97 0 -0, 0008 0, 0008 0 -0, 55

4 у_т (изб.) - 5 ^' 8, 93 1, 04 0 0, 007 -0, 007 0, 025 -0, 064

5 ^'(осн.) -1000 - 8, 93 1, 04 -1 0, 007 -0, 007 0, 025 -0, 064

Индексная строка (Щ-В) 474500 -19590 0 -53 -947 -25 -1327

полнота симплекс-таблицы: симплекс-таблица, соответствую­щая прямой задаче, содержит всю информацию о решении двой­ственной и наоборот.

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

Теорема двойственности непосредственно иллюстрируется приведенными таблицами. Так, для задачи (4.6) 2_ор{ = Ж_ор1 = 6980; для задачи (4.7) 2_ор( = Ж_ор( = 47 450.

В справедливости утверждения о полноте симплекс-таблиц прямой и двойственной задач нетрудно убедиться, сравнивая их попарно. Специально укажем на соответствие между элементами индексной строки прямой задачи, расположенными в столбцах небазисных дополнительных переменных, и значениями основ­ных двойственных переменных, попавших в базис оптимального решения двойственной задачи. Так, в таблице 76 значения эле­ментов индексной строки для остаточных переменных х₅, х_в (по­рожденных соответственно 1-м и 2-м ограничениями прямой за­дачи 4.6) равны ассоциированным с этими ограничениями ос­новным двойственным переменным у_ь " у₂- Аналогичное утверж­дение можно сделать и относительно элементов индексной строки прямой задачи 4.7, соответствующих избыточной пере­менной х₅ и остаточным переменным хв, х₇, х$. Значения этих элементов совпадают со значениями ассоциированных с соответ­ствующими ограничениями двойственных переменных (ср. табл. 78 и 79).

Методы анализа оптимальных решений, основанные на взаи­мосвязях прямой и двойственной задач, подробно рассмотрены в главе 16.

Контрольные вопросы и задания

1. Сформулируйте общие требования к задачам, решаемым методами линейно­го программирования.

2. В чем состоит практическое значение линейного программирования? Како­вы его преимущества перед традиционными способами проектирования и эконо­мического обоснования проектных решений?

3. Назовите основные виды алгоритмов линейного программирования и оха­рактеризуйте кратко их суть.

4. Назовите основные составные части модели линейного программирования.

5. Укажите, какие аспекты землеустроительного проектирования отражают:
совокупность основных переменных задачи;

система линейных ограничений; целевая функция.

6. Как записывается целевая функция общей задачи линейного программирова­ния?

7. Приведите общий вид системы ограничений задачи линейного программи­рования. Какова стандартная форма записи ограничений?

8. Какие виды землеустроительных задач сводятся к общей задаче линейного программирования? Приведите соответствующие примеры.

9. Назовите основные этапы постановки задачи линейного программирования.

10. Как обычно записывают ресурсные ограничения в задачах линейного про­граммирования? Приведите примеры.

11. Какой вид обычно имеют ограничения, учитывающие плановые задания по производству продукции? Приведите примеры.

12. Каков общий вид ограничений по кормам? Какие разновидности ограниче­ний по кормам вы можете назвать?

13. Что такое избыточность системы ограничений? Приведите соответствующие примеры для случая ограничений по кормам.

14. Каковы основные особенности табличного представления задач линейного программирования?

15. Что называется каноническим видом (представлением) задачи линейного представления?

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

17. Перечислите разновидности дополнительных переменных.

18. Как привести к каноническому виду ограничение типа «>»? Каков экономи­ческий смысл избыточной переменной? Приведите примеры.

19. Как преобразовать к каноническому представлению ограничение типа «<»? • Каков экономический смысл остаточной переменной? Приведите примеры.

20. В ограничения какого типа вводят искусственные переменные? Какова цель их введения в каноническую запись задачи?

21. Как получить опорное решение задачи линейного программирования, ис­пользуя ее каноническое представление?

22. С какими коэффициентами входят в выражение для целевой функции в ка­ноническом представлении остаточные и избыточные переменные?

23. Каким образом необходимо включать в выражение для целевой функции ис­кусственные переменные в задачах на минимум и на максимум целевой функции?

24. Какими методами решаются общие задачи линейного программирования?

25. Что такое область допустимых значений (ОДЗ) основных переменных зада­чи линейного программирования? Чем определяются границы ОДЗ?

26. Приведите пример графического изображения области допустимых значе­ний задачи линейного программирования, в которой число основных переменных равно двум.

27. Как геометрически изображается целевая функция задачи линейного про­граммирования, в которой число основных переменных равно двум?

28. Что такое линия уровня целевой функции? Приведите пример уравнения для линии уровня.

29. Какому расположению линии уровня целевой функции соответствует опти­мальное решение задачи линейного программирования?

30. Что такое допустимое базисное решение задачи линейного программирова­ния? Каким точкам области допустимых значений соответствуют базисные реше­ния?

31. Каким должно быть число базисных переменных в базисном решении?

32. Перечислите правила построения первой симплекс-таблицы.

33. Чему равен нулевой элемент индексной строки симплекс-таблицы?

34. В чем смысл итерационной процедуры симплекс-метода?

35. Назовите последовательность шагов одной итерации симплекс-метода.

36. Как на основании анализа индексной строки симплекс-таблицы можно оп­ределить, оптимально полученное решение или нет?

37. Как определяется ключевой (разрешающий) столбец симплекс-таблицы на данной итерации?

38. Как определяют вводимую в базис переменную?

39. Как определяют ключевую (разрешающую) строку симплекс-таблицы на данной итерации?

40. Как определяют выводимую из базиса переменную?

41. Приведите формулы для расчета элементов новой симплекс-таблицы при частичной замене базиса.

42. Как осуществляется контроль вычислений при определении оптимального решения задачи линейного программирования?

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

44. По какой схеме строится двойственная задача? Что такое «двойственные пе­ременные, ассоциированные с ограничениями прямой задачи»?

45. К какому виду можно привести двойственную задачу, если в прямой задаче псе ограничения относятся к типу «<» и целевая функция максимизируется?

46. Как связаны между собой решения прямой и двойственной задач?

Глава 15 РАСПРЕДЕЛИТЕЛЬНАЯ (ТРАНСПОРТНАЯ) МОДЕЛЬ

15.1. ПОСТАНОВКА РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ

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

Идея этого метода принадлежит отечественным ученым (А.Толстой, Л.В.Канторович), которые в 1939—1940гг., по су­ществу, поставили и решили транспортную задачу с использова­нием метода потенциалов. Аналогичный метод, отличающийся лишь небольшой деталью, был предложен независимо в 1951г. американским ученым Дж. Данцигом и назван им модифициро­ванным распределительным методом (в зарубежной литературе он называется методом МОБ1).

Первоначально распределительный метод применялся в зада­чах, связанных с транспортировкой грузов, их распределением между несколькими пунктами отправления и приема; поэтому он известен также под названием «транспортная задача». Суть ее заключается в следующем.

Заданы т источников ресурса и п пунктов его потребления. Запасы ресурса в источниках составляют А-„ /= \,..., т, потребно­сти — Вр ]= 1,..., п. Стоимость транспортировки единицы ресурса от /-го источника ку'-му потребителю— Су, ху — количество ре­сурса, транспортируемого от /-го источника ку'-му потребителю. Требуется определить такие значения ху, при которых общие транспортные расходы будут минимальны. Задача предполагает­ся сбалансированной; общий запас ресурса у поставщиков и об­щий спрос на него у потребителей равны:

Т п

/=1 у=1

Такую задачу называют закрытой; если же этот баланс не вы­держивается, транспортная задача является открытой.

С учетом условия сбалансированности модель транспортной задачи может быть сформулирована следующим образом.

Целевая функция:

2= 2СуХу-> тт. _(15Л)

Ограничения по запасам:

П

2>, у=4-, 1=Ъ-, т. (15.2)

/=1

Ограничения по потребностям:

Т

%Ху = В_р У=1,..., «. (15.3)

/ = 1

Условие баланса:

Т п

Х4= X⁵/- (15.4)

(= 1 у'=1

Условия неотрицательности:

х, ₇> 0, /= 1,..., т, у'=1,..., и. (15.5)

Из данной модели видны важнейшие отличительные особен­ности распределительных (транспортных) задач:

условия задачи описываются только уравнениями (в симплек­сном методе ограничения задачи описывались и неравенствами);

все переменные выражаются в одних и тех же единицах изме­рения;

во всех уравнениях коэффициенты при переменных равны единице;

каждая переменная встречается только в двух уравнениях сис­темы ограничений: в одном по строке (по запасам) и в одном по, столбцу (по потребностям).

Целевая функция 2 выражает суммарные расходы на транс­портировку груза. Ограничения типа (15.2) и (15.3) означают, что' сумма ресурса, забираемого из /-го источника, должна быть рав-

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

Величины С» могли бы выражать не транспортные расходы, а, например, прибыль от транспортных операций. В этом случае также была бы возможна постановка задачи такого же типа, но с максимизацией целевой функции.

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

Задача 15.1. При землеустроительном обследовании в хозяй­стве было выделено 5 участков с различным плодородием, при­годных для трансформации угодий. Площади этих участков 250, 100, 520, 310 и 130 га. По проекту на них намечается разместить кормовой севооборот площадью 600 га, полевой — 560 га, улуч­шенные сенокосы — 150 га. Необходимо так распределить сево­обороты и угодья по участкам, чтобы чистый доход был макси­мальным. Дополнительная информация приведена в таблице 80.