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

Задача №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–й строки

--> ЧИТАТЬ ПОЛНОСТЬЮ <--