пользователей: 21252
предметов: 10461
вопросов: 177855
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

49. Транспортная задача. Открытая и закрытая модели транспортной задачи. Методы решения транспортной задачи.

Пусть в  имеется однородный груз в количествах . Его необходимо перевезти в пункты  в количествах , так чтобы стоимость перевозок была 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.


12.06.2014; 22:54
хиты: 66
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь