Файл: Решение задачи Составим матрицу.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.11.2023

Просмотров: 14

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.



Исходные данные

Вариант 1

№ варианта
Объем производства, тыс.ед. (ai)
Объем потребления, тыс.ед. (bi)

1
2
3
4
5
1
2
3
4
5

1
100
150
260
80
-
125
105
70
60
140


Решение задачи

Составим матрицу.

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

Поставщики



Потребители
Объем производства

В1
В2
В3
В4
В5
В6

А1
2,8
2,2
1,7
2,0
2,1
0
100

А2
3,1
1,9
3,3
1,8
2,3
0
150

А3
3,9
2,1
3,4
3,0
2.,7
0
260

А4
2,7
2,3
3,2
2,5
2,4
0
80

А5
2,1
1,8
3,5
2,7
2,8
0
-

Объем потребления

125
105
70
60

140
90
590

590


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

  1. Метод северо-западного угла. Сущность этого метода заключается в том, что начинают удовлетворять потребности первого потребителя В1 за счет запаса поставщика А1. Если потребность не удовлетворена, то недостающее количества продукта поставляют от поставщика А2. Если потребности потребителя В1 удовлетворены полностью, остаток продукции поставщика А1 направляют потребителю В2. При неполном удовлетворении потребностей потребителя В2 недостающее количество продукта поставляется от поставщика А2. Если после этого у поставщика А2 остались излишки, они направляются потребителю В3. И т.д.

Таблица 2 – Матрица планирования, полученная методом северо-западного угла

Поставщик
Потребитель
Запас

B 1
B 2
B 3
B 4
B 5
В6

A 1
100
-
-
-
-
-
0
100

  
2,8  
  
2,2 
  
1,7  



2  
  
2,1 

A 2
25
105
20
-
-
-
0
150

  
3,1  
  
1,9 
  
3,3  



1,8  
  
2,3 

A 3
-
-
50
60
140
10
0
260

  
3,9 
  
2,1  
  
3,4 



3,0 
  
2,7  

A 4
-
-
-
-
-
80
0
80

  
2,7  
  
2,3
  
3,2 



2,5  
  
2,4  

A 5
-
-
-
-
-
-
0
-

  
2,1 
  
1,8 
  
3,5 
  
2,7  
  
2,8  

Потребность
125
105
70
60

140
90
590


Общая стоимость перевозок по составленному плану:

Z=100*2,8+25*3,1+105*1,9+20*3,3+50*3,4+60*3,0+140*2,7 =1351(ед. стоимости).

  1. Метод минимальной стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел аi или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходовали, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.


Таблица 3 – Матрица планирования, полученная методом минимальной стоимости.

Поставщик
Потребитель
Запас

B 1
B 2
B 3
B 4
B 5
В6

A 1
5
95
-
-
-
-
0
100

  
2,8  
  
2,2 
  
1,7  



2  
  
2,1 

A 2



10
50
-
-
90
0
150

  
3,1  
  
1,9 
  
3,3  



1,8  
  
2,3 

A 3
120
-
-
-
140


0
260

  
3,9 
  
2,1  
  
3,4 



3,0 
  
2,7  

A 4
-
-
20
60
-

0
80

  
2,7  
  
2,3
  
3,2 



2,5  
  
2,4  

A 5
-
-
-
-
-
-
0
-

  
2,1 
  
1,8 
  
3,5 
  
2,7  
  
2,8  

Потребность
125
105
70
60

140
90
590


Стоимость полученного плана перевозок будет следующей:

 = 5*2,8+120*3,9+95*2,2+10*1,9+50*3,3+20*3,2+60*2,5+140*2,7 =1467 (ед. стоимости)


  1. Метод двойного предпочтения. Суть метода заключается в том, что в каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объёмы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости. Этот метод использован при разработке плана перевозок в таблице 4.


Таблица 4 - Матрица планирования, полученная методом двойного предпочтения


Поставщик
Потребитель
Запас

B 1
B 2
B 3
B 4
B 5
В6

A 1



10
-
-
-
90
vv 0
100

  
2,8  
  vv
2,2 
  
1,7  



2  
  
2,1 

A 2
55
95



-
-


0
150

  v
3,1  
  v
1,9 
  
3,3  



1,8  
  
2,3 

A 3
70
-
50
-
140


0
260

  v
3,9 
  
2,1  
  v
3,4 



3,0 
  
2,7  

A 4
-
-
20
60
-

0
80

  
2,7  
  
2,3
  vv
3,2 
v
2,5  
  
2,4  

A 5
-
-
-
-
-
-
0
-

  
2,1 
  
1,8 
  
3,5 
  
2,7  
  
2,8  

Потребность
125
105
70
60

140
90
590

Стоимость перевозок по этому плану следующая:

Z = 55*3,1+70*3,9+10*2,2+95*1,9+50*3,4+20*3,2+60*2,5+140*2,7 = 1408 (ед. стоимости)

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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
v1=14
v2=8
v3=9
v4=10
v5=13
v6=16

u1=0
14
8
9
10
11
12

u2=-4
10
4
6
9
5
8

u3=-6
8
12
13
15
11
10

u4=-11
3
8
16
7
2
4

u5=-11
11
9
10
12
7
5


Опорный план является оптимальным, так как не существуют оценки свободных клеток, для которых ui + vj > cij

Выбираем максимальную оценку свободной клетки

Для этого в перспективную клетку поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1
2
3
4
5
6
Запасы

1
14
8
9
10
11
12
100

2
10
4
6
9
5
8
150

3
8
12
13
15
11
10
260

4
3
8
16
7
2
4
80

5
11
9
10
12
7
5
-

Потребности
125
105
70
60

140
90
590


Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Смотрите также файлы