РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
Факультет «Экономический»
Кафедра «Экономика, финансы иуправление на транспорте»
КОНТРОЛЬНАЯ РАБОТА
подисциплине: «ЭКОНОМИКО-МАТЕМАТИЧЕСКОЕМОДЕЛИРОВАНИЕ»
Воронеж 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> 0; (2)
Vj – Ui ? Cij для хij = dij; (3)
где Vj – потенциал j–го столбца;
Ui – потенциал i–й строки;
Cij – расстояние перевозки от i–го поставщика до j–го потребителя;
хij– корреспонденция (размеры перевозок)от 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
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
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
r = {60; 25; 100} = 25