Задача № 1

Решение

Запишем задачу в виде:

Строим область ограничений (1)-(4).

y

(2)

15

(1)

(3)

B C z_min

5

2 z_max

A

-15 z=0 0 1 2 5 x

-3

Область ограничений (1)-(4) строится следующим образом. Например, строим область, соответствующую неравенству (1). Числа, стоящие в знаменателях неравенства (1), есть длины отрезков, отсекаемых прямой (1) (при замене знака неравенства знаком равенства) на соответствующих осях координат. Далее рассматриваем, например, точку (0;0). При подстановке её координат в (1) в случае удовлетворения данного неравенства принимаем полуплоскость, отсекаемую прямой (1) от всей координатной плоскости, которой принадлежит точка (0;0). В противном случае принимаем другую полуплоскость.

Строим также прямую z=0 и нормальный к ней вектор , указывающий направление возрастания функции z. Перемещая z=0 в направлении , получаем, что последний раз эта прямая пересекает область ограничений в точке А(5;0). Поэтому:

Перемещая z=0 в противоположном направлении, получаем, что последний раз эта прямая пересекает область ограничений по отрезку ВС, причём точка В имеет координаты В(0;5). Находим координаты точки С:

Поэтому:

Задача № 2

Решение

Запишем задачу в канонической форме.

Вводим дополнительные переменные . Тогда получим:

Решим полученную задачу симплекс-методом. Здесь переменные - базисные, остальные – свободные. Разрешающий столбец выбирается по элементу Δ-строки, который имеет максимальное положительное значение. Элементы θ-столбца есть частное от деления элемента столбца b(i) на соответствующий элемент разрешающего столбца, причём рассматриваются только строго положительные элементы разрешающего столбца (для остальных элементов разрешающего столбца отношение θ не рассчитывается). Строка, для которой имеет место минимальное значение θ, является разрешающей (в таблицах разрешающие строки и столбцы выделены тёмным цветом). На пересечении разрешающей строки и столбца находится разрешающий элемент. Переход от одной симплекс-таблицы к другой происходит следующим образом. Все элементы разрешающей строки делятся на разрешающей элемент. Все элементы разрешающего столбца принимаются равными нулю, кроме разрешающего элемента, который уже будет равен единице. Остальные элементы новой симплекс-таблицы рассчитываются по правилу прямоугольника: Во всех таблицах в столбцах Сб стоят коэффициенты при соответствующих переменных в целевой функции. В первой симплекс-таблице в столбце b(i) стоят свободные члены при ограничениях условия (правые части неравенств в исходной системе ограничений). В остальных симплекс-таблицах все элементы (кроме столбца Сб) рассчитываются по правилу прямоугольника). Расчёты продолжаются до тех пор, пока в Δ-строке последней таблицы не останется положительных элементов.

БП	Сб	b(i)	x1(1)	x2(-4)	x3(0)	x4(0)	x5(0)	θ
x3	0	9	-1	3	1	0	0	3
x4	0	38	6	5	0	1	0	7,6
x5	0	10	2	-1	0	0	1
Δj		0	-1	4	0	0	0
x2	-4	3	-0,33333	1	0,333333	0	0
x4	0	23	7,666667	0	-1,66667	1	0	3
x5	0	13	1,666667	0	0,333333	0	1	7,8
Δj		-12	0,333333	0	-1,33333	0	0
x2	-4	4	0	1	0,26087	0,043478	0
x1	1	3	1	0	-0,21739	0,130435	0
x5	0	8	0	0	0,695652	-0,21739	1
Δj		-13	0	0	-1,26087	-0,04348	0

Так как в последней строке все элементы неположительны, то получен оптимальный план (дополнительные переменные опускаем): Минимальное значение целевой функции:

Задача № 3

Bj Ai	B1	B2	B3	ai
A1	2	5	2	80
A2	4	1	5	160
A3	3	6	7	90
bj	130	60	140

Решение

Так как , то имеем транспортную задачу закрытого типа. Начальный опорный план находим по правилу минимального элемента и решаем задачу методом потенциалов. Правило минимального элемента применяется следующим образом: находим клетку с минимальной стоимостью и заполняем её максимальной величиной перевозок; из оставшихся клеток опять находим клетку с минимальной стоимостью и заполняем её максимальной величиной перевозок; и т.д.

Bj Ai	B1	B2	B3	ai	ui
A1	2	5	2 80	80	u1=0
A2	4 40	1 60	5 60	160	u2=3
A3	3 90	6	7	90	u3=2
bj	130	60	140	330
vj	v1=1	v2=-2	v3=2

В таблице потенциалы u_i, v_j выбираются так. Один из потенциалов принимается равным произвольному числу (например, u₁=0). Далее по занятым перевозками клеткам остальные потенциалы выбираются так, чтобы для занятых клеток выполнялось равенство: .

Оценки свободных клеток:

Так как все оценки неотрицательны, то получен оптимальный план:

Минимальные транспортные затраты:

Так как все оценки строго положительны, то оптимальный план единственен.

Начальный опорный план построим также способом – способом северо-западного угла (этого нет в условии). Далее решаем задачу опять же методом потенциалов.

Bj Ai	B1	B2	B3	ai	ui
A1	2 80	5	2	80	u1=0
A2	4 50 -	1 60	5 50 +	160	u2=2
A3	3 +	6	7 90 -	90	u3=4
bj	130	60	140	330
vj	v1=2	v2=-1	v3=3

Так как есть отрицательные оценки, то строим цикл и составляем новый план.

Bj Ai	B1	B2	B3	ai	ui
A1	2 80 -	5	2 +	80	u1=0
A2	4	1 60	5 100	160	u2=-1
A3	3 50 +	6	7 40 -	90	u3=1
bj	130	60	140	330
vj	v1=2	v2=2	v3=6

Так как есть отрицательные оценки, то строим цикл и составляем новый план.

Bj Ai	B1	B2	B3	ai	ui
A1	2 40 -	5	2 40 +	80	u1=0
A2	4 +	1 60	5 100 -	160	u2=3
A3	3 90	6	7	90	u3=1
bj	130	60	140	330
vj	v1=2	v2=-2	v3=2

Так как есть отрицательные оценки, то строим цикл и составляем новый план.

Bj Ai	B1	B2	B3	ai	ui
A1	2	5	2 80	80	u1=0
A2	4 40	1 60	5 60	160	u2=3
A3	3 90	6	7	90	u3=2
bj	130	60	140	330
vj	v1=1	v2=-2	v3=2

Так как все оценки неотрицательны, то получен оптимальный план:

Минимальные транспортные затраты:

Так как все оценки строго положительны, то оптимальный план единственен.

Задача № 4

Решение

Применим для решения задачи алгоритм Форда-Фалкерсона.

Алгоритм из двух частей — насыщение потока и его перераспределение. В первой части задача ставится локально. Дуги рассматриваются отдельно (возможно хаотично) и каждой дуге приписывается возможно больший поток, согласованный только с условием сохранения в узлах (вершинах). Во второй части перераспределения потока выполняется из условия достижения общего по сети максимума потока.

1. Насыщение потока. Поток называется насыщенным, если любой путь из истока (I) в сток (S) содержит насыщенную дугу. Рассмотрим путь 1-6-8-9. Пропустим через этот путь поток равный 5. При этом дуга 1-6 будет насыщена. Аналогично, путь 1-2-5-8-9 насытим потоком 2. Распределение потока отметим на графе. В числителе ставим пропускную способность, в знаменателе — поток. Числитель всегда больше знаменателя, знаменатель может быть и нулем. Насыщенные дуги на рисунке выделены жирными линиями.

Далее путь 1-3-6-9 насытим потоком 3.

Путь 1-3-4-6-9 насытим потоком 1.

Путь 1-4-7-9 насытим потоком 2.

В сток S больше нет ненасыщенных путей. Поэтому получили поток максимальной мощности.

Сумма потоков, исходящих из I: 2+4+5+2=13. Сумма потоков, входящих в S: 2+4+7=13. Получили равные числа. Это свидетельствует о правильности решения. Таким образом, максимальный поток f_max=13. Ниже изображён максимальный поток с указанием направлений потоков по рёбрам.

Задача № 5

Решение

Каждое событие изобразим кружком, разделённым на 4 сектора. Сверху указываем номер события, слева и справа – соответственно ранний и поздний срок свершения события, снизу резерв времени события.

Ранний срок свершения события:

Поздние сроки свершения события:

Резервы времени событий:

Для критических событий резерв времени равен нулю. С учётом этого находим критический путь L_кр: 1-3-4-5-9-10 (наибольший по продолжительности путь с событиями, имеющими нулевой резерв времени).

Его длина: T_кр=9+7+5+8+6=35.

Литература