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

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

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

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

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

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

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

Воронеж 2008

Задача №1

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

Задание:

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

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

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

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

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

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

Решение:

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

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

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

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

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

V_j – U_i ≤ C_ij для х_ij = 0; (1)

V_j – U_i = C_ij для d_ij > х_ij > 0; (2)

V_j – U_i ≥ C_ij для х_ij = d_ij; (3)

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

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

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

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

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

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

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

V_j = U_i + C_ij;

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

U_i = V_j – C_ij.

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

х_ул = min [х_{ij четн}, (d_ij – х_ij)_нечетн]

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

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