Пусть произведено x₁ единиц продукции P₁ и x₂ единиц продукции P₂ (эти величины должны быть целыми и неотрицательными). Тогда будет израсходовано 2x₁+4x₂ единиц сырья S₁ (но не более 720), 4x₁+6x₂ единиц сырья S₂ (но не более 300) и 9x₁+2x₂ единиц сырья S₄ (но не более 422). Если прибыль от продажи единицы продукции P₁ и P₂ составляет 3 и 2 рубля соответственно, то полная прибыль будет равна 3x₁+2x₂ руб. Требуется установить, при каких x₁ и x₂ она будет наибольшей.

Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 3x₁+2x₂ → max при системе ограничений:

x₁≥0, x₂≥0.

Перейдём к канонической форме, то есть приведём систему неравенств к системе уравнений путём введения дополнительных базисных переменных x₃, x₄, x₅:

(дополнительные переменные обозначают неиспользованные остатки сырья). Полагая свободные переменные x₁, x₂ равными 0, получим начальный опорный план X = (0, 0, 720, 300, 422).

Составим симплекс-таблицу:

Базис	x1	x2	x3	x4	x5
x3	2	4	1	0	0	720
x4	4	6	0	1	0	300
x5	9	2	0	0	1	422
F(X)	-3	-2	0	0	0	0

Этот опорный план допустим, так как все свободные члены (720, 300, 422) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -3. Соответствующая ему переменная x₁ будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (720/2, 300/4, 422/9) = (360, 75, 422/9). Наименьшее среди них неотрицательное значение равно 422/9. Соответствующая ему переменная x₅ будет новой свободной переменной, а соответствующая строка - ведущей:

Базис	x1	x2	x3	x4	x5
x3	2	4	1	0	0	720
x4	4	6	0	1	0	300
x5	9	2	0	0	1	422
F(X)	-3	-2	0	0	0	0

Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 9. Заменяем строку x₅ на строку x₁, для чего делим все её элементы на разрешающий элемент:

Базис	x1	x2	x3	x4	x5
x3	2	4	1	0	0	720
x4	4	6	0	1	0	300
x1	1	2/9	0	0	1/9	422/9
F(X)	-3	-2	0	0	0	0

Исключаем новую базисную переменную x₁ из остальных строк, для чего вычитаем из них строку x₁, умноженную на соответствующий элемент столбца x₁ (2 для x₃, 4 для x₄ и -3 для F(X)):

Базис	x1	x2	x3	x4	x5
x3	0	32/9	1	0	-2/9	5636/9
x4	0	46/9	0	1	-4/9	1012/9
x1	1	2/9	0	0	1/9	422/9
F(X)	0	-4/3	0	0	1/3	422/3

Получаем новый опорный план X = (422/9, 0, 5636/9, 1012/9, 0). Он допустим, так как все свободные члены (422/9, 5636/9, 1012/9) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -4/3 в столбце x₂. Других отрицательных коэффициентов нет, поэтому переменная x₂ будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (1409/8, 22, 211). Наименьшее среди них неотрицательное значение равно 22. Соответствующая ему переменная x₄ будет новой свободной переменной, а соответствующая строка - ведущей:

Базис	x1	x2	x3	x4	x5
x3	0	32/9	1	0	-2/9	5636/9
x4	0	46/9	0	1	-4/9	1012/9
x1	1	2/9	0	0	1/9	422/9
F(X)	0	-4/3	0	0	1/3	422/3

Разрешающий элемент равен 46/9. Заменяем строку x₄ на строку x₂, разделив все её элементы на разрешающий элемент:

Базис	x1	x2	x3	x4	x5
x3	0	32/9	1	0	-2/9	5636/9
x2	0	1	0	9/46	-2/23	22
x1	1	2/9	0	0	1/9	422/9
F(X)	0	-4/3	0	0	1/3	422/3

Исключаем новую базисную переменную x₂ из остальных строк, для чего вычитаем из них строку x₂, умноженную на соответствующий элемент столбца x₂ (2/9 для x₁, 32/9 для x₅ и -4/3 для F(X)):

Базис	x1	x2	x3	x4	x5
x3	0	0	1	-16/23	2/23	548
x2	0	1	0	9/46	-2/23	22
x1	1	0	0	-1/23	3/23	42
F(X)	0	0	0	6/23	5/23	170

Получаем новый опорный план X = (42, 22, 548, 0, 0). Он допустим, так как все свободные члены (42, 22, 548) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Оптимальный план можно записать как x₁ = 42, x₂ = 22, то есть при изготовлении 42 единиц продукции P₁ и 22 единиц продукции P₂ прибыль от их продажи будет максимальна и равна 170 руб. При этом x₄ = x₅ = 0, но x₃ = 548, то есть сырьё S₂ и S₃ будет израсходовано полностью, остаток же сырья S₁ составит 548 единиц.

Последнее редактирование 29.03.2022, 07:15 Коцюрбенко Алексей Владимирович (Старший модератор)