Решение транспортной задачи симплекс-методом
Решение транспортной задачи симплекс-методом — альтернатива способу решения транспортной задачи методом потенциалов. При этом данные транспортной таблицы выражают через линейные уравнения:[1]
Например, для транспортной задачи с 3 поставщиками и 5 потребителями (цены перевозки Cij — на пересечении строк и столбцов) вида
| Потребитель B1, потребность 20 шт. |
Потребитель B2, потребность 12 шт. |
Потребитель B3, потребность 5 шт. |
Потребитель B4, потребность 8 шт. |
Потребитель B4, потребность 15 шт. | |
|---|---|---|---|---|---|
| Поставщик A1, запас 15 шт. |
С11=1 | С12=0 | С13=3 | С14=4 | С15=2 |
| Поставщик A2, запас 25 шт. |
С21=5 | С22=1 | С23=2 | С24=3 | С25=3 |
| Поставщик A3, запас 20 шт. |
С31=4 | С32=8 | С33=1 | С34=4 | С35=3 |
можно построить следующую систему линейных уравнений:[2]
| x11 | +x12 | +x13 | +x14 | +x15 | =15 | ||||||||||
| x21 | +x22 | +x23 | +x24 | +x25 | =25 | ||||||||||
| x31 | +x32 | +x33 | +x34 | +x35 | =20 | ||||||||||
| x11 | +x21 | +x31 | =20 | ||||||||||||
| x12 | +x22 | +x32 | =12 | ||||||||||||
| x13 | +x23 | +x33 | =5 | ||||||||||||
| x14 | +x24 | +x34 | =8 | ||||||||||||
| x15 | +x25 | +x35 | =15 | ||||||||||||
| 1x11 | +0x12 | +3x13 | +4x14 | +2x15 | +5x21 | +1x22 | +2x23 | +3x24 | +3x25 | +4x31 | +8x32 | +1x33 | +4x34 | +3x35 | =z |
Данциг разрабатывал метод решения транспортной задачи, по его словам, независимо от предшественников, как способ конкретизации разработанного им симплекс-метода.[1] Таха в своей разработке TORA применил формат транспортной задачи только для экранного представления данных, выполняя вычисления обычным симплекс-методом, поскольку он считает, что классический метод решения транспортной задачи при реализации на современном компьютере представляет лишь исторический интерес.[3] Автор статьи считает, что те алгоритмы, которые обычно описывают по транспортной задаче в литературе (метод потенциалов), также вполне пригодны для практической реализации, что и было проделано им для системы 1С:Предприятие.[4]
Источники[править]
- ↑ 1,0 1,1 Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
- ↑ Б.Банди «Основы линейного программирования» М:Радио и связь, 1989 (djvu)
- ↑ Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 912 с. — ISBN 5-8459-0740-3 (рус.) (djvu)
- ↑ http://kb.mista.ru/article.php?id=859
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |