Решение транспортной задачи симплекс-методом

Материал из Циклопедии
Перейти к: навигация, поиск

 → Транспортная задача

Решение транспортной задачи симплекс-методом — альтернатива способу решения транспортной задачи методом потенциалов. При этом данные транспортной таблицы выражают через линейные уравнения:[1]:296

Данциг 296.png

Например, для транспортной задачи с 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]:83

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]:296 Таха в своей разработке TORA применил формат транспортной задачи только для экранного представления данных, выполняя вычисления обычным симплекс-методом, поскольку он считает, что классический метод решения транспортной задачи при реализации на современном компьютере представляет лишь исторический интерес.[3]:206 Автор статьи считает, что те алгоритмы, которые обычно описывают по транспортной задаче в литературе (метод потенциалов), также вполне пригодны для практической реализации, что и было проделано им для системы 1С:Предприятие.[4]

[править] Источники

  1. 1,0 1,1 Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
  2. Б.Банди «Основы линейного программирования» М:Радио и связь, 1989 (djvu)
  3. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 912 с. — ISBN 5-8459-0740-3 (рус.) (djvu)
  4. http://kb.mista.ru/article.php?id=859


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты