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

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

Постановка транспортной задачи

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Общая постановка транспортной задачи состоит в определении оптимального плана…

Выбор критерия оптимальности

1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки… 2) Тарифная плата за перевозку груза (критерий - тарифы провозных плат).… 3) Эксплутационные расходы на транспортировку грузов (критерий - себестоимость эксплутационных расходов). Более верно…

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(6)

При данном плане перевозок общая стоимость перевозок составит

(7)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (6), при котором целевая функция (7) принимает минимальное значение.

Решение транспортной задачи

1. Найти начальный допустимый план. 2. Выбрать из небазисных переменных ту, которая будет вводиться в базис. Если… 3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2.

Построение допустимого (опорного) плана в транспортной задаче

Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла. Суть метода состоит в последова­тельном… аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1)= 0 или bj(q+1)= 0. Если справедливо первое,…

Пример нахождения опорного плана

Поставщики	Потребители и их спрос	Мощность поставщиков

 

F=14 x₁₁ + 28 x₁₂ + 21 x₁₃ + 28 x₁₄ + 10 x₂₁ + 17 x ₂₂ + 15 x₂₃ + 24 x₂₄ + 14 x₃₁ + 30 x₃₂ +25 x₃₃ + 21 x₃₄

 

Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).

Таблица 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

Нахождение оптимального решения

Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он… Алгоритм нахождения решения транспортной задачи этим методом основан на…  

Выбор небазисной переменной, которая будет вводиться в базис.

если (где cij - стоимость перевозки из пункта i в пункт j) (8) Поскольку система (8) содержит уравнений и m+n неизвестных, то одну из них… Если оказалось, что все ci,j’ отрицательны, то план оп­тимален. Если же хотя бы в одной свободной клетке ci,j’ > 0,…

Выбор переменной, которая будет выводиться из базиса.

Цикл пересчета представляет собой замкнутую ломаную линию состоящую из горизонтальных и вертикальных линий, концы которых лежат в заполненных… Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не… Процесс улучшения плана продолжается до тех пор, пока не будет получен план, в котором все ci,j’ отрицательны.

Пример нахождения оптимального плана

(См. Пример нахождения опорного плана.)

Рассчитаем потенциалы пунктов отправки и пунктов доставки и . Для этого составьте систему для заполненных клеток плана перевозок: .Решим данную систему, полагая =0.

2. Вычислим коэффициенты изменения стоимости для незаполненных клеток плана: c_i,j’ = u_{i +} v_j - c_i,j.

Таблица 2

Поставщики и их ресурсы	Потребители и их спрос
B1	B2	B3	B4
A1		-7	-2	-13
A2	[-6]		[+6]	-13	-4
A3	[+6]	-3	[-6]

 

Стоимость перевозок по данному плану составляет: 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.

Поставщики и их ресурсы	Потребители и их спрос
B1	B2	B3	B4
A1	[-20]	-1	[+20]	-7
A2	-6			-13	-10
A3	[+20]	-3	[-20]

 

Стоимость перевозок по данному плану составляет: 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.

Поставщики и их ресурсы	Потребители и их спрос
B1	B2	B3	B4
A1		-5		-7
A2	-2			-9	-6
A3		-7	-4

 

Стоимость перевозок по данному плану составляет: 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

Если такой команды в меню нет, то необходимо выполнить команду Сервис/Надстройки и установить Поиск решения. После выполнения команды появится окно:  

Анализ оптимального решения на чувствительность в Excel

Для проведения анализа полученного решения на чувствительность необходимо после запуска в Excel задачи на решениев окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты"и"Устойчивость".

Отчет по результатам

Отчет по результатам состоит из трех таблиц:

· таблица 1 содержит информацию о ЦФ;

· таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;

· таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Отчет по устойчивости

  Таблица 1 содержит информацию, относящуюся к переменным: