Задача - Транспортная задача - файл n1.docx

приобрести
Задача - Транспортная задача
скачать (105.4 kb.)
Доступные файлы (1):
n1.docx106kb.05.06.2012 06:41скачать

n1.docx

В пунктах выпускается однородная продукция в количестве , единиц. Себестоимость единицы продукции в пункте равна . Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость перевозки единицы продукции из пункта в пункт известна.

Требуется:

  1. Найти оптимальный план перевозок, который обеспечивает минимальные суммарные затраты на производство и доставку продукции;

  2. Составить экономико-математическую модель задачи;

  3. Найти величину минимальных затрат.

Все необходимые данные даны в таблице:























140

180

240

3

3

2

80

160

120

180

3























2

6

6

5

1

4

8

7

10

6

3

Решение.

Задача является открытой, так как запасы суммарный спрос меньше суммарного предложения: 140+180+240 = 560 > 540 = 80+160+120+180 единиц. Для того, чтобы привести задачу к закрытому типу, необходимо ввести фиктивного потребителя с потребностью в 560-540=20 единиц продукции. Стоимость перевозки в пункт потребления из всех пунктов производства считаем равным 0.

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



при ограничениях





и естественном условии неотрицательности количества поставляемой продукции



Математическая модель задачи выглядит следующим образом:









  1. Составим опорный план методом северо-западного угла.

Рассмотрим "северо-западный угол" незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю. Поставим туда наименьшее из значений 140 и 80, т.е 80. Тогда спрос первого потребителя будет удовлетворён, вычеркнем из дальнейшего рассмотрения первый столбец, а у первого поставщика осталось 140-80=60 единиц нераспределённой продукции. Далее рассматриваем "северо-западный угол" оставшейся таблицы, то есть клетку, соответствующую первому поставщику и второму потребителю, ставим туда наименьшее из значений 160 и 60, т.е. 60. Вся продукция первого поставщика распределена, значит вычёркиваем первый столбец, у второго потребителя потребность уменьшилась до 160-60=100. Аналогично продолжаем заполнять таблицу. После n+m-1 шагов получаем опорный план:




80

160

120

180

20

140

80

60

-

-

-

180

-

100

80

-

-

240

-

-

40

180

20



  1. Составим начальный опорный план методом наименьшего элемента. В правом верхнем углу каждой ячейки записываем



80

160

120

180

20

140




6




5




9




9




3

80










40










20




180




8




4




7




11




3







160




20
















240




9




12




8




5




2













60




180










Введем некоторые обозначения: Ai* - излишек нераспределенного груза от поставщика Ai, Bj* - недостача в поставке груза потребителю Bj.
Находим незанятую клетку с минимальным тарифом (рассматриваем нефиктивных потребителей): (2,2). Помещаем туда меньшее

из чисел A2*=180 и B2*=160. Спрос потребителя B2 удовлетворён (B2*=0), A2* стало равным 180-160=20.

Находим незанятую клетку с минимальным тарифом: (3,4). Помещаем туда меньшее

из чисел A3*=240 и B4*=180. Спрос потребителя B4 удовлетворён (B4*=0), A3* стало равным 240-180=60.

Находим незанятую клетку с минимальным тарифом: (1,1). Помещаем туда меньшее

из чисел A1*=140 и B1*=80. Спрос потребителя B1 удовлетворён (B1*=0), A1* стало равным 140-80=60.

Находим незанятую клетку с минимальным тарифом: (2,3). Помещаем туда меньшее

из чисел A2*=20 и B3*=120. Продукция пункта A2 распределена (A2*=0), B3* стало равным 120-20=100.

Находим незанятую клетку с минимальным тарифом: (3,3). Помещаем туда меньшее

из чисел A3*=60 и B3*=100. Продукция пункта A3 распределена (A3*=0), B3* стало равным 100-60=40.

Находим незанятую клетку с минимальным тарифом: (1,3). Помещаем туда меньшее из чисел A1*=60 и B3*=40. Спрос потребителя B3 удовлетворён (B3*=0), A1* стало равным 60-40=20.

Осталось распределить 20 единиц груза из пункта А1. Неудовлетворённым остался только спрос фиктивного потребителя – пункта В5. Помещаем туда 20, после чего вся продукция становится распределённой и спрос всех потребителей удовлетворён.
Таким образом, начальным опорным планом является



.

Проверим, является ли план, полученный методом наименьшего элемента, оптимальным, используя метод потенциалов. Так как m+n-1=5+3-1=7 и имеем 7 загруженных клеток, план является ацикличным.

Пусть Ui и Vj - потенциалы i-го склада и j-го магазина соответственно.

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=C'i,j,

