Видеоурок по решению транспортной задачи в Excel с помощью надстройки поиск решения.

Ниже приведены условие задачи, текстовый отчет о решении и видеоурок. Закачка полного решения(документы  doc и xlsx в архиве zip) начнется автоматически через 10 секунд. 

 Условие:

Готовая продукция заводов ai (i=1-3) направляется на склады Bj (j=l-4). Заводы ai производят аi, тыс. изделий. Пропускная способность складов Bj за это время характеризуется величинами bj, тыс. изделий. Стоимость перевозки с завода ai, на склад Bj одной тысячи изделий равна Сij (ден.ед.).

 

с11

с12

с13

с14

а1

 

9

5

1

8

290

с21

с22

с23

с24

а2

=

1

2

4

3

210

с31

с32

с33

с34

а3

 

3

7

2

6

140

b1

b2

b3

b4

k

 

250

280

170

100

2

 

Требуется:

1) составить экономико-математическую модель задачи,  которая позволила бы найти план перевозки готовой продукции заводов на склады с минимальными затратами;

2)                 методом потенциалов найти оптимальный план перевозки готовой продукции на склады при дополнительном условии, что на складе Вк созданы лучшие условия для хранения готовой продукции, а поэтому он должен быть загружен полностью;

3)                 найти величину fmin минимальных транспортных затрат;

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

 

Решение:

1. Запишем начальные условия задачи в форме табл. 1.

Табл.1

Мощности заводов Аi, (шт)

Склады и их спрос

В1 (250 )

В2 ( 280 )

В3 (170  )

В4 (100 )

А1 ( 290)

 

9

X11

5

X12

1

X13

8

X14

А2 (210 )

 

1

X21

  2

X22

4

X23

3

X24

А3 (140)

 

3

X31

7

X32

2

X33

6

X34

Обозначим через Хij (i = 1,3; j = 1,4) количество  изделий, кото­рое планируется перевезти с завода Аi, на склад bj, а через f - общие транс­портные затраты.

Целевая функция задачи запишется в виде:

f=   9 • X11 +   5• X12 +...+  6•X34 (min)                          (3.1)

Сравнивая суммарную мощность заводов    290+210+140=640 с потребностью  

складов bj   250+280+170+100=800 , видим, что эти суммы не совпадают. Следовательно, данная транспортная задача обладает открытой моделью. Часть продукции ( 160 единиц) останется недопоставленной.

Переходя к ограничениям на переменные Хij, следует учесть, что ко­личество продукции, вывозимой из каждого завода Аi, не может превышать мощности производства на этом заводе, т.е.

X11 + X12 + X13+ X14 290

X21 + X22 + X23 + X24   210                                  (3.2)

 X31 + X32+ X33 + X34 140                                 

В то же время склады bj должны быть обеспечены полностью, т.е. сумма поставок, направляемых на каждый склад Bj со всех заводов Аi , должна равняться их потребности. Эти требо­вания можно выразить следующими равенствами:

X11 + X21 + X31 = 250

X12 + X22 + X32 = 280

 X13 + X23+ X33 = 170

X14 + X24+ X34  =  100                             (3.3)

Если исключить обратные перевозки, то должны выполняться условия

Хij  ≥0    (i=1,3; j=1,4)                                  (3.4)

Соотношения (3.1) - (3.4) образуют экономико-математическую модель рассматриваемой задачи.

Таким образом, математическая модель задачи: целевая функция (3.1), описывающая транспортные затраты, минимизируется при ограниче­ниях (3.2) - (3.4).

2. Введем в рассмотрение фиктивный завод Ас мощностью производства, равной небалансу, т.е.

800-640=160  изделий с одинаковыми затратами на перевозку, равными нулю: C4j= 0 (j=1,4).

Однако по условиям задачи необходимо найти оптимальный план задачи    при дополнительном условии, что склад  В2 должен быть загружен полностью. Это ограничение будет соблюде­но в том случае, если в заключительной таблице с оптимальным планом клетки (4; 2) останутся свободными. Чтобы добиться этого на время решения условно завысим показатель критерия оптимальности в клетках (4 ;2), например, до значения

(+100). Понятно, что теперь занимать клетки (4; 2) будет явно невыгодно.

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

Таблица 2

Мощности заводов Аi, (шт)

Склады и их спрос

 

В1 (250 )

В2 ( 280 )

В3 (170  )

В4 (100 )

Ui

А1 ( 290)

 

9

 

5

120

1

170

8

 

U1= 0

А2 (210 )

 

1

50

  2

160

4

 

3

 

U2= -3

А3 (140)

 

3

140

7

 

2

 

6

 

U3= -1

А4 (110)

 

0

60

+100

 

0

 

0

100

U4= -4

Vj

V1=4

V2=5

V3=1

V4=4

 
           

Построим исходный опорный план методом минимального элемента.

Для исследования плана на оптимальность необходимо найти оценки свободных клеток. Для этого надо знать потенциалы Ui и Vj заводов  Аi и складов bj, которые опреде­ляются в результате решения системы уравнений

 

U1 + V= 5

U1 + V3 = 1

U2+ V1 = 1                               (3.5)

U2+ V2 = 2

U3+ V1 = 3

U4+ V1 = 0

U4+ V3 = 0

 

 составленных по заполненным клеткам. Это неопределенная система, т.к. неизвестных на одно больше числа уравнений. Придадим одному из неизвестных определенное числовое значе­ние, например, U1= 0. Тогда остальные неизвестные находятся из системы (3.5): Получаем: U1= 0, U2 = -3, U3 = -1, U4 = -4,  V1 = 4, V2 =  5 ,V3 = 1 ,V4 = 4

Теперь можно найти оценки свободных клеток: S11= C11 - (U1 + V) =  9- (0-4) = 13   , S14=4, S23=6, S24=2, S32=3, S33=2, S34=3, S43=3.

 

Поскольку в табл. 2 свободных клеток с отрицательными оценками

нет, то опорный план является оптимальным. Итак,  получен  оптимальный

план:

 

 

0

120

170

0

X*=

50

160

0

0

 

140

0

0

0

 

 

 

 

 

 

 

 

 

3. Значение целевой функции - минимальные транспортные затраты -по оптимальному плану составляют:

fmin=   120·5 + 170·1 + 50·1 + 160·2 + 140·3 =1560 ден.ед.

 

4. Склад В1  недополучит   продукции  в размере 60 ед., склад В4  недополучит   продукции  в размере 100 ед..

 

Имя файла: TranspZ.zip

Размер файла: 25.72 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке