Экономико-математическое моделирование

Вариант 97(13)

Контрольная работа №1

  Вариант 97

Задача  №1

1. Построить оптимальный план перевозок каменного угля с 5 станций до 9-ти крупных потребителей, имеющих подъездные пути .
2. Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

Запишем условие задачи в матричной  форме. В строке A_i указываем размер ресурсов у отправителей, а в столбце B_j – размер потребностей у получателей. В верхнем правом углу каждой клетки значение C_ij – критерия оптимальности перевозки грузов от i поставщика к j потребителю. C_ij означает расстояние перевозки от i поставщика до j потребителя. Размер всех ресурсов у отправителей равен общей потребности получателей. Если клетка имеет ограничение пропускной способности, то в левом верхнем углу клетки указывается число d_ij.

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

В исходную матрицу для решения  задачи запишем значения ресурсов и  потребностей грузов и построим начальный  план методом северо-западного угла.

Ai	Bj
	B1		B2		B3		B4		B5		B6		B7		B8		B9		Ui
	165		105		85		95		75		115		90		125		145
A1		90		30		100		110		150	30	50		60		80		90
150	150
A2		10		40		45		50		25		70	30	15		30	10	30
160	15		105		40
A3	10	20		35		80		160		90		80		70		40		60
400					45		95		75		115		70
A4		50		5		40		30		120		40		75		30	40	20
150													20		90		40
A5		15	15	25		10	20	35		25		80		20		70		90
140															35		105
Vj

 Объем работы по перевозке  грузов в тонно-километрах для  данного плана 73750 ед.

Число базисных клеток начального плана равно  , где m – число строк, а n – число столбцов. K=5+9-1=13. Число базисных клеток начального плана равно 13, что совпадает с рассчитанным по формуле. Клетка C₄₉ не является базисной.

Оптимальный план перевозок на заданной матрице найдем методом потенциалов последовательного улучшения начального плана.

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

Такой строкой  является А₃. Тогда потенциал U₃=100.

Рассчитаем  остальные потенциалы по формулам: для j-го столбца  ; для i-той строки .

V₃=U₃+C₃₃=100+80=180;

V₄=U₃+C₃₄=100+160=260;

V₅=U₃+C₃₅=100+90=190;

V₆=U₃+C₃₆=100+80=180;

V₇=U₃+C₃₇=100+70=170;

U₂=V₃-C₂₃=180-45=135;

V₂=U₂+C₂₂=135+40=175;

V₁=U₂+C₂₁=135+10=145;

U₁=V₁-C₁₁=145-90=55;

U₄=V₇-C₄₇=170-75=95;

V₈=U₄+C₄₈=95+30=125;

U₅=V₈-C₅₈=125-70=55;

V₉=U₅+C₅₉=55+90=145.

Проверим условия оптимальности:

V_j – потенциал j-го столбца; U_i – потенциал i-той строки; С_ij – расстояние перевозки от i-го поставщика до j-го потребителя; x_ij – корреспонденция (размеры перевозок) от i-го поставщика до j-го потребителя; d_ij – величина пропускной способности ij клетки.

Для  удобства запишем расчеты  в таблицу:

	V1	V2	V3	V4	V5	V6	V7	V8	V9			V1	V2	V3	V4	V5	V6	V7	V8	V9
U1	90	120	125	205	135	125	115	70	90		U1	90	30	100	110	150	50	60	80	90
U2	10	40	45	125	55	45	35	-10	10		U2	10	40	45	50	25	70	15	30	30
U3	45	75	80	160	90	80	70	25	45		U3	20	35	80	160	90	80	70	40	60
U4	50	80	85	165	95	85	75	30	50		U4	50	5	40	30	120	40	75	30	20
U5	90	120	125	205	135	125	115	70	90		U5	15	25	10	35	25	80	20	70	90

   

Нарушения условий есть в ячейках х₁₂, х₁₃, х₁₄, х₁₇, х₁₆, х₂₄, х₂₅, х₂₇, х₃₁, х₃₂, х₄₂, х₄₃, х₄₄, х₄₆, х₅₁, х₅₂, х₅₃, х₅₄, х₅₅, х₅₆, х₅₇.

Максимальное нарушение в клетке х₅₄=205-35=170. Для этой клетки строим замкнутый контур, в который входят только базисные клетки и клетка с нарушением. Из клетки х₅₄ проводим ломаную линию, заканчивающуюся в той же клетке, направление движения при этом изменяется под прямым углом только в базисных клетках. Клетка с нарушением имеет №1, корреспонденцию улучшения плана находим из следующего выражения: . На эту величину изменяются все корреспонденции контура, начиная с клетки с нарушением: уменьшаются корреспонденции, записанные в четных клетках, и увеличиваются корреспонденции, записанные в нечетных клетках контура.

Контур для улучшения плана: х₅₄→х₃₄→х₃₇→х₄₇→х₄₈→х₅₈→х₅₄. 

х_ул=min[х₃₄=95, х₄₇=85, х₅₈=35; х₅₄=20, ∞, ∞]=20.

х₅₄=0+20=20; х₃₄=95-20=75; х₃₇=70+20=90; х₄₇=20-20=0; х₄₈=90+20=110; х₅₈=35-20=15. Строим новую матрицу перевозок.

Продолжая расчеты, получим матрицу  оптимального плана перевозок:

Ai	Bj
	B1	B2	B3	B4	B5	B6	B7	B8	B9	Ui
A1	0	30	0	0	0	30	90	0	0	150
A2	155	0	0	0	5	0	0	0	0	160
A3	10	75	0	0	15	30	0	125	145	400
A4	0	0	0	95	0	55	0	0	0	150
A5	0	0	85	0	55	0	0	0	0	140
Vj	165	105	85	95	75	115	90	125	145

Объем работы по перевозке грузов в тонно-километрах для оптимального плана 37025 ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №2

Вариант №13

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

Целевая функция:

Ограничения:

Решение

Найдем  область допустимых решений. Она  является пересечением полуплоскостей, каждая из которых определяется одним  из неравенств ограничений. Для получения  каждой полуплоскости следует знак неравенства заменить на знак равенства.

При этом найдены  уравнения прямых – границ полуплоскостей. Каждая прямая разбивает плоскость  на две полуплоскости. Искомую полуплоскость  отмечают в соответствии со смыслом  неравенства.

Прямые  строим по точкам.

: координаты первой точки х₁=5, х₂=1; координаты второй точки х₁=4, х₂=5.

: координаты первой точки  х₁=6, х₂=4; координаты второй точки х₁=5, х₂=6.

: координаты первой точки  х₁=3, х₂=0; координаты второй точки х₁=0, х₂=6.

: координаты первой точки  х₁=0, х₂=-1; координаты второй точки х₁=1, х₂=0.

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

Система неравенств противоречива. Задача не имеет решений.

 

Задача №3

Вариант № 13

Найти оптимальное значение функции  при заданной системе ограничений.

Целевая функция: .

Ограничения: .

Решение.

Перейдем  от ограничений типа неравенств к  ограничениям типа равенств.

Для этого  перенесем все члены из меньших частей неравенств в большие и обозначим их новыми неотрицательными переменными и . Ограничения типа равенства оставим без изменений. Новые переменные введем также в целевую функцию с коэффициентами, равными 0. Получим основную задачу линейного программирования.

Ограничения: .

Целевая функция: .

Найдем  вид канонической задачи линейного  программирования. Для этого выразим  базисные неизвестные через свободные. Число базисных неизвестных равно числу ограничений, остальные переменные – свободные. Получим:

Выразим целевую  функцию через свободные неизвестные.

При этом при  нулевых значениях свободных  неизвестных базисные положительны.

Для уменьшения целевой функции следует увеличивать  переменную х₂. В первом ограничении можно увеличивать переменную до 15, во втором – до в третьем – до 20.

Выразим х₂ из второго ограничения и подставим в первое и третье, а также в выражение для целевой функции.

Получим:

В выражение для целевой функции  обе переменных входят с положительными коэффициентами. Поэтому можно утверждать, что найден оптимальный план: х₃=х₄=0. Остальные неизвестные: х₁=16,667, х₃=6,667, х₅=13,333.

Оптимальное значение функции  равно 23,333.

 

 

 

 

 

 

 

Контрольная работа №2

Задача №1

Вариант №9

Требуется найти оптимальную трассу участка железнодорожного пути между пунктами А и В, из которых второй лежит к северо-востоку от первого. Местность, по которой пройдет магистраль, является пересеченной и включает лесистые зоны, холмы, болота, реку. Поэтому стоимость строительства равных по длине участков пути может быть различной. Требуется так провести дорогу из пункта А в пункт В, чтобы суммарные затраты на сооружение участка были минимальными.

№5	13	№11	68	№17	10	№23	11	№29	13	№35	8	№41	10	В
12		9		11		13		10		7		15		10
№4	13	№10	10	№16	10	№22	12	№28	14	№34	8	№40	11	№46
10		12		12		13		8		9		13		11
№3	11	№9	13	№15	13	№21	14	№27	8	№33	10	№39	10	№45
9		12		15		9		10		10		12		15
№2	10	№8	11	№14	14	№20	10	№26	9	№32	8	№38	12	№44
14		9		29		11		14		12		10		10
№1	15	№7	12	№13	10	№19	88	№25	12	№31	10	№37	13	№43
12		9		10		13		10		11		9		13
А	13	№6	8	№12	8	№18	12	№24	13	№30	11	№36	10	№42