Сделай Сам Свою Работу на 5
 

По критерию стоимости в матричной форме.

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

 

Вопрос 21, 22. Постановка транспортной задачи

по критерию стоимости в матричной форме.

 

Рассмотрим простейший вариант модели транспортной задачи (ТЗ), когда речь идет о рациональной перевозке некоторого однородного продукта от производителя к потребителям; при этом имеется баланс между суммарным спросом потребителей и возможностями поставщиков по их удовлетворению. Причем потребителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были полностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рацио-нальном прикреплении, правильном направлении перевозок грузов, при котором потреб-ности полностью удовлетворяются, вся продукция от поставщиков вывозиться, а затраты на транспортировку минимальны.

Транспортную задачу можно сформулировать следующим образом, представив ее в виде таблицы, которую называют распределительной. Распределительную таблицу назы-вают иногда табличнойили матричной моделью ТЗ.

 

  Поставщики Потребители Запас груза, ai
B1 B2 Bn
A1 c11 x11 c12 x12   … c1n x1n a1
A2 c12 x12 c22 x22   … c2n x2n a2
Am cm1 xm1 cm2 xm2   … cmn xmn am
Потребность в грузе, bj b1 b2 bn  

 

В m пунктах отправления A1, …, Am сосредоточен однородный груз в количествах соответственно a1, …, am единиц. Имеющийся груз необходимо доставить потребителям B1, …, Bn, спрос которых выражается величинами b1, …, bn единиц. Известна стоимость cij перевозки единицы груза из i-го пункта отправления в j пункт назначения. Удельные транспортные издержки (расходы) записывают в форме матрицы , которую называют матрицей тарифов. Требуется спланировать перевозки, т.е. указать, сколько единиц груза должно быть отправлено от i-го поставщика j-му потребителю, так, чтобы максимально удовлетворить спрос потребителей и чтобы суммарные транспортные затраты на перевозки были при этом минимальными. Рассмотрим простейший случай, когда суммарные запасы поставщиков равны суммарным потребностям



Для составления математической модели задачи введем переменные xij , обозначающие количество единиц груза, которые необходимо доставить из i-го пункта отправления в j-й пункт назначения. Все эти переменные можно записать в виде матрицы , которая будет называться матрицей перевозок:

.

Цель транспортной задачи – минимизировать общие затраты на реализацию плана перевозок, которые можно представить целевой функцией:

. (17.1.1.)

Переменные должны удовлетворять следующим условиям:

1) ограничения по запасам:

(17.1.2.)

2) ограничения по потребностям:

(17.1.3.)

3) условия неотрицательности:

xij ³0 . (17.1.4.)

где cij – стоимость перевозки единицы груза из i-го пункта отправления в j пункт назначения;

- количество груза, сосредоточенного в пункте ;

- количество груза, необходимое для доставки потребителю .

Если план перевозок удовлетворяет ограничениям (17.1.2) – (17.1.4.), то такой план называется допустимым. Допустимый план перевозок, доставляющий минимум целевой функции называется оптимальным. В следующей теореме, которую примем без доказательства, введем критерий существования допустимого плана.

Теорема 17.1. (о существовании допустимого плана).

Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно выпол-нение равенства

(17.1.5.)

 

Модель ТЗ называется закрытой, если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство

.

Если для ТЗ выполняется одно из условий:

или ,

то модель задачи называется открытой.

Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закры-тую. Так, при выполнении условия необходимо ввести фиктивный -й пункт назначения , т.е. в матрице задачи предусматривается дополнительный столбец. Спрос фиктивного потребителя полагают равным небалансу, т.е. , а все тарифы – одинаковыми, чаще всего равными нулю .

Аналогично при выполнении условия вводится фиктивный поставщик , у которого запас груза равен , а тарифы дополнительной строки распределительной таблицы равны нулю, т.е. .

При преобразовании открытой задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.

 

 

Вопрос 23. Построение исходного опорного плана.

 

Построение опорных планов, а также преобразование их проводят непосредственно в распределительной таблице. Если в плане перевозок переменная равна некоторому числу , то это число записывают в соответствующую клетку и считают ее занятой (или базисной), если же , то клетку оставляют свободной. При этом число занятых клеток должно быть равно , а остальные клеток будут свободными.

Для построения начального опорного плана в распределительной таблице исполь-зуют такие правила и методы, как правило «северно-западного угла», правило «мини-мального элемента», метод Фогеля.

Существует несколько методов составления исходного опорного плана. Самый простой из них – метод «северо-западного угла». Исходные данные примера (затраты на перевозку единицы продукции от каждого поставщики к каждому потребителю) приведены в верхних правых углах таблицы 2.5.1.

Таблица 2.5.1

Опорный план решения транспортной задачи, составленный методом «северо-западного угла»  
Запасы поставщиков Потребности потребителей  
B1=100 B2=200 B3=50 B4=252 B5=77  
A1=127  
       
A2=152  
         
A3=225  
     
A4=175  
       

 

Метод наименьшего элемента состоит в заполнении клеток, начиная с тех, в которых стоят наименьшие затраты на перевозку (см. табл. 2.5.1). В данном случае минимальную стоимость имеют перевозки по каналу А42 – 8 у.д.е. Ставим в эту клетку максимально возможное количество перевозок – 175 (т.к. возможности А4=175). Следующие по затратам на перевозку каналы А45 и А44. Однако, возможности А4 уже исчерпаны, поэтому далее заполняется клетка, соответствующая каналу А24, в которую ставим 152 единицы груза (А2=152). Далее заполняем клетку А22. Сюда можно поставить только 25, т.к. второму потребителю требуется 200, а 175 он уже получает от А4.

Следующие по затратам перевозки по каналу А24 – 11 у.д.е. В эту клетку можно поставить только 127 единиц продукции, т.к. А2=152, а он уже поставил 25 единиц потребителю В2.

Канал А25 и А32 не рассматриваем, т.к. возможности А2 уже исчерпаны, а потребности В2 полностью удовлетворены. Поэтому затем заполняется клетка, соответствующая каналу А33(затраты на перевозку – 42 у.д.е.)

В дальнейшем транспортная таблица заполняется аналогично.

 



©2015- 2023 stydopedia.ru Все материалы защищены законодательством РФ.