Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов (183509)

Посмотреть архив целиком

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

Факультет «Экономический»

Кафедра «Экономика, финансы и управление на транспорте»











КОНТРОЛЬНАЯ РАБОТА

по дисциплине: «ЭКОНОМИКО-МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ»












Воронеж 2008


Задача №1


Метод потенциалов для решения транспортной задачи в матричной форме с ограничениями пропускной способности.

Задание:

  1. Построить оптимальный план перевозок каменного угля с пяти станций Аi (i = 1,2,3,4,5), до девяти крупных потребителей, имеющих подъездные пути Вj (j = 1,2,…,9).

  2. Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

Исходные данные (вариант 67):

Данные о наличии ресурсов на пяти станциях отправления Аi приведены в таблице 1, данные о размерах прибытия груза Вj на девять станций назначения – в таблице 2.


Таблица 1 - Ресурсы станций отправления Аi (строки матрицы)

Номер станции отправления

Значение

А1

150

А2

160

А3

400

А4

150

А5

140

Итого:

1000


Таблица 2 - Объем потребности Вj получателя (столбцы матрицы)

Номер станции назначения

Значение

В1

135

В2

105

В3

95

В4

115

В5

85

В6

105

В7

90

В8

135

В9

135

Итого:

1000


Решение:

Расстояние перевозки от каждой i–й станции отправления до каждой j–й станции назначения указано в правом верхнем углу каждой клетки матрицы. В левом верхнем углу ряда клеток матрицы указаны ограничения пропускной способности.

Условием задачи установлено, что размер всех ресурсов у отправителей равен общей потребности получателей:



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



Первоначально строится начальный план базисного варианта способом наименьшего значения критерия.

Любой допустимый план является оптимальным тогда и только тогда, когда каждой строке и каждому столбцу матрицы могут быть присвоены некоторые числа Ui и Vj, называемые потенциалами и отвечающие условиям:


VjUiCij для хij = 0; (1)

VjUi = Cij для dij > хij > 0; (2)


VjUiCij для хij = dij; (3)


где Vj – потенциал j–го столбца;

Ui – потенциал i–й строки;

Cij – расстояние перевозки от i–го поставщика до j–го потребителя;

хij – корреспонденция (размеры перевозок) от i–го поставщика до j–го потребителя;

dij – величина пропускной способности ij клетки.

Присвоение потенциалов начинают со строки, в которой среди базисных клеток имеется максимальное расстояние. Этой строке можно присвоить любой положительный потенциал, например, 100. Затем, используя условие оптимальности (2), находят потенциалы остальных строк и столбцов по формулам:

для j–го столбца


Vj = Ui + Cij;


для i–й строки


Ui = VjCij.


Корреспонденция улучшения плана находится из следующего выражения:


хул = minij четн, (dij – хij)нечетн]



Вj

Аi

В1=135

В2=105

В3=95

В4=115

В5=85

В6=105

В7=90

В8=135

В9=135

Ui


90

30

100

110

150

30 50

+ 60

80

90

 

А1=150

45

 

 

 

 

30

75

 

 

100


х

 

 

1+40

 

 

х

 

 

 


+ 10

40

45

50

25

70

30 15

30

10 30

 

А2=160

80

 

 

 

80

 


 

 

180


х

 

 

1+20

х

1+10

 

 

 

 


10 20

35

80

160

90

+ 80

70

40

60

 

А3=400

10

105

 

 

 

15

135

135

90


 

х

1+20

 

1+25

1+90

х

х

х

 


50

5

40

30

120

40

75

30

40 20

 

А4=150

 

 

 

95

 

55

 

 

 

220


 

 

 

х

 

х

 

 

 

 


15

15 25

10

20 35

+ 25

80

20

70

90

 

А5=140

 

 

95

20

5

20

 

 

 

180


 

 

х

 

х

х

 

 

 

 


 

 

 

 

 

 

 

 

 

 

Vj

190

125

190

250

205

260

160

130

150

 

 

 

 

 

 

 

 

 

 

 

 


F(х) = 45·90 + 30·50 + 75·60 + 80·10 + 80·25 + 10·20 + 105·35 + 15·70 + 135·40 + 135·60 + 95·30 + 55·40 + 95·10 + 20·35 + 5·25 + 20·80 = 39700 ден. ед.

80 – 70 + 60 – 90 + 10 – 25 + 25 – 80 = – 90 < 0 – цикл подходит


Случайные файлы

Файл
312.doc
179736.rtf
123934.rtf
задача 26 (2).doc
132599.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.