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

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

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

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

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

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

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

Воронеж 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 на размер перевозок будет минимальной, т.е.

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

Любой допустимый план является оптимальным тогда и только тогда, когда каждой строке и каждому столбцу матрицы могут быть присвоены некоторые числа 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)_нечетн]

В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

В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	105
х	х
10	40	45	50	25	70	30 15	30	10 30
А2=160	125	35	165
х	х
10 20	35	80	160	90	80	70	40	60
А3=400	10	75	25	20	135	135	100
х	х	х	х	х
50	5	40	30	120	40	75	30	40 20
А4=150	95	55	140
х	х
15	15 25	10	20 35	25	80	20	70	90
А5=140	95	20	25	165
х	х
Vj	175	135	175	170	190	180	165	140	160

План оптимальный.

F(х) = 37925 – 20·25 = 37425 ден.ед.

Ответ: F(х)_нач. = 39700 ден.ед.; F(х)_опт. = 37425 ден.ед.

Задача №2

Графический метод решения задачи оптимизации производственных процессов

Задание: Решить задачу линейного программирования графическим методом. Исходные данные (вариант 7):

Целевая функция: f(x) = x₁ + 2x₂ → max,

Ограничения: –x₁ – x₂ ≥ –1, x₁– 2x₂ ≤ 1.

Решение:

–х₁ – х₂ ≥ –1

х₁ – 2х₂ ≤ 1 (–1)

х₁ ≥ 0; х₂ ≥ 0

х₁ + х₂ ≤ 1

2х₂ – х₁ ≥ 1

х₁ + х₂ = 1

х₁ = 1 – х₂

Если х₁ = 0, то х₂ = 1;

если х₂ = 0, то х₁ = 1.

х₁ – 2х₂ = 1

х₁ = 1 + 2х₂

Если х₁ = 0, то х₂ = –1/2;

если х₂ = 0, то х₁ = 1.

Строим прямые уравнений ограничений и находим область допустимых решений (рис. 1).

х₂ ≤ – х₁ +1 – нижняя полуплоскость;

2х₂ ≥ х₁ –1 – верхняя полуплоскость.

Рис. 1 - Решением системы неравенств является т. С (0;1)

Ответ: х₁= 0

х₂ = 1

Задача №3

Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством.

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

Целевая функция: f(x) = x₁ + 2x₂ –3х₃ → max.

Ограничения: x₁ + x₂ + х₃ = 25,

2x₁ – 3x₂ + 3х₃ ≥ 10;

x₁ – 3x₂ + 4х₃ ≤ 30.

Решение:

Т.к. дана задача на максимизацию целевой функции f, то она сводится к задаче на минимизацию функции –f.