Пусть в имеется однородный груз в количествах . Его необходимо перевезти в пункты в количествах , так чтобы стоимость перевозок была min.
При этом предлагается, что количество требуемого груза равно имеющимся запасам, т.е. , когда суммарное количество груза равно суммарным потребностям, то это закрытая модель транспортной задачи.
Если условие не выполняется, то модель открытая.
- количество перевозимого груза из в .
- стоимость перевозки одного груза.
Количество груза, отправленного из на все пункты назначения должно равняться имеющимся запасам :
. Количество груза, пребываемого в
Тогда линейная функция определяет полную стоимость
А система ограничений:
1. , - количество груза отправляемого из =имеющемуся запасу
2., - количество груза, пребываемого в =потребности .
Пункты отправл.
Пункты назначения
Тонн товара
В1
В2
В3
А1
с11 х11
с12 х12
с13 х13
12
А2
с21 х21
с22 х22
с23 х23
15
8
9
10
Теорема:
Транспортная задача в закрытой форме имеет решение всегда будет строиться опорный план для которого целевая функция достигает свой минимум или максимум.
Количество неизвестных l*r, количество уравнений в системе .
Возьмем конкретную задачу.
Две автобазы обслуживают 3 магазина.
С 1 – ой вывезти 12 т. товара.
Со 2 – ой вывезти 15 т. товара.
В 1 – ый магазин нужно доставить 8 т. товара.
Во 2 – ой магазин нужно доставить 9 т. товара.
В 3 – ий магазин нужно доставить 10 т. товара.
Стоимость перевозки:
с 1 –ой базы в 1 – ый магазин составляет 0,8.
с 1 –ой базы во 2 – ой магазин составляет 1,1.
с 1 –ой базы в 3 – ий магазин составляет 0,9.
со 2 –ой базы в 1 – ый магазин составляет 1,0.
со 2 –ой базы во 2 – ой магазин составляет 0,7.
со 2 –ой базы в 3 – ий магазин составляет 1,2.
Наличие товара на базах:
,
Целевая функция:
Задача: Минимизировать целевую функцию.
Первая часть решения будет заключаться в построении опорного плана.
Построение первоначального опорного плана.
Система ограничений содержит неизвестных и уравнений, связанных условием замкнутости. Эти уравнений являются линейно зависимыми. Исключаем одно из одинаковых уравнений, получаем систему линейно независимых уравнений и невырожденный опорный план будет содержать положительную компоненту.
Если условия транспортной задачи выполняются и опорный план записан таблицу, то клетки в которых находятся отличные от 0 перевозки называются занятыми, а остальные незанятые. Занятые клетки соответствуют базисным неизвестным и для невырожденного плана их количество .
Опорность плана при записи условия транспортной задачи в виде таблицы заключается в его ацикличности (отсутствие цикла), т.е. в таблице нельзя построить замкнутый цикл, все вершины которого лежат в занятых клетках.
ОПР: Циклом называется набор клеток, в котором две и только две клетки расположены только в одном столбце и строке таблицы, причем последняя клетка расположена в том же столбце или той же строке что и первая.
Построение цикла в зависимости от задачи начинается с занятой (свободной) клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот под прямым углом и движутся по строке (столбцу) к следующей занятой клетке, пытаясь веруться к первоначальной клетке. Если такой возврат возможен, то план не является опорным.
Способы построения опорного плана:
1. Метод северо – западного угла;
2. Метод минимальной стоимости;
3. Метод двойного предпочтения.
Метод северо – западного угла.
Построение цикла начинается с левой верхней клетки.
Построим опорный план.
В1
В2
В3
А1
8 0,8
4 1,1
- 0,9
12
А2
- 1,0
5 0,7
10 1,2
15
8
9
10
Цикла нет ацикличность имеет опорный невырожденный план
Посчитаем Z=8*0.8+5*0.7+4*1.1+10*1.2=26.3.
