Постановка задачи:
Имеется 3 пункта отправления и 4 пункта назначения. Пункты отправления характеризуются объемом предложений, а пункты назначения – спросом. Пункты отправления соединены с пунктами назначения. Стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту.
Требуется определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок.
Цели типового расчета:
- Сбалансировать транспортную задачу (если она несбалансированная).
- Сформулировать задачу линейного программирования математически (целевая функция и ограничения).
- Решить транспортную задачу двумя методами:
- симплекс-методом;
- методом, основанным на использовании транспортной таблицы.
- Провести анализ чувствительности оптимального решения (интервалы изменений коэффициентов целевой функции), вычислить двойственные цены ресурсов.
При решении методом, основанным на использовании транспортной таблицы, начальное решение определять одним из следующих методов:
- Метод северо-западного угла.
- Метод наименьшей стоимости.
- Метод Фогеля.
Номер метода определения начального решения = 2 + (вариант mod 3).
Вариант 15 | 1 | 2 | 3 | 4 | ||||
1 | x11 | 89 | x12 | 133 | x13 | 52 | x14 | 74 |
2 | x21 | 100 | x22 | 92 | x23 | 50 | x24 | 65 |
3 | x31 | 81 | x32 | 89 | x33 | 104 | x34 | 76 |
Спрос | 1439 | 1115 | 2058 | 1495 |
Решение:
Следовательно:
Начальное решение для решения транспортной задачи определяется методом северо-западного угла.
Сбалансированная транспортная задача:
1 | 2 | 3 | 4 | Предложение | |||||
1 | x11 | 89 | x12 | 133 | x13 | 52 | x14 | 74 | 1079 |
2 | x21 | 100 | x22 | 92 | x23 | 50 | x24 | 65 | 2063 |
3 | x31 | 81 | x32 | 89 | x33 | 104 | x34 | 76 | 1226 |
4 | x41 | 1000 | x42 | 1000 | x43 | 1000 | x44 | 1000 | 1739 |
1439 | 1115 | 2058 | 1495 |
|
Соответствующая задача линейного типа:
z= 89×1+133×2+52×3+74×4+100×5+92×6+50×7+65×8+ 81×9+89×10+104×11+76×12+1000×13+ 1000×14+ 1000×15+ 1000×16]
Ограничения:
1 2 3 4 5 6 7 8 |
1x1 1x2 1x3 1x4 0x5 0x6 0x7 0x8 0x9 0x10 0x11 0x12 0x13 014 0x15 0 x16 = 1079 0x1 0x2 0x3 0x4 1x5 1x6 1x7 1x8 0x9 0x10 0x11 0x12 0x13 0x14 0x15 0x16 = 2063 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 1x9 1x10 1x11 1x12 0x13 0x14 0x15 0x16 = 1226 0x1 0x2 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0x10 0x11 0x12 1x13 1x14 1x15 1x16 = 1739 1x1 0x2 0x3 0x4 1x5 0x6 0x7 0x8 1x9 0x10 0x11 0x12 1x13 0x14 0x15 0x16 = 1439 0x1 1x2 0x3 0x4 0x5 1x6 0x7 0x8 0x9 1x10 0x11 0x12 0x13 1x14 0x15 0x16 = 1115 0x1 0x2 1x3 0x4 0x5 0x6 1x7 0x8 0x9 0x10 1x11 0x12 0x13 0x14 1x15 0x16 = 2058 0x1 0x2 0x3 1x4 0x5 0x6 0x7 1x8 0x9 0x10 0x11 1x12 0x13 0x14 0x15 1x16 = 1495 |
РЕШЕНИЕ СИМПЛЕКС МЕТОДОМ
1 2 3 4 5 6 7 8 9 |
1911 1867 1948 1926 1900 1908 1950 1935 1919 1911 1896 1924 1000 1000 1000 1000 0 0 0 0 0 0 0 0 12214000 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2063 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1226 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1439 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 2058 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1495 |
1 2 3 4 5 6 7 8 9 |
1911 1867 -2 1926 1900 1908 0 1935 1919 1911 -54 1924 1000 1000 -950 1000 0 0 0 0 0 0 -1950 0 8200900 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 0 0 -1 0 1 1 0 1 0 0 -1 0 0 0 -1 0 0 1 0 0 0 0 -1 0 5 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1226 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1439 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 2058 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1495 |
1 2 3 4 5 6 7 8 9 |
1911 1867 1933 1926 -35 -27 0 0 1919 1911 1881 1924 1000 1000 985 1000 0 -1935 0 0 0 0 -15 0 8191225 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 0 0 -1 0 1 1 0 1 0 0 -1 0 0 0 -1 0 0 1 0 0 0 0 -1 0 5 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1226 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1439 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 2058 0 0 1 1 -1 -1 0 0 0 0 1 1 0 0 1 1 0 -1 0 0 0 0 1 1 1490 |
1 2 3 4 5 6 7 8 9 |
-22 -66 0 -7 -35 -27 0 0 1919 1911 1881 1924 1000 1000 985 1000 -1933 -1935 0 0 0 0 -15 0 6105518 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 1 1 0 1 1 1 0 1 0 0 -1 0 0 0 -1 0 1 1 0 0 0 0 -1 0 1084 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1226 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1439 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 -1 -1 0 -1 0 0 1 0 0 0 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 979 -1 -1 0 0 -1 -1 0 0 0 0 1 1 0 0 1 1 -1 -1 0 0 0 0 1 1 411 |
1 2 3 4 5 6 7 8 9 |
1902 1858 0 -7 1889 1897 0 0 1919 1911 -43 0 1000 1000 -939 -924 -9 -11 0 0 0 0 -1939 -1924 5314754 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 1 1 0 1 1 1 0 1 0 0 -1 0 0 0 -1 0 1 1 0 0 0 0 -1 0 1084 1 1 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 1 1 1 0 0 0 -1 -1 815 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1439 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 -1 -1 0 -1 0 0 1 0 0 0 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 979 -1 -1 0 0 -1 -1 0 0 0 0 1 1 0 0 1 1 -1 -1 0 0 0 0 1 1 411 |
1 2 3 4 5 6 7 8 9 |
-17 -61 0 -7 -30 -22 0 0 0 -8 -43 0 1000 1000 980 995 -1928 -1930 -1919 0 0 0 -20 -5 3750769 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 1 1 0 1 1 1 0 1 0 0 -1 0 0 0 -1 0 1 1 0 0 0 0 -1 0 1084 1 1 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 1 1 1 0 0 0 -1 -1 815 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1739 0 -1 0 0 0 -1 0 0 0 -1 0 0 1 0 1 1 -1 -1 -1 0 1 0 1 1 624 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 -1 -1 0 -1 0 0 1 0 0 0 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 979 -1 -1 0 0 -1 -1 0 0 0 0 1 1 0 0 1 1 -1 -1 0 0 0 0 1 1 411 |
1 2 3 4 5 6 7 8 9 |
-17 939 0 -7 -30 978 0 0 0 992 -43 0 0 1000 -20 -5 -928 -930 -919 0 -1000 0 -1020 -1005 3126769 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 1 1 0 1 1 1 0 1 0 0 -1 0 0 0 -1 0 1 1 0 0 0 0 -1 0 1084 1 1 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 1 1 1 0 0 0 -1 -1 815 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 -1 0 -1 -1 1115 0 -1 0 0 0 -1 0 0 0 -1 0 0 1 0 1 1 -1 -1 -1 0 1 0 1 1 624 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1115 -1 -1 0 -1 0 0 1 0 0 0 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 979 -1 -1 0 0 -1 -1 0 0 0 0 1 1 0 0 1 1 -1 -1 0 0 0 0 1 1 411 |
Окончательный результат:
1 2 3 4 5 6 7 8 9 |
1 -17 -61 0 -7 -30 -22 0 0 0 -8 -43 0 0 0 -20 -5 -1928 -1930 -1919 -1000 0 0 -20 -5 2011769 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1079 8 1 1 0 1 1 1 0 1 0 0 -1 0 0 0 -1 0 1 1 0 0 0 0 -1 0 1084 9 1 1 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 1 1 1 0 0 0 -1 -1 815 14 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 -1 0 -1 -1 1115 13 0 -1 0 0 0 -1 0 0 0 -1 0 0 1 0 1 1 -1 -1 -1 0 1 0 1 1 624 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 -1 -1 1 1 1 1 0 7 -1 -1 0 -1 0 0 1 0 0 0 1 0 0 0 1 0 -1 0 0 0 0 0 1 0 979 12 -1 -1 0 0 -1 -1 0 0 0 0 1 1 0 0 1 1 -1 -1 0 0 0 0 1 1 411 |
Отсюда следует:
1 2 3 4 5 6 7 |
x3=1079 x8=1084 x9=815 x14=1115 x13=624 x7=979 x12=411 |
411РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ
Начальное базисное решение, определённое методом северо-западного-угла:
1 2 3 4 5 6 |
X = 1079 -1 -1 -1 360 1115 588 -1 -1 -1 1226 -1 -1 -1 244 1495 |
Итерации решения транспортной задачи (числа -1 означают, что данный х=0):
1 2 3 4 |
1079 -1 -1 -1 360 1115 588 -1 -1 -1 1226 -1 -1 -1 244 1495 |
1 2 3 4 |
1079 -1 -1 -1 -1 1115 948 -1 360 -1 866 -1 -1 -1 244 1495 |
1 2 3 4 |
213 -1 866 -1 -1 1115 948 -1 1226 -1 -1 -1 -1 -1 244 1495 |
1 2 3 4 |
213 -1 866 -1 -1 871 1192 -1 1226 -1 -1 -1 -1 244 -1 1495 |
1 2 3 4 |
213 -1 866 -1 -1 -1 1192 871 1226 -1 -1 -1 -1 1115 -1 624 |
1 2 3 4 |
-1 -1 1079 -1 -1 -1 979 1084 1226 -1 -1 -1 213 1115 -1 411 |
Окончательное решение:
1 2 3 4 |
-1 -1 1079 -1 -1 -1 979 1084 815 -1 -1 411 624 1115 -1 -1 |
Отсюда:
1 2 3 4 5 6 7 |
x13=1079 x23=979 x24=1084 x31=815 x34=411 x41=624 x42=1115 |
Анализ чувствительности выдал следующий результат:
Двойственные цены:
1 2 3 4 5 6 7 |
y1=-928 y2=-930 y3=-919 y4=0 y5=1000 y6=1000 y7=980 y8=995 Intervals for right parts of limits: 264<=b1<=1079 1248<=b2<=2063 411<=b3<=1226 624<=b4<=1739 1439<=b5<=2554 1115<=b6<=∞ 2058<=b7<=2873 1495<=b8<=2310 Intervals for coefficients in Z function: 72<=c1<=∞ 72<=c2<=∞ -∞<=c3<=59 67<=c4<=∞ 70<=c5<=∞ 70<=c6<=∞ 43<=c7<=70 45<=c8<=72 76<=c9<=89 81<=c10<=∞ 61<=c11<=∞ 59<=c12<=81 992<=c13<=1000 1000<=c14<=1008 980<=c15<=∞ 995<=c16<=∞ |
Скачать ZIP-архив с исходными кодами