Материал: Математические методы и модели в экономике. лабораторный практикум. Амелин С.В
Рис. 6.7. Результаты решения транспортной задачи
Открытая модель.
Составим план перевозок грузов от 4-х поставщиков Аi (i=1,2,3,4) соответственно в количествах 100, 400, 100 и 100 единиц к пяти потребителям Вj (j=1,2,3,4,5) соответственно в количествах 50, 100, 150, 200, 250 единиц с наименьшей стоимостью перевозок. Стоимость перевозок единицы груза представлена матрицей С:
|
1 |
6 |
8 |
12 |
16 |
||
|
|
|
|
|
|
|
|
16 |
10 |
8 |
6 |
15 |
|
||
C |
|
|
|
|
|
|
|
|
4 |
1 |
9 |
11 |
|
13 |
|
|
|
|
|
|
|
|
|
|
3 |
2 |
7 |
7 |
|
15 |
|
|
|
|
|||||
Решение. |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
Суммарные запасы (предложение) |
ai |
700 . |
|||||
|
|
|
|
i 1 |
|
|
|
|
|
|
|
5 |
|
|
|
Суммарные потребности (спрос) |
bj |
|
750. |
||||
j 1
Суммарный спрос превышает суммарное предложение, следовательно, модель открытая (2-й случай). Необходимо
85
ввести фиктивного поставщика А5 с запасами 750-700=50 единиц продукта.
Постав- |
|
Потребители |
|
Предло- |
||
щики |
В1 |
В2 |
В3 |
В4 |
В5 |
жение |
|
|
|
|
|
|
|
А1 |
1 |
6 |
8 |
12 |
16 |
100 |
|
Х11 |
Х12 |
Х13 |
Х14 |
Х15 |
|
А2 |
16 |
10 |
8 |
6 |
15 |
400 |
|
Х21 |
Х22 |
Х23 |
Х24 |
Х25 |
|
А3 |
4 |
1 |
9 |
11 |
15 |
100 |
|
Х31 |
Х32 |
Х33 |
Х34 |
Х35 |
|
А4 |
3 |
2 |
7 |
7 |
15 |
100 |
|
Х41 |
Х42 |
Х43 |
Х44 |
Х45 |
|
(А5) |
0 |
0 |
0 |
0 |
0 |
(50) |
|
Х51 |
Х52 |
Х53 |
Х54 |
Х55 |
|
Спрос |
50 |
100 |
150 |
200 |
250 |
Σ 850 |
Тогда математическая модель задачи примет вид:
(Х11 + 6Х12 + 8Х13 + 12Х14 + 16Х15 + 16Х21 + 10Х22 + 8Х23 + 6Х24 +
+15Х25 + 4Х31 + Х32 + 9Х33 + 11Х34 + 13Х35 + 3Х41 + 2Х43 +
+7Х43 + 7Х44 + 15Х45 + 0Х51 + 0Х52 + 0Х53 + 0Х54 + 0Х55) min.
Система ограничений имеет вид:
Х11 + Х12 + Х13 + Х14 + Х15 = 100 Х21 + Х22 + Х23 + Х24 + Х25 = 400 Х31 + Х32 + Х33 + Х34 + Х35 = 100 Х41 + Х42 + Х43 + Х44 + Х45 = 100 Х51 + Х52 + Х53 + Х54 + Х55 = 50 Х11 + Х21 + Х31 + Х41 + Х51 = 50 Х12 + Х22 + Х32 + Х42 + Х52 = 100 Х13 + Х23 + Х33 + Х43 + Х53 = 150 Х14 + Х24 + Х34 + Х44 + Х54 = 200 Х15 + Х25 + Х35 + Х55 + Х55 = 250
Для решения транспортной задачи можно использовать метод потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления Аi приписывается некоторое число Ui, а каждому пункту назначения Вj – число Vj. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство
Ui + Vj = Cij. |
(6.8) |
86
Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными Ui и Vj. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.
После того, как будут найдены все потенциалы Ui и Vj, для каждой свободной клетки (i, j) определяют числа
ij = Cij – (Ui + Vj). |
(6.9) |
Далее находим наибольшее по модулю отрицательное числоi0 j0 (т.е. самое малое из отрицательных) и делаем сдвиг по соот-
ветствующему циклу пересчета. Таким образом, в методе потенциалов для нахождения чисел ij не нужно искать циклы пересчета для всех свободных клеток. Надо найти только один цикл пересчёта, соответствующий наименьшему отрицательному i0 j0 .
Этапы метода потенциалов:
1.Найти первоначальный опорный план. Число заполненных клеток равно m + n – 1.
2.Найти потенциалы Ui и Vj. Составить для базисных клеток m + n – 1 уравнений с m + n неизвестными.
3.Для каждой свободной клетки найти значения ij = Cij –
–(Ui + Vj). Если среди значений ij нет отрицательных, то полученный план транспортной задачи оптимальный. Если же такие имеются, то перейти к новому опорному плану.
4.Среди отрицательных ij выбрать наибольшее по модулю отрицательное число ij. Построить для этой свободной клетки цикл пересчета и произвести сдвиг по циклу пересчета.
5.Полученный опорный план проверить на оптимальность. Если он не оптимален, то перейти к п. 2.
Ввод данных в программу «Транспортная задача» из ППП
PRIMA представлен на рис. 6.8. Решение задачи представлено на рис. 6.9.
87
Рис. 6.8. Заполнение диалоговой формы «Транспортная задача»
88
Рис. 6.9. Решения транспортной задачи в ППП PRIMA (начало)
89