Пример решения задачи симплекс М-методом

Условие задачи, решаемой симплекс М методом.

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

Содержание

Условие задачи

Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.

Решение задачи симплекс методом

1) Определение оптимального плана производства

Пусть x₁, x₂, x₃ - количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:

F = 10 · x₁ + 8 · x₂ + 12 · x₃ → max

5·x₁	+ 2·x₂	+ 4·x₃	≤	2000
4·x₁	+ 5·x₂	+ 4·x₃	≤	1000
1·x₁	+ 0·x₂	+ 0·x₃	≥	100
0·x₁	+ 1·x₂	+ 0·x₃	≥	50
x₁ ≥ 0	x₂ ≥ 0	x₃ ≥ 0

Решаем симплекс методом.

Вводим дополнительные переменные x₄ ≥ 0, x₅ ≥ 0, x₆ ≥ 0, x₇ ≥ 0, чтобы неравенства преобразовать в равенства.

5·x₁	+ 2·x₂	+ 4·x₃	+ 1·x₄	+ 0·x₅	+ 0·x₆	+ 0·x₇	=	2000
4·x₁	+ 5·x₂	+ 4·x₃	+ 0·x₄	+ 1·x₅	+ 0·x₆	+ 0·x₇	=	1000
1·x₁	+ 0·x₂	+ 0·x₃	+ 0·x₄	+ 0·x₅	– 1·x₆	+ 0·x₇	=	100
0·x₁	+ 1·x₂	+ 0·x₃	+ 0·x₄	+ 0·x₅	+ 0·x₆	– 1·x₇	=	50
x₁ ≥ 0	x₂ ≥ 0	x₃ ≥ 0	x₄ ≥ 0	x₅ ≥ 0	x₆ ≥ 0	x₇ ≥ 0

Чтобы найти начальный базис, вводим новые искусственные переменные x₈ ≥ 0, x₉ ≥ 0.
Вводим очень большое положительное число M→+∞, и решаем М методом.

F = 10 · x₁ + 8 · x₂ + 12 · x₃ + 0 · x₄ + 0 · x₅ + 0 · x₆ + 0 · x₇ – M · x₈ – M · x₉ → max

5·x₁	+ 2·x₂	+ 4·x₃	+ 1·x₄	+ 0·x₅	+ 0·x₆	+ 0·x₇	+ 0·x₈	+ 0·x₉	=	2000
4·x₁	+ 5·x₂	+ 4·x₃	+ 0·x₄	+ 1·x₅	+ 0·x₆	+ 0·x₇	+ 0·x₈	+ 0·x₉	=	1000
1·x₁	+ 0·x₂	+ 0·x₃	+ 0·x₄	+ 0·x₅	– 1·x₆	+ 0·x₇	+ 1·x₈	+ 0·x₉	=	100
0·x₁	+ 1·x₂	+ 0·x₃	+ 0·x₄	+ 0·x₅	+ 0·x₆	– 1·x₇	+ 0·x₈	+ 1·x₉	=	50
x₁ ≥ 0	x₂ ≥ 0	x₃ ≥ 0	x₄ ≥ 0	x₅ ≥ 0	x₆ ≥ 0	x₇ ≥ 0	x₈ ≥ 0	x₉ ≥ 0

В качестве базиса возьмем x₄ = 2000; x₅ = 1000; x₈ = 100; x₉ = 50.
Данные заносим в симплекс таблицу.

Симплекс таблица № 1

	C_j		10	8	12	0	0	0	0	– M	– M
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
0	x₄	2000	5	2	4	1	0	0	0	0	0	400
0	x₅	1000	4	5	4	0	1	0	0	0	0	250
– M	x₈	100	1	0	0	0	0	– 1	0	1	0	100
– M	x₉	50	0	1	0	0	0	0	– 1	0	1	∞
	Δ_i	– 150M	– M – 10	– M – 8	– 12			M	M

Целевая функция:
F = 4∑i = 1C_i·b_i = 0 · 2000 + 0 · 1000 – M · 100 – M · 50 = – 150M

Вычисляем оценки по формуле:
Δ(x_j) = 4∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₁) = 0 · 5 + 0 · 4 – M · 1 – M · 0 – 10 = – M – 10
Δ(x₂) = 0 · 2 + 0 · 5 – M · 0 – M · 1 – 8 = – M – 8
Δ(x₃) = 0 · 4 + 0 · 4 – M · 0 – M · 0 – 12 = – 12
Δ(x₆) = 0 · 0 + 0 · 0 – M · ( – 1) – M · 0 – 0 = M
Δ(x₇) = 0 · 0 + 0 · 0 – M · 0 – M · ( – 1) – 0 = M

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка
Δ(x₁) = – M – 10.
Вводим переменную x₁ в базис.

Определяем переменную, выходящую из базиса из условия, чтобы остальные базисные переменные не приняли отрицательных значений. Для этого находим наименьшее неотрицательное отношение Q_i = b_i/a_i2 для столбца x₁:
Q₁ = 2000 / 5 = 400
Q₂ = 1000 / 4 = 250
Q₃ = 100 / 1 = 100
Q₄ = 50 / 0 = ∞
Наименьшее неотрицательное отношение Q₃ = 100 в строке 3. Переменная x₈ выходит из базиса.

Вводим переменную x₁ в базис. Переменную в строке x₈ выводим из базиса. Для этого выполняем эквивалентные преобразования, чтобы столбец x₁ состоял из единицы, в строке x₁, и нулей, в остальных строках.

Из 1-й строки вычитаем 3-ю строку, умноженную на 5
Из 2-й строки вычитаем 3-ю строку, умноженную на 4

	C_j		10	8	12	0	0	0	0	– M	– M
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉
0	x₄	2000 – 5·100	5 – 5·1	2 – 5·0	4 – 5·0	1 – 5·0	0 – 5·0	0 – 5·( – 1)	0 – 5·0	0 – 5·1	0 – 5·0
0	x₅	1000 – 4·100	4 – 4·1	5 – 4·0	4 – 4·0	0 – 4·0	1 – 4·0	0 – 4·( – 1)	0 – 4·0	0 – 4·1	0 – 4·0
10	x₁	100	1	0	0	0	0	– 1	0	1	0
– M	x₉	50	0	1	0	0	0	0	– 1	0	1

Получаем новую таблицу.

Симплекс таблица № 2

	C_j		10	8	12	0	0	0	0	– M	– M
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
0	x₄	1500	0	2	4	1	0	5	0	– 5	0	750
0	x₅	600	0	5	4	0	1	4	0	– 4	0	120
10	x₁	100	1	0	0	0	0	– 1	0	1	0	∞
– M	x₉	50	0	1	0	0	0	0	– 1	0	1	50
	Δ_i	– 50M + 1000		– M – 8	– 12			– 10	M	M + 10

Целевая функция:
F = 4∑i = 1C_i·b_i = 0 · 1500 + 0 · 600 + 10 · 100 – M · 50 = – 50M + 1000

Вычисляем оценки по формуле:
Δ(x_j) = 4∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₂) = 0 · 2 + 0 · 5 + 10 · 0 – M · 1 – 8 = – M – 8
Δ(x₃) = 0 · 4 + 0 · 4 + 10 · 0 – M · 0 – 12 = – 12
Δ(x₆) = 0 · 5 + 0 · 4 + 10 · ( – 1) – M · 0 – 0 = – 10
Δ(x₇) = 0 · 0 + 0 · 0 + 10 · 0 – M · ( – 1) – 0 = M
Δ(x₈) = 0 · ( – 5) + 0 · ( – 4) + 10 · 1 – M · 0 – ( – M) = M + 10

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка
Δ(x₂) = – M – 8.
Вводим переменную x₂ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Q_i = b_i/a_i2 для столбца x₂:
Q₁ = 1500 / 2 = 750
Q₂ = 600 / 5 = 120
Q₃ = 100 / 0 = ∞
Q₄ = 50 / 1 = 50
Наименьшее неотрицательное отношение Q₄ = 50 в строке 4. Выводим переменную x₉ из базиса и удаляем искусственные переменные. Выполняем линейные преобразования

Из 1-й строки вычитаем 4-ю строку, умноженную на 2
Из 2-й строки вычитаем 4-ю строку, умноженную на 5

	C_j		10	8	12	0	0	0	0
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇
0	x₄	1500 – 2·50	0 – 2·0	2 – 2·1	4 – 2·0	1 – 2·0	0 – 2·0	5 – 2·0	0 – 2·( – 1)
0	x₅	600 – 5·50	0 – 5·0	5 – 5·1	4 – 5·0	0 – 5·0	1 – 5·0	4 – 5·0	0 – 5·( – 1)
10	x₁	100	1	0	0	0	0	– 1	0
8	x₂	50	0	1	0	0	0	0	– 1

Получаем новую таблицу.

Симплекс таблица № 3

	C_j		10	8	12	0	0	0	0
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇	Q
0	x₄	1400	0	0	4	1	0	5	2	350
0	x₅	350	0	0	4	0	1	4	5	87,5
10	x₁	100	1	0	0	0	0	– 1	0	∞
8	x₂	50	0	1	0	0	0	0	– 1	∞
	Δ_i	1400			– 12			– 10	– 8

Целевая функция:
F = 4∑i = 1C_i·b_i = 0 · 1400 + 0 · 350 + 10 · 100 + 8 · 50 = 1400

Вычисляем оценки по формуле:
Δ(x_j) = 4∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₃) = 0 · 4 + 0 · 4 + 10 · 0 + 8 · 0 – 12 = – 12
Δ(x₆) = 0 · 5 + 0 · 4 + 10 · ( – 1) + 8 · 0 – 0 = – 10
Δ(x₇) = 0 · 2 + 0 · 5 + 10 · 0 + 8 · ( – 1) – 0 = – 8

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка
Δ(x₃) = – 12.
Вводим переменную x₃ в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение Q_i = b_i/a_i2 для столбца x₃:
Q₁ = 1400 / 4 = 350
Q₂ = 350 / 4 = 87,5
Q₃ = 100 / 0 = ∞
Q₄ = 50 / 0 = ∞
Наименьшее неотрицательное отношение Q₂ = 87,5 в строке 2. Переменная x₅ выходит из базиса.

2-ю строку делим на 4
Из 1-й строки вычитаем 2-ю строку, умноженную на 4

	C_j		10	8	12	0	0	0	0
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇
0	x₄	1400 – 4·1752	0 – 4·0	0 – 4·0	4 – 4·1	1 – 4·0	0 – 4·14	5 – 4·1	2 – 4·54
12	x₃	1752	0	0	1	0	14	1	54
10	x₁	100	1	0	0	0	0	– 1	0
8	x₂	50	0	1	0	0	0	0	– 1

Подробные вычисления
1400 – 4·1752 = 1400 – 7002 = 1400 – 350 = 1050
2 – 4·54 = 2 – 204 = 2 – 5 = – 3

Получаем новую таблицу.

Симплекс таблица № 4

	C_j		10	8	12	0	0	0	0
C_i	Базис	b_i	x₁	x₂	x₃	x₄	x₅	x₆	x₇
0	x₄	1050	0	0	0	1	– 1	1	– 3
12	x₃	1752	0	0	1	0	14	1	54
10	x₁	100	1	0	0	0	0	– 1	0
8	x₂	50	0	1	0	0	0	0	– 1
	Δ_i	2450					3	2	7

Целевая функция:
F = 4∑i = 1C_i·b_i = 0 · 1050 + 12 · 1752 + 10 · 100 + 8 · 50 = 2450

Вычисляем оценки по формуле:
Δ(x_j) = 4∑i = 1C_i·a_ij – C_j.
Оценки базисных переменных всегда равны нулю. Для свободных переменных, имеем:
Δ(x₅) = 0 · ( – 1) + 12 · 14 + 10 · 0 + 8 · 0 – 0 = 3
Δ(x₆) = 0 · 1 + 12 · 1 + 10 · ( – 1) + 8 · 0 – 0 = 2
Δ(x₇) = 0 · ( – 3) + 12 · 54 + 10 · 0 + 8 · ( – 1) – 0 = 7

Отрицательных оценок нет. План оптимальный.

Ответ

x₁ = 100; x₂ = 50; x₃ = 1752 ≈ 87,5; x₄ = 1050; x₅ = 0; x₆ = 0; x₇ = 0; F_max = 2450.

То есть необходимо произвести x₁ = 100 единиц продукции вида А, x₂ = 50 единиц продукции вида Б и x₃ = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит F_max = 2450 единиц.

Автор: Олег Одинцов. Опубликовано: 08-12-2011