Xreferat.com » Рефераты по математике » Транспортная задача линейного программирования

Транспортная задача линейного программирования

А1 (а1=50) 1,0 2,0 3,0 2,5 3,5 А2(а2=20) 0,4 3,0 1,0 2,0 3,0 А3(а3=75) 0,7 1,0 1,0 0,8 1,5 А4(а4=80) 1,2 2,0 2,0 1,5 2,5

В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу:

Транспортная задача линейного программирования Магазины

Склад

B1

(b1=40)

B2

(b2=50)

B3

(b3=15)

B4

(b4=75)

B5

(b5=40)

B6

(b6=5)

А1 (а1=50) 1,0 2,0 3,0 2,5 3,5 0
А2(а2=20) 0,4 3,0 1,0 2,0 3,0 0
А3(а3=75) 0,7 1,0 1,0 0,8 1,5 0
А4(а4=80) 1,2 2,0 2,0 1,5 2,5 0

Математическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда

Транспортная задача линейного программирования x11 x12 x13 x14 x15 x16

x21 x22 x23 x24 x25 x26

X = x31 x32 x33 x34 x35 x36 - матрица перевозок.

x41 x42 x43 x44 x45 x46

min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (1)

Транспортная задача линейного программированияx11+x12+x13+x14+x15+x16=50

x21+x22+x23+x24+x25+x26=20

x31+x32+x33+x34+x35+x36=75

x41+x42+x43+x44+x45+x46=80

x11+x21+x31+x41=40 (2)

x12+x22+x32+x42=50

x13+x23+x33+x43=15

x14+x24+x34+x44=75

x15+x25+x35+x45=40

x16+x26+x36+x46=5

xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3)

Двойственная ЗЛП:

max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (1*)

Транспортная задача линейного программирования

Транспортная задача линейного программированияu1+v1≤1

u1+v2≤2

u1+v3≤3 (2*)

u1+v4≤2,5

u1+v5≤3,5

u1+v6≤0

ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3*)

Будем искать первоначальный план по методу наименьшей стоимости:

1) x21=20 и 2-ую строку исключаем.2) x31=20 и 1-ый столбец исключаем.

3) x34=55 и 3-ю строку исключаем.4) x44=20 и 4-ый столбец исключаем.

5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0. 6) x43=150 и 3-ий столбец исключаем.7) x45=40 и 5-ый столбец исключаем.x46=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.

Транспортная задача линейного программирования Магазины

Склад

B1

(b1=40)

B2

(b2=50)

B3

(b3=15)

B4

(b4=75)

B5

(b5=40)

B6

(b6=5)

А1 (а1=50)

Транспортная задача линейного программирования1,0

Транспортная задача линейного программирования

Транспортная задача линейного программирования

50
2,0

Транспортная задача линейного программирования3,0

Транспортная задача линейного программирования2,5

Транспортная задача линейного программирования3,5

0
А2(а2=20)

Транспортная задача линейного программирования0,4

20

3,0 1,0 2,0 3,0 0
А3(а3=75)

Транспортная задача линейного программирования0,7

20

0
1,0

1,0

55
0,8

1,5 0
А4(а4=80) 1,2 2,0

15
2,0

20
1,5

40
2,5

5
0

Стоимость 1-ого плана:

D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положим u1=0,тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:

Транспортная задача линейного программирования Магазины

Склад

B1

(b1=40)

v1=1,7

B2

(b2=50)

v2=2

B3

(b3=15)

v3=2,3

B4

(b4=75)

v4=1,8

B5

(b5=40)

v5=2,8

B6

(b6=5)

v6=0,3

Транспортная задача линейного программирования

  0,7

А1 (а1=50)

U1=0

Транспортная задача линейного программированияТранспортная задача линейного программирования

0
1,0

Транспортная задача линейного программированияТранспортная задача линейного программирования

- 0,7
50
2,0

- 0,7
3,0

- 0,7
2,5

 0,3

3,5

0

0
А2(а2=20)

U2=-1,3

- 2,3
20
0,4

0
3,0

- 1,5
1,0

- 1,5
2,0

- 1
3,0

0

0
А3(а3=75)

U3=-1

Транспортная задача линейного программирования

0
0,7

Транспортная задача линейного программирования

20

Транспортная задача линейного программирования

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: