Решение транспортных задач, имеющих некоторые дополнительные условия. Задача с распределением резерва (спрос не равен предложению)

РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ, ИМЕЮЩИХ НЕКОТОРЫЕ ДОПОЛНИТЕЛЬНЫЕ УСЛОВИЯ

ТЕМА 6. ТРАНСПОРТНАЯ СЕТЬ

Задача с распределением резерва (спрос не равен предложению). Исключим из задачи, условия которой записаны в табл. 2, четвертого потребителя груза, оставив все остальные данные и требования без изменений. Таким образом, у грузоотправителей окажется 600 т груза в запасе (в резерве), который никому не вывозится (спрос меньше предложения). В этом случае задача решается следующим образом.

Условия задачи записываются в таблицу (табл. 22), в которой вместо столбца четвертого грузополучателя вводится фиктивный столбец Р с ограничением по спросу в 600 т, который равен разности между суммами фактических величин предложения и спроса (2000 - 1400 = 600).

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

В данном случае задача решена с помощью метода аппроксимации Фогеля и модифицированного распределительного метода.

Полученное решение кроме оптимального закрепления потребителей за грузоотправителями показывает, что наиболее рационально, с точки зрения транспортных затрат, иметь 400 т резервного запаса груза у поставщика А₁ и 200 т. — у грузовладельца А₂.

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

Запрещение корреспонденции. В практике организации и планирования работы транспорта могут возникать ситуации, когда в силу каких-то причин невозможно удовлетворить спрос потребителя B _j поставками из А _і, т. е. на корреспонденцию из А _і в B _j налагается запрет.

Например, наложим запрет на перевозки груза от поставщика А₂ потребителю В₂ (см. табл. 22). Чтобы решить задачу, достаточно вместо реального элемента целевой матрицы, стоящего в клетке А₂В₂ (2), поставить очень большую величину М, которая больше любого наперед заданного числа, или поставить какое-либо число, например 100, которое больше любого элемента целевой матрицы, имеющегося в данной, задаче.

Обязательная, или директивная, корреспонденция означает обязательность поставки из точки А _і в точку В _j части или всего объема материалов, имеющихся в А _і. В этом случае величина обязательной поставки вычитается из суммы спроса B _j и суммы ограничения А _і и при решении задачи не учитывается.

Например, из точки А₃ нужно обязательно завести 400 т груза в В₃ (см. табл. 2). Следовательно, при решении задачи ограничения столбца В₃ и строки А₃ уменьшаются на 400 т. и будут равны: для В₃ — 400 т. (800 – 400 = 400) и для А₃ — 600 т. (1000 - 400 = 600).

При подсчете окончательного значения грузооборота обязательный объем (400 × 8 = 3200 т.км) прибавляется к полученному оптимальному объему грузооборота.

Планирование грузопотоков взаимозаменяемых продуктов производится после того, как их объем с помощью переводных коэффициентов будет выражен в условных единицах.

Таблица 4.22

Например, у поставщиков имеются разные виды топлива (у А₁ — уголь; А₂ — торф; А₃ — дрова и т. д.), а потребителям безразлично, какое будет поставлено топливо, только бы оно обеспечивало необходимые мощности их нагревательных устройств. Известно, что разное, топливо имеет различную теплотворную способность. Чтобы выразить все виды имеющегося топлива в сопоставимых величинах, нужно будет перевести его в условные единицы. Условные единицы топлива будут выражать ограничения по спросу и предложению. Далее задача решается обычным путем.

Открытая модель распределительного метода возникает в случаях, когда отсутствует какая-либо из групп ограничений — спрос Σ b_j,- или предложение Σ а _i. Это означает, что любой потребитель может взять всю сумму имеющихся у поставщиков материалов или, наоборот, любой из поставщиков может удовлетворить спрос всех потребителей данного материала.

Задача решается, просто. Если отсутствуют ограничения по предложению, то ограничения по спросу в каждом столбце таблицы переносятся в клетки с оптимальным элементом целевой матрицы данного столбца, а при отсутствии ограничений по спросу — в клетки каждой строки.

Полученное решение всегда будет оптимальным. Пример. Чтобы удовлет-ворить потребности в строительном песке пяти потребителей В₁ В₂; В₃; В₄; В₅, его можно добывать в неограниченном количестве в любой из трех точек А₁, А₂; А₃. Потребность: В₁ — 300, В₂ — 200, В₃ — 400, В₄ — 250 и В₅ — 400 т в сутки.

Расстояния (элементы целевой матрицы) между потребителями и возмож-ными местами добычи песка указаны в правых верхних углах клеток табл. 23.

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

Все условия задачи занесены в табл. 23. Переносим ограничения спроса по столбцам в клетки с минимальными расстояниями А₁В₁, А₃В₂; А₃В₃; А₁В₄; A₃B₅. Таким образом, эти клетки получат загрузку в 300; 200; 400; 250 и 400 т (табл. 24).

Поскольку загружались клетки с оптимальным зна­чением элемента целевой матрицы, то полученное втабл. 24 решение, с точки зрения транспортной работы, будет оптимальным. При этом решении добыча песка в точках А₁ и А₂ должна быть равна соответственно 550 и 1000 т. В точке А₂ добычу вести нерационально. Открытая модель распределительного метода встречается при решении целого ряда задач: определения оптимального размещения и мощности автотранспортных предприятий, закрепления маршрутов за АТП, размещения и мощности предприятий добывающей и обрабатывающей промышленности, размещения и емкости складов и др.

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

Таблица 23

Таблица 4.24

Заменим в задаче, условия которой записаны в табл. 2, расстояние между точками А₁ и В₃ на 6 км вместо 10 км. Остальные условия оставим прежними. Пользуясь методом МОДИ, найдем оптимальное решение (табл. 25).

Таблица 25

Объем грузовой работы при оптимальном решении равен 11200 ткм. Однако в этой задаче имеется другое базисное оптимальное решение с точно таким же объемом грузовой работы, но другим вариантом грузопотоков. Оно получится, если загрузить клетку А₁В₃, перераспределив загрузку в клетках А₁В₄, А₃В₃ и А₃В₄, учитывая ограничения по спросу и предложению (табл. 26). Следовательно, имеются два базисных оптимальных решения (табл. 25 и 26).

Переместив 400 т груза из клетки А₃В₃ в ранее свободную клетку А₁В₃ и из клетки А₁В₄ — в клетку А₃В₄, мы получили другой вариант оптимального решения (другой базис). При этом от первого перемещения было получено сокращение грузооборота на 400-2 = 800 ткм, а от второго — увеличение на 800 ткм, т. е. грузооборот остался прежним, а грузопотоки изменились. Потенциалы и их суммы для всех клеток матрицы (см. табл. 25 и 26) одинаковы.

Таблица 26

Сохранить неизменными в табл..26 потенциалы позволило то обстоятельство, что в свободной клетке А₁В₃ табл. 25 сумма потенциалов равна элементу целевой функции. Это же мы замечаем и для клетки A₁B₄ табл. 26.

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

Но если имеется хотя бы одно альтернативное базисное решение, то имеется бесчисленное множество оптимальных решений. В этом нетрудно убедиться, если в клетках А₁В₃, А₁В₄, А₃В₃ и А₃В₄ изменять загрузку в различных вариантах, не нарушая ограничений по спросу и предложению.

Признаками наличия альтернативного оптимальною базисного решения в первом (метод Хичкока) и втором (метод Креко) способах решения задач распределительным методом являются нулевые суммы потенциалов с элементом целевой матрицы (первый способ) и элементов целевой матрицы контура (второй способ) хотя бы в одной свободной клетке.

Распределительный метод достаточно прост, он позволяет решать широкий круг различных задач как транспортных, так и других отраслей народного хозяйства. Его существенным недостатком является то, что им пользоваться можно только когда имеем дело с однородными величинами (однородный груз, однородный подвижной состав, условные однородные величины и т. п.).

КОНТРОЛЬНІ ПИТАННЯ