просматривая все занятые клетки. Получим:

U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V3 = C'1,3 - U1 = 9 – 0 = 9

V5 = C'1,5 – U1 = 3 – 0 = 3

U2 = C'2,3 - V3 = 7 – 9 = -2

U3 = C'3,3 – V3 = 8 – 9 = -1

V2 = C'2,2 – U2 = 5 – (-1) = 6

V4 = C'3,4 – U3 = 5 – (-1) = 6

Для свободных клеток определим значения оценок (разностей между прямыми и

косвенными тарифами).

S1,2 = C'1,2 - (U1 + V2) = -1

S1,4 = C'1,4 - (U1 + V4) = 3

S2,1 = C'2,1 - (U2 + V1) = 4

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 2

S3,1 = C'3,1 - (U3 + V1) = 4

S3,2 = C'3,2 - (U3 + V2) = 7

S3,5 = C'3,5 - (U3 + V5) = 0

Имеем одну клетку с отрицательной оценкой – клетка (1,2). Строим для нее цикл так, чтобы он начинался и заканчивался в этой клетке, а остальными узлами были бы загруженные клетки таблицы.



80

160

120

180

20

140




6

+

5

-

9




9




3

80










40










20




180




8

-

4

+

7




11




3







160




20
















240




9




12




8




5




2













60




180










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

В результате перемещения по циклу получим новый план:



80

160

120

180

20

140




6




5




9




9




3

80




40
















20




180




8




4




7




11




3







120




60
















240




9




12




8




5




2













60




180










Целевая функция (суммарные транспортные расходы и расходы на производство по полученному плану)

. Значение целевой функции уменьшилось на 40 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V2 = C'1,2 - U1 = 5 – 0 = 5

V5 = C'1,5 – U1 = 3 – 0 = 3

U2 = C'2,2 – V2 = 4 – 5 = -1

V3 = C'2,3 – U2 = 7 – (-1) = 8

U3 = C'3,3 – V3 = 8 – 8 = 0

V4 = C'3,4 – U3 = 5 – 0 = 5

Для свободных клеток определим значения оценок

S1,3 = C'1,1 - (U1 + V1) = 3

S1,4 = C'1,4 - (U1 + V4) = 3

S2,1 = C'2,1 - (U2 + V1) = 3

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 1

S3,1 = C'3,1 - (U3 + V1) = 3

S3,2 = C'3,2 - (U3 + V2) = 7

S3,5 = C'3,5 - (U3 + V5) = -1

План не оптимален, так как имеется клетка с отрицательной оценкой – (3,5). Строим для нее цикл.



80

160

120

180

20

140




6

+

5




9




9

-

3

80




40
















20




180




8

-

4

+

7




11




3







120




60
















240




9




12

-

8




5

+

2













60




180










Перемещаем по циклу груз величиной в 20 единиц.

В результате перемещения по циклу следующий план:



80

160

120

180

20

140




6




5




9




9




3

80




60






















180




8




4




7




11




3







100




80
















240




9




12




8




5




2













40




180




20




Целевая функция (транспортные расходы)

. Значение целевой функции уменьшилось на 20 единиц по сравнению с предыдущим этапом.

Проверим полученный план на оптимальность. Подсчитаем потенциалы.

U1 = 0

V1 = C'1,1 – U1 = 6 - 0 = 6

V2 = C'1,2 - U1 = 5 – 0 = 5

U2 = C'2,2 – V2 = 4 – 5 = -1

V3 = C'2,3 – U2 = 7 – (-1) = 8

U3 = C'3,3 – V3 = 8 – 8 = 0

V4 = C'3,4 – U3 = 5 – 0 = 5

V5 = C'3,5 – U3 = 2 – 0 = 2

Для свободных клеток определим значения оценок

S1,3 = C'1,1 - (U1 + V1) = 1

S1,4 = C'1,4 - (U1 + V4) = 4

S1,5 = C'1,5 - (U1 + V5) = 1

S2,1 = C'2,1 - (U2 + V1) = 3

S2,4 = C'2,4 - (U2 + V4) = 7

S2,5 = C'2,5 - (U2 + V5) = 2

S3,1 = C'3,1 - (U3 + V1) = 3

S3,2 = C'3,2 - (U3 + V2) = 7

Так как все оценки Si,j>=0, то полученный план является оптимальным, минимальные

транспортные расходы равны 3000.

Как видим, опорный план, полученный методом северо-западного угла, оказался оптимальным.

Ответ: Оптимальный план перевозок представлен в таблице



80

160

120

180

20

140




6




5




9




9




3

80




60






















180




8




4




7




11




3







100




80
















240




9




12




8




5




2













40




180




20





Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации