Транспортная задача
Пример.
Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.
Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:
(6)
При данном плане перевозок общая стоимость перевозок составит
(7)
Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (6), при котором целевая функция (7) принимает минимальное значение.
Пример нахождения опорного плана
Поставщики | Потребители и их спрос | Мощность поставщиков | |||
F=14 x11 + 28 x12 + 21 x13 + 28 x14 + 10 x21 + 17 x 22 + 15 x23 + 24 x24 + 14 x31 + 30 x32 +25 x33 + 21 x34
Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).
Таблица 1
Стоимость перевозок по данному плану составляет: 1681:
F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681
Пример нахождения оптимального плана
(См. Пример нахождения опорного плана.)
Рассчитаем потенциалы пунктов отправки и пунктов доставки и . Для этого составьте систему для заполненных клеток плана перевозок: .Решим данную систему, полагая =0.
2. Вычислим коэффициенты изменения стоимости для незаполненных клеток плана: ci,j’ = ui + vj - ci,j.
Таблица 2
Поставщики и их ресурсы | Потребители и их спрос | ||||||||||||||||||||||||
|
|
|
| ||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
|
|
|
|
| -4 | ||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
Стоимость перевозок по данному плану составляет: 1681.
F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681
Получим потенциалы и .. Рассчитаем коэффициенты изменения стоимости перевозок.
Составим цикл пересчета: Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6]. Количество единиц изменения плана: 6. Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2. Получим следующий план перевозок (Табл.3).
Таблица 3.
Поставщики и их ресурсы | Потребители и их спрос | ||||||||||||||||||||||||
|
|
|
| ||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
|
|
|
|
| -10 | ||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
Стоимость перевозок по данному плану составляет: 1645.
F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *6 + 30 *0 +25*20 + 21 *17 =1645
Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20]. Количество единиц изменения плана: 20
Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3. Получим следующий план перевозок (Табл.4).
Таблица 4.
Поставщики и их ресурсы | Потребители и их спрос | ||||||||||||||||||||||||
|
|
|
| ||||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
|
|
|
|
| -6 | ||||||||||||||||||||
|
|
|
|
| |||||||||||||||||||||
Стоимость перевозок по данному плану составляет: 1565.
F=14 *7 + 28* 0 + 21*20 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *26 + 30 *0 +25*0 + 21 *17 =1565
Получим потенциалы и . Рассчитаем коэффициенты изменения стоимости перевозок. Потенциалы и коэффициенты указаны в таблице 4. Полученный план оптимальный, т.к. все коэффициенты изменения стоимости отрицательны или равны нулю.
Решение транспортной задачи средствами EXCEL
Анализ оптимального решения на чувствительность в Excel
Для проведения анализа полученного решения на чувствительность необходимо после запуска в Excel задачи на решениев окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты"и"Устойчивость".
Отчет по результатам
Отчет по результатам состоит из трех таблиц:
· таблица 1 содержит информацию о ЦФ;
· таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;
· таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.