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

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

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

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

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

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

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

Воронеж 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, называемые потенциалами иотвечающие условиям:

Vj – Ui ≤ Cij для хij = 0; (1)

Vj – Ui = Cij для dij > хij<sub/>> 0; (2)

Vj – Ui ≥ Cij для хij = dij; (3)

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

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

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

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

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

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

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

Vj = Ui + Cij;

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

Ui = Vj – Cij.

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

хул = min [хijчетн, (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 – цикл подходит

r = {15; 45; 80; 20} =15

В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 30 ● 30 90 100 х 1+85 1+40 х 1+40 1+50 +10 40 45 50 – 25 70 30 15 30 10 30 А2=160 95 65 180 х 1+20 х 1+10 1+10 10 20 – 35 80 160 90 + 80 70 40 60 А3=400 10 105 15 135 135 180 х х х х 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 20 5 180 х х х

Vj

190 215 190 250 205 260 160 220 240

F(х) = 39700 – 90·15 = 38350 ден.ед.

30 – 90 + 10 – 25 + 25 –80 + 80 – 35 = – 85 < 0 – цикл подходит

r = {30; 65; 5; 105} = 5

В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 25 5 30 90 100 х х х + 10 40 45 50 – 25 70 30 15 30 10 30 А2=160 100 60 180 х х 10 20 – 35 80 160 + 90 80 70 40 60 А3=400 10 100 ● 20 135 135 95 х 1+15 1+20 х х х 50 5 40 30 120 40 75 30 40 20 А4=150 95 55 135 1+5 1+15 х х 15 15 25 10 20 35 25 80 20 70 90 А5=140 95 20 25 180 х х

Vj

190 130 190 165 205 175 160 135 155

F(х) = 38350 – 85·5 = 37925 ден.ед.

90 – 25 + 10 – 90 + 30 –35 = – 20 < 0 – цикл подходит

r = {60; 25; 100} = 25