Многоэтапная транспортная задача оптимального размещения и концентрации производства

Целевая функция задачи запишется в виде:

f₂ =9• X₁₁ + 3 • X₁₂ +...+ 3•X₆₆ (min)                          (2.2.5)

Сравнивая суммарные возможности промежуточных пунктов 100 + 30 + 70 + 240 + 160 + 200 = 800 со спросом потребителей 40 + 160 + 120 + 150 + 130 + 200 = 800, видим, что эти суммы совпадают. Следовательно, данная транспортная задача обладает закрытой моделью.

Переходя к ограничениям на переменные Х_kj, следует учесть, что спрос потребителей В_j, не может превышать возможности промежуточных пунктов, т.е.

  X₁₁ + X₁₂ + X₁₃ + X₁₄ + X₁₅ + X₁₆ =100

 X₂₁ + X₂₂ + X₂₃ + X₂₄ + X₂₅ + X₂₆ = 30                                   (2.2.6)

 X₃₁ + X₃₂+ X₃₃ + X₃₄+ X₃₅ + X₃₆ = 70

 X₄₁ + X₄₂+ X₄₃  + X₄₄+ X₄₅ + X₄₆ = 240

 X₅₁ + X₅₂+ X₅₃ + X₅₄+ X₅₅ + X₅₆ = 160

 X₆₁ + X₆₂+ X₆₃ + X₆₄+ X₆₅ + X₆₆ = 200

 

Условия удовлетворения спроса поставщиков Вj:

 X₁₁ + X₂₁ + X₃₁+ X₄₁+ X₅₁  + X₆₁ = 40

 X₁₂ + X₂₂ + X₃₂ + X₄₂+ X₅₂ + X₆₂ = 160

 X₁₃ + X₂₃+ X₃₃ + X₄₃ + X₅₃ + X₆₃ = 120

 X₁₄ + X₂₄+ X₃₄+ X₄₄ + X₅₄ + X₆₄ = 150                             (2.2.7)

 X₁₅ + X₂₅+ X₃₅+ X₄₅ + X₅₅  + X₆₅ = 130

 X₁₆ + X₂₆+ X₃₆+ X₄₆ + X₅₆ + X₆₆ = 200

          Условия неотрицательности переменных:

Х_ij  ≥0    (j=1,6; k=1,6)                                  (2.2.8)

Соотношения (2.2.5) - (2.2.8) образуют экономико-математическую модель рассматриваемой  задачи.

Таким образом, математическая модель задачи: целевая функция (2.2.5), описывающая суммарные затраты на втором этапе транспортировки, минимизируется при ограничениях (2.2.6) - (2.2.8).

    Решим полученную  транспортную задачу методом  потенциалов.

Таблица 2.7.

	В1 (40)	В2 (160)	В3 (120)	В4 (150)	В5 (130)	В6 (200)
D1 (100)	9	3	4	1	5	2 100	-2
D2 (30)	1 30	6	2	5	3	8	-1
D3 (70)	3	5	2	1 70	3	4 0	0
D4 (240)	7	2 160	5	1 80	4	6	0
D5 (160)	2 10	3	1 120	4	2 30	8	0
D6 (200)	5	3	2	4	1 100	3 100	-1
Vj	2	2	2	1	2	4

Приступая к составлению  исходного опорного плана, устанавливаем, что в нашем случае любой опорный план должен «загружать» m+n-1= 6+6-1=11  клеток.

Построим исходный опорный  план методом минимального элемента.

Для исследования плана  на оптимальность необходимо найти  оценки свободных клеток. Для этого

надо знать потенциалы U_i и V_j, которые определяются в результате решения системы уравнений                                                     

U₁ + V₆ = 2

U₂ + V₁ = 1

U₃ + V₄ = 1

U₃ + V₆ = 4

U₄ + V₂ = 2

U₄ + V₄ = 1

U₅ + V₁ = 2

U₅ + V₃ = 1

U₅ + V₅ = 2

U₆ + V₅ = 1

U₆ + V₆ = 3

 

составленных по заполненным  клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа  уравнений. Придадим одному из неизвестных  определенное числовое значение, например, U₁ = 0. Тогда остальные неизвестные находятся из системы.

   Получаем

U₁ = 0-2 U₂ = -1, U₃ = 0, U₄ = 0, U₅ = 0, U₆ = -1,V₁ = 2, V₂ = 2, V₃ = 2, V₄ = 1, V₅ = 2, V₆ = 4.

Теперь можно найти  оценки свободных клеток: Δ₁₁ = C₁₁ - (U₁ + V₁) = 9-(2-2)= 9 и так далее. Поскольку в таблице 2.8  свободных клеток с отрицательными оценками нет, то опорный план является оптимальным.

Итак,  получен  оптимальный  план:

 

	0	0	0	0	0	100
	30	0	0	0	0	0
X*=	0	0	0	70	0	0
	0	160	0	80	0	0
	10	0	120	0	30	0
	0	0	0	0	100	100

 

 

 

 

    

 

 Этому плану соответствуют  минимальные суммарные затраты в 1300 ден. ед.