1. Що називається припустимими базисними рішеннями? Яким крапкам припустимої безлічі рішень вони відповідають?

2. Сформулюйте основну теорему лінійного програмування. Який практичний висновок про можливий метод відшукання оптимальних рішень витікає з неї?

3. Як вибирається напрямний стовпець при рішенні завдання лінійного програмування (ЛП) на максимум і мінімум табличним симплексом-методом?

4. Сформулюйте ознаку оптимальності д.б.р. при рішенні симплексом-методом завдання ЛЦ на максимум і мінімум.

5. Який зміст двоїстих змінних й цільовий функції двоїстого завдання, якщо пряме завдання максимізації?

6. При яких умовах вигідніше вирішувати двоїсте ЛП завдання, чим пряму?

7. Як знайти оптимальне рішення двоїстого завдання, вирішуючи відповідне пряме завдання, і навпаки?

8. Як зв'язані між собою оптимальні значення цільової функції прямій і двоїстого завдання?

9. Як зв'язані між собою компоненти оптимального рішення прямого завдання й обмеження двоїстого завдання й навпаки?

10. Дайте економічну інтерпретацію теорем 2.6 й 2.7 подвійності.

11. Як провести дослідження моделей завдань ЛП на чутливість? Який зміст оптимальних значень подвійних змінних?

12. Використовуючи прийом доведіть справедливість теорем 2.6 й 2.7 (принцип рентабельності) для пари двоїстих завдань при довільних обмеженнях.

13. Як визначити кількість штучних змінних, які варто вводити в обмеження завдання ЛП? Поясніть зміст коефіцієнтів +М (-М), з якими вводяться штучні змінні в цільову функцію.

14. Як зв'язані між собою розв'язний вектор А для прямого завдання й оптимальні плани (рішення) двоїстої.

15. Сформулюйте ознаку оптимальності поточного плану при використанні розв'язних множників.

16. Дайте визначення псевдоплана. Якою властивістю володіють оцінки векторів будь-якого псевдоплана? Чим відрізняється псевдоплан від довільного припустимого базисного рішення?

17.Яким умовам повинен задовольняти довільний сполучений базис й як його знайти?

18. Сформулюйте ознаку нерозв'язності Лп-задачі при її рішенні із двоїстим симплексом-методом і дайте його обґрунтування.

20. Укажіть подібності й розходження звичайного симплекса-методу й двоїстого симплекса-методу.

21. Поясніть основну ідею методу декомпозиції Данцига-Вульфа. На якій властивості безлічі рішень Лп-задач базується цей метод?

22. Поясніть зміст координуючого завдання в методі декомпозиції.

23. Чому метод декомпозиції використає метод зворотної матриці (модифікований симплекс-метод)?

24. Сформулюйте признак. оптимальності при рішенні Лп-задач методом декомпозиції й доведіть його справедливість.

25. Сформулюйте умову можливості розв'язання транспортного завдання.

26. Назвіть ознаку оптимальності плану Т-задачі й поясніть зміст його умов.

27. Що називається опорним планом Т-задачі?

28. Як перевірити довільний план на спірність?

29. Який план називається виродженим? Як установити, чи є опорний план виродженням?

30. Дайте обґрунтування методу потенціалів, розглядаючи його як варіант симплекса-методу.

31. Як вирішувати Т-задачу методом потенціалів на максимум? Як при цьому зміниться правило вибору елемента xt/, що вводить у базис, і ознака оптимальності опорного плану?

32. У якому випадку застосування методу мінімального елемента приводить до скорочення числа ітерацій у порівнянні про метод північно-західного кута?

33. Чому при рішенні Т-задачі угорським методом ланцюжок у матриці X будується обов'язково з нульових елементів?

34. Як зміниться попередній етап угорського методу при рішенні Т-задачі на максимум?

35. У чому складаються особливості угорського методу в порівнянні G методом потенціалів?

36 Чи можуть елементи од виявитися негативними в процесі рішення Т-задачі угорським методом?

37. Дайте обґрунтування угорського методу для рішення Т-задачі.

38. Як звести відкриту модель Т-задачі до закритого?

38. Сформулюйте основні властивості потоку на мережі.

40. Як записується умова балансу для транспортної мережі?

41. Сформулюйте теорему Форда-Фалкерсона й доведіть її справедливість.

42. Сформулюйте ознаку оптимальності алгебраїчного плану транспортної мережі, зрівняєте його з відповідною ознакою для Т-задачи.

43. Ознака спірності алгебраїчного плану транспортної мережі.

44. Як знайти початковий опорний план для мережі?

45. Коли доцільне використання декомпозиціонного методу для рішення транспортних завдань?

146. Перелічить основні математичні моделі дискретного програмування.

47. Що називається правильним відсіканням, як воно формується в методі площин, що відтинають?

48. Який геометричний зміст має правильне відсікання?

49. Чи можуть величини γ_ιƒ бути негативними, якщо, наприклад, χ_ιƒ<0?

50. Що являє собою повну безліч всіх відсікань, формованих по деякій симплексі-таблиці? Як знайти потужність цієї безлічі?

51. Чому в методі площин, що відтинають, використається двоїстий симплекс-метод?

7. Сформулюйте достатні умови можливості переходу до асимптотичного завдання при рішенні завдання ЛЦП методом Гомори й поясните їхній зміст.

52. Яка основна ідея методу галузей і границь? У чому складаються особливості його реалізації при рішенні конкретних класів завдань (моделей)?

53. Як виробляються розгалуження безлічі й обчислюються оцінки при рішенні методом галузей завдання лінійного цілочисленного програмування (ЛЦП) на мінімум і максимум?

54. Яка аналогія існує між методом Гомори й методом галузей і границь стосовно до завдань ЛЦП?

55. Як виробляються розгалуження безлічі й обчислюються оцінки при рішенні методом галузей і границь завдання про комівояжера?

56. Укажіть основні достоїнства й недоліки методу галузей і границь при рішенні комбінаторних завдань дискретного програмування.

57. У чому сутність обчислювального методу динамічного програмування?

58. Сформулюйте принцип оптимальності Беллмана й поясните його зміст.

59. Для завдань якої структури можливе застосування методу динамічного програмування?

60. Укажіть умови, при яких завдання вирішується методом динамічного програмування у зворотному напрямку й, навпаки, у прямому напрямку.

61. Який основний недолік динамічного програмування?

62. Назвіть методи зниження розмірності завдань динамічного програмування.

63. Укажіть головні компоненти завдання керування запасами.

64. Виведіть формули для найпростішого завдання керування запасами з постійним попитом і періодичними поставками, коли період між поставками постійний.

65. У якій моделі керування запасами використається дворівнева стратегія і як вона формулюється?

66. У яких завданнях керування запасами використається метод динамічного програмування?

67. Укажіть основні труднощі, що виникають при рішенні завдання нелінійного програмування.

68. При яких обмеженнях можна застосовувати метод множників Лагранжа?

69. Який зміст мають множники Лагранжа?

70. Сформулюйте теорему Куна -танкера. У чому складається її значення для рішення Нп-задач?

71. Поясните зміст умов регулярності. Який вид вони можуть приймати?

72. Поясните зміст умов нетвердості, що доповнює.

73. Запишіть умови теореми Куна-Таккера для Нп-задачі при додаткових обмеженнях незаперечності.

74. Як зв'язані між собою оптимальні рішення пари двоїстих Лп-задачі сідлова крапка відповідної функції Лагранжа?

75. Який зв'язок існує між оптимальним рішенням завдання нелінійного програмування й сідловом крапкою функції Лагранжа для цього завдання?

76. Яка властивість геометричної нерівності лежить в основі методів геометричного програмування?

77. Сформулюйте основну теорему геометричного програмування й покажіть її зв'язок з теорією подвійності.

78. Який зміст має умова "існує таке рішення t, що g_i(t) < 0; i = 1, р», використовуване в цій теоремі?

79. Що таке ступінь труднощів завдання геометричного програмування?