3.Задача 3.6

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

f=-x₁+2x₂→ max,

x₁-8x₂≤10,

x₁+x₂≤1,

3x₁+10x₂≤3,

x₁≥0, x₂≥0.

Приведем условие задачи к каноническому виду

f(х)+x₁-2x₂=0,

x₁-8x₂+х₃=10,

x₁+x₂+х₄=1,

3x₁+10x₂+х₅=3,

x₁≥0, x₂≥0.

Составим симплекс-таблицу(3.1).

БП	СЧ	Х1	Х2	Х3	Х4	Х5	α1
Х3	10	1	-8	1	0	0	-1,25
Х4	1	1	1	0	1	0	1
Х5	3	3	10	0	0	1	0,3
f	0	1	-2	0	0	0

Таблица 3.1.

В строке коэффициентов целевой функции найдем наибольшее отрицательное значение (-2).Столбец, соответствующий этому значению называется веду- щим. Разделим значения свободных членов на соответствующие значения ведущего столбца. В результате получим значения α_1.Выберем среди них наименьшее положительное значение (0,3).Соответствующая строка Х5 является ведущей.Пересечение ведущей строки и ведущего столбца дает ведущий элемент 10.

Разделим все элементы ведущей строки на ведущий элемент 10.Обозначение ведущей строки Х₅ заменим на обозначение ведущего столбца Х₂.Составим вторую симплекс - таблицу(3.2), используя преобразования:

новая Х₃=старая Х₃-(-8)*новая Х₂;

новая Х₄= старая Х₄-новая Х₂;

новая f=старая f-(-2)*новая Х₂.

БП	СЧ	Х1	Х2	Х3	Х4	Х5	α2
Х2	0,3	0,3	1	0	0	0,1
Х3	12,4	3,4	0	1	0	0,8
Х4	0,7	0,7	0	0	1	-0,1
f	0,6	1,6	0	0	0	0,2

Таблица 3.2

Все значения в строке функции базиса Х₂, Х₃, Х₄ не отрицательны. Следовательно, α₂=(0; 0,3; 12,4; 0,7; 0). Поэтому β=(0; 0,3)-оптимальное решение исходной задачи, при этом f(β)=0,6.

Ответ: β=(0; 0,3); f(β)=0,6.

4.Задача 4.6

Решить транспортную задачу, с заданными начальными условиями:

Транспортные издержки (матрица C)	Объём производства (матрица А)	Объём потребления (матрица В)
1 4 2 5 2 1 4 1 3 2 1 3	6,3,3	4,2,4,2

Решение:

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

Таблица 4.1.

Поставщик	Потребитель					Объём производства		U
	B1	B2	B3	B4
A1	4 1	… 4	2 2	… 5	6		0
A2	… 2	1 1	… 4	2 1	3		-2
A3	… 3	1 2	2 1	… 3	3		-1
Объём потребления	4	2	4	2	12
V	1	3	2	3

2. Найдем потенциалы поставщиков и потребителей. Для этого составим уравнения для заполненных клеток таблицы:

U₁+V₁=1, U₁+V₃=2, U₂+V₂=1,

U₂+V₄=1, U₃+V₃=2, U₃+V₃=1.

Пусть U₁=0.Тогда все остальные потенциалы для данного опорного решения можно определить :

U₁=0, V₁=1, V₃=2, U₃=-1, U₂=-2, V₄=3, V₂=3.

3.Затем для проверки оптимальности опорного плана просмотрим свобод- ные клетки, для которых определяем косвенные тарифы C'_ij =U_i + V_j.

C'₁₂ =U₁+V₂=0+3=3, C'₁₄ =U₁+V₄=0+3=3, C'₂₁ =U₂+V₁=-2+1=-1,

C'₂₃ =U₁+V₃=-2+2=0, C'₃₁ =U₃+V₁=-1+1=0, C'₃₄ =U₃+V₄=-1+3=2.

4.Далее для каждой свободной клетки вычислим оценки, то есть разницу между тарифом и косвенным тарифом S_ij=C_ij - C'_ij .

S₁₂=4-3=1, S₁₄=5-3=2, S₂₁=2-(-1)=3,

S₂₃=4-0=4, S₃₁=3-0=3, S₃₄=3-2=1.

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

Оптимальный план имеет вид:

Х_опт.=

Ответ: Х_опт.=