( f₂ = 100∙2 + 30∙1 + 70∙1 + 160∙2 + 80∙1+ 10∙2 + 120∙1 + 30∙2 + 100∙1 + 100∙3 = 1300) 

    Общие транспортные  затраты в данном случае составят:

f = f₁ + f₂ = 1280 + 1300 = 2580 ден.ед.

   Изобразим решение  данной задачи на рисунке 2.2.

 

2.3. Сравнивая полученные результаты в пунктах 2.1 и 2.2, можем сделать вывод, что в нашем случае планы, полученные в пунктах 2.1 и 2.2 равнозначны. Так как суммарные транспортные затраты в обоих планах одинаковы и равны 2580 ден. ед.

2.4. Решим двухэтапные транспортные задачи с учетом дополнительных ограничений.

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

Z_min = (40∙1 + 80∙3 + 80∙1 + 30∙1 + 160∙1 + 110∙3+ 30∙4 + 130∙3 + 90∙2 + 20∙1 + 30∙2) + (100∙2 + 30∙1 + 70∙4 + 150∙1 + 10∙6+ 80∙4 + 10∙2 + 30∙3 + 120∙1 + 130∙3+ 50∙1+ 20∙3) = 3420 тыс. ден. ед.

    Можем сделать  вывод, что введение дополнительных  ограничений, привело к повышению  значения целевой функции на 3420 – 2580 = 840 ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.5 Компьютерная реализация.

      2.5.1. Решим задачу пункта 2.1 в среде Microsoft Excel, используя надстройку поиск решения.

    Создадим математическую  форму и введем исходные данные.

    Заполним диалоговое  окно поиск решения.

   В результате  получим:

     

Мы получили план перевозок c такими же суммарными затратами, что и в пункте 2.1. Следовательно, задача решена нами верно.

 

2.5.2. Решим задачу пункта 2.2 в среде Microsoft Excel, используя надстройку поиск решения.

    Создадим математическую  форму и введем исходные данные  для первого этапа задачи.

 

 В результате получим:

   

Создадим математическую форму и введем исходные данные для  второго этапа задачи.

 

 В результате получим:

   Мы получили  такое же решение, что и в пункте 2.2. Следовательно, в пункте 2.2 задача решена верно.

 

2.5.3. Решим двухэтапную транспортную задачу с учетом дополнительных ограничений:

5. Из А1 в Д1 можно перевезти не менее 80 единиц груза,

Из А3 в  Д4 перевозки не осуществляются и из Д4 в В2 перевозки так же запрещены,

Из Д6 в  В5 можно перевезти не более 50 единиц груза.

   Используя форму  задачи пункта 2.5.1, дополним в  диалоговое окно поиск решения  заданные три ограничения, получим:

 

    Можем сделать  вывод, что введение дополнительных ограничений, привело к повышению значения целевой функции на 3420 – 2580 = 840 ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Заключение.

     Подводя  итоги, проделанной нами работы, можем сделать вывод, что для  рассматриваемого нами случая  двухэтапной транспортной, когда возможности поставщиков равны потребностям потребителей, а вместимость промежуточных пунктов не превосходит по величине объем грузоперевозок, наиболее подходящим методом решения будет метод сведения двухэтапной транспортной задачи к классической задачи линейного программирования. Данный метод рассмотрен нами в пункте 2.1. главы 2. Значение целевой функции, полученное данным методом в нашем случае равно значению  целевой функции, полученной в пункте 2.2. Обычно значение целевой функции, полученной при решении двухэтапной транспортной задачи выше значения целевой функции, полученной методом раздельного прикрепления. В нашем случае эти значения равны. Это объясняется тем, что данная задача имеет несколько оптимальных решений.

       Анализируя влияние дополнительных ограничений, рассмотренное нами в пункте 2.4 главы 2, можем отметить, что при их введении  значение целевой функции возрастает на 840 тыс. ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература.

1. Таха X. Введение в исследование операций. М: Издательский дом "Вильяме", 2001. -912с.
2. Эддоус М., Стэнсфилд Р. Методы принятия решений. М.: Юнити, 1997. - 590 с.
3. Кузнецов  А.В.,   Сакович  В.А.,   Холод  II.И.   Высшая   математика:   Математическое программирование. Мн.: Вышэйшая школа, 2001. - 351 с.
4. Сборник    задач     и     упражнений     по     высшей     математике:     Математическое программирование / Под общей ред. А.В.Кузнецова и Р.А.Рутковского. Мн.: Вышэйшая школа, 2002. - 447 с.
5. Экономико-математические методы и модели / Под ред. А.В. Кузнецова. Мн.: БГЭУ,1999.-413с.
6. Исследование операций в экономике / Под ред. НЛП. Кремера. М.: Банки и биржи -Юнити, 1997.-407с.
7. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Высшая школа, 2001. - 208 с.
8. Смородинский С.С.,  Батин Н.В.   Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003. - 136 с.
9. Смородинский    С.С.,    Батин    Н.В.    Методы    анализа    и    принятия    решений    в слабоструктурированных задачах. Мн.: БГУИР, 2002. - 116с.

10. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических      моделей. Мн.: БГУИР, 1997. - 77 с.

 

 

 

 

 

 

 

 

 

 

 

Помощь на экзамене, зачете, тесте.