![]() |
![]() |
Мастерская программиста Гирича Семёна Николаевича Решение задач линейного программирования |
|||||||||||
![]() |
|||||||||||||
|
|||||||||||||
![]() |
6.5. Пример решения транспортной задачи |
Задача: Решить транспортную задачу. Таблица - план перевозок по условию задачи:
Решение задачи. Первоначальный план перевозок. Задача сбалансированная (закрытая).Таблица 1.
Решим задачу с применением метода потенциалов. 1. Рассчитаем потенциалы пунктов отправки и пунктов доставки alfa и betta. Для этого составьте систему для заполненных клеток плана перевозок: betta[j] - alfa[i] = C[i,j]; где C - стоимость перевозки из пункта i в пункт j. Решим данную систему, полагая alfa[1]=0. 2. Вычислим коэффициенты изменения стоимости ( dC[i,j] ) для незаполненных клеток плана: dC[i,j] =betta[j] - alfa[i] - C[i,j]; Таблица 2.
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6] Количество единиц изменения плана: 6 Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2. Получим следующий план перевозок (Табл.3) Таблица 3.
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20] Количество единиц изменения плана: 20 Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3. Получим следующий план перевозок (Табл.4) Таблица 4.
Получим потенциалы alfa и betta. Рассчитаем коэффициенты изменения стоимости перевозок. Потенциалы и коэффициенты указаны в таблице 4. Полученный план оптимальный, т.к. все коэффициенты изменения стоимости (dC[i,j]) отрицательны или равны нулю. |
|
![]() |
![]() |
![]() |
|||||
© 2011 Семён Гирич, |
|
![]() ![]() |
|||||
![]() |
![]() |
![]() |