Это задачи об оптимизации схем перевозок различных грузов и другие задачи, имеющие аналогичные математические модели.
Пример. Имеются 3 предприятия-поставщика, выпускающие однородную продукцию, которую надо отправить 4 потребителям. Такими поставщиками могут быть, например, лесопильные предприятия, снабжающие мебельные фабрики пиломатериалами. Предприятия –поставщики мы будем обозначать А1;А2;А3 а предприятия – потребители В1;В2;В3;В4 .
Известны запасы груза у каждого поставщика ,объёмы заявок каждого потребителя , а также стоимость перевозок единицы груза от каждого поставщика к каждому потребителю .
Требуется предложить оптимизационный план перевозок, т. е. Указать какое количество груза следует отправить от каждого поставщика каждому потребителю, так, чтобы стоимость всех перевозок была минимальна.
При этом должны выполняться следующие условия:
1. Все запасы груза от каждого поставщика должны быть вывезены полностью.
2. Заявки каждого потребителя должны быть удовлетворены полностью.
Исходные данные задачи сведем в таблицу 7.1, которая называется транспортной таблицей.
Табл.7.1
Поставщики
Запас груза
Потребители
В1
В2
В3
В4
А1
а1=40
А2
а2=30
А3
а3=50
Заявки
20
60
10
30
Числа, стоящие в правых верхних углах клеток табл.7.1 показывают, чему равна стоимость перевозки одной единицы груза от соответствующего поставщика к соответствующему потребителю. Например, цифра «2», стоящая в правом верхнем углу верхней клетки 1-го столбца таблицы, означает, что стоимость перевозки одной единицы груза от 1-го поставщика А1 к первому потребителю В1 равна 2 единицам.
Составим математическую модель задачи, которую будем решать по критерию минимума суммарной стоимости перевозки всех грузов.
Так как требуется определить, какое количество груза должно быть перевезено от каждого поставщика к каждому потребителю, в качестве элементов решения мы будем использовать двухиндексные переменные, первый индекс которых будет соответствовать номеру поставщика, а второй- номеру потребителя. Для первого поставщика соответствующие элементы решения будут иметь следующий смысл:
- количество груза перевозимого от 1-го поставщика к 1-му потребителю;
- количество груза перевозимого от 1-го поставщика к 2-му потребителю;
……………………………………………………………………………………….
- количество груза перевозимого от 1-го поставщика к 4-му потребителю.
У элементов решения относящихся к второму поставщику, первый индекс будет равен 2:
- количество груза перевозимого от 2-го поставщика к 1-му потребителю;
- количество груза перевозимого от 2-го поставщика к 2-му потребителю;
……………………………………………………………………………………….
- количество груза перевозимого от 2-го поставщика к 4-му потребителю,
А у относящихся к 3-му поставщику-«3».
Для большей наглядности элементы решения записываются в соответствующие клетки транспортно таблицы.
Найдем целевую функцию модели. Стоимость перевозки одной единицы груза от первого поставщика к первому потребителю равна 2-м единицам. Стоимость перевозки единиц груза будет в раз больше: 2. Стоимость перевозки от 1-го поставщика к 2-му потребителю будет равна 8, а к третьему и четвертому- 7и 4. Аналогичным образом можно найти затраты на перевозку груза и от остальных поставщиков а общие затраты на перевозку будут равны
2+8+7+4+9+1+6+3+10+12++11→max ( 7.1)
Выражение (7.1) является целевой функцией задачи. Составим ограничения по вывозу продукции от каждого поставщика. Первый поставщик должен отправить в адрес 1-го, 2-го, 3-го и 4-го потребителя соответственно , , и единиц груза, всего =40. Т. е. ограничение, обеспечивающее вывоз всего груза от 1-го поставщика будет иметь вид:
+ + + =40 (7.2)
Аналогичные ограничения можно записать для 2-го и 3-го поставщиков:
+ + + =30, (7.3)
+ + + =50, (7.4)
Запишем условие того, что полностью выполнена заявка 1-го потребителя. Это произойдет в том случае, если количество груза, полученного им от 1-го, 2-го и 3-го поставщиков в сумме будет равно 20:
++=20 (7.5)
Аналогичные выражения можно записать для каждого из 4-х поставщиков.
Для 2-го:
++=60 (7.6)
Для 3-го:
++=10 (7.7)
Для 4-го:
++=30 (7.8)
Отметим, что при формировании ограничений (7.2)- (7.4) для поставщиков суммируются элементы решения находящиеся в соответствующей строке табл.7.1,
А при формировании ограничений (7.5)-(7.8) для потребителей суммируются элементы решения находящиеся в соответствующем столбце. В модель, также необходимо включить тривиальные ограничений на неотрицательность элементов решения:
(7.9)
Где i- индекс поставщика, i=1,3
j - индекс потребителя, j=1,4
Выражения (7.1) - (7.9) образуют математическую модель транспортной задачи (сокращенно ТЗ). Видно, что транспортная задача описывается моделью линейного программирования и потому в принципе может быть решена, например, симплекс – методом. Однако благодаря её специфическому виду (все коэффициенты при переменных в ограничениях 7.2-7.8 равны 1), её можно решать и более простыми методами.
Математическая модель транспортной задачи в общем виде.
Рассмотрим математическую модель ТЗ в общем виде. Пусть имеется m поставщиков с запасами груза a1;a2…am и n потребителей с объёмами заявок b1;b2…bn. Известна стоимость перевозок единицы груза от i-го поставщика к j-му потребителю. Требуется определить сколько груза следует перевести от каждого поставщика к каждому потребителю так чтобы общая стоимость перевозки грузов была минимальна, все запасы груза от каждого поставщика полностью вывезены, а заявки каждого потребителя полностью удовлетворены. Предполагается, что суммарные запасы груза равны суммарным потребностям в нем:
(7.10)
Задачи, предполагающие выполнение этого условия называются закрытыми транспортными задачами.
Пусть – количество груза перевозимого от i-того поставщика к j потребителю. Требования вывести весь груз от каждого поставщика записывается в виде следующих m уравнений.
(7.11)
Или
(7.12)
Требования, обеспечивающие удовлетворение заявок всех потребителей реализуются в виде системы n уравнений:
(7.13)
Или (7.14)
Выражение для целевой функции задачи имеет следующий вид:
(7.15)
Совокупность выражений (7.12) - (7.15) – это математическая модель транспортной задачи.
Лекция 8
Решение транспортных задач, как и обычных ЗЛП осуществляется в 2 этапа.
На I-м этапе отыскивается опорное решение транспортной задачи, на II-м – это решение последовательно улучшается до получения оптимального решения.
,объёмы заявок каждого потребителя 
, а также стоимость перевозок единицы груза от каждого поставщика к каждому потребителю 
.
20
60
10
30
=40. Т. е. ограничение, обеспечивающее вывоз всего груза от 1-го поставщика будет иметь вид:
(7.9)
(7.10)
– количество груза перевозимого от i-того поставщика к j потребителю. Требования вывести весь груз от каждого поставщика записывается в виде следующих m уравнений.
(7.11)
(7.12)
(7.13)
(7.14)
(7.15)