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

Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 3x[sub]1[/sub]+2x[sub]2[/sub] [$8594$] max при системе ограничений:

x[sub]1[/sub][$8805$]0, x[sub]2[/sub][$8805$]0.

Перейдём к канонической форме, то есть приведём систему неравенств к системе уравнений путём введения дополнительных базисных переменных x[sub]3[/sub], x[sub]4[/sub], x[sub]5[/sub]:

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

Составим симплекс-таблицу:
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]2[/col][col]4[/col][col]1[/col][col]0[/col][col]0[/col][col]720[/col][/row]
[row][col]x₄[/col][col]4[/col][col]6[/col][col]0[/col][col]1[/col][col]0[/col][col]300[/col][/row]
[row][col]x₅[/col][col]9[/col][col]2[/col][col]0[/col][col]0[/col][col]1[/col][col]422[/col][/row]
[row][col]F(X)[/col][col]-3[/col][col]-2[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Этот опорный план допустим, так как все свободные члены (720, 300, 422) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -3. Соответствующая ему переменная x[sub]1[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (720/2, 300/4, 422/9) = (360, 75, 422/9). Наименьшее среди них неотрицательное значение равно 422/9. Соответствующая ему переменная x[sub]5[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col silver]2[/col][col]4[/col][col]1[/col][col]0[/col][col]0[/col][col]720[/col][/row]
[row][col]x₄[/col][col silver]4[/col][col]6[/col][col]0[/col][col]1[/col][col]0[/col][col]300[/col][/row]
[row][col silver]x₅[/col][col gray]9[/col][col silver]2[/col][col silver]0[/col][col silver]0[/col][col silver]1[/col][col silver]422[/col][/row]
[row][col]F(X)[/col][col silver]-3[/col][col]-2[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 9. Заменяем строку x[sub]5[/sub] на строку x[sub]1[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col silver]2[/col][col]4[/col][col]1[/col][col]0[/col][col]0[/col][col]720[/col][/row]
[row][col]x₄[/col][col silver]4[/col][col]6[/col][col]0[/col][col]1[/col][col]0[/col][col]300[/col][/row]
[row][col silver]x₁[/col][col gray]1[/col][col silver]2/9[/col][col silver]0[/col][col silver]0[/col][col silver]1/9[/col][col silver]422/9[/col][/row]
[row][col]F(X)[/col][col silver]-3[/col][col]-2[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Исключаем новую базисную переменную x[sub]1[/sub] из остальных строк, для чего вычитаем из них строку x[sub]1[/sub], умноженную на соответствующий элемент столбца x[sub]1[/sub] (2 для x[sub]3[/sub], 4 для x[sub]4[/sub] и -3 для F(X)):
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]0[/col][col]32/9[/col][col]1[/col][col]0[/col][col]-2/9[/col][col]5636/9[/col][/row]
[row][col]x₄[/col][col]0[/col][col]46/9[/col][col]0[/col][col]1[/col][col]-4/9[/col][col]1012/9[/col][/row]
[row][col]x₁[/col][col]1[/col][col]2/9[/col][col]0[/col][col]0[/col][col]1/9[/col][col]422/9[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-4/3[/col][col]0[/col][col]0[/col][col]1/3[/col][col]422/3[/col][/row]
[/table]Получаем новый опорный план X = (422/9, 0, 5636/9, 1012/9, 0). Он допустим, так как все свободные члены (422/9, 5636/9, 1012/9) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -4/3 в столбце x[sub]2[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]2[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (1409/8, 22, 211). Наименьшее среди них неотрицательное значение равно 22. Соответствующая ему переменная x[sub]4[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]0[/col][col silver]32/9[/col][col]1[/col][col]0[/col][col]-2/9[/col][col]5636/9[/col][/row]
[row][col silver]x₄[/col][col silver]0[/col][col gray]46/9[/col][col silver]0[/col][col silver]1[/col][col silver]-4/9[/col][col silver]1012/9[/col][/row]
[row][col]x₁[/col][col]1[/col][col silver]2/9[/col][col]0[/col][col]0[/col][col]1/9[/col][col]422/9[/col][/row]
[row][col]F(X)[/col][col]0[/col][col silver]-4/3[/col][col]0[/col][col]0[/col][col]1/3[/col][col]422/3[/col][/row]
[/table]Разрешающий элемент равен 46/9. Заменяем строку x[sub]4[/sub] на строку x[sub]2[/sub], разделив все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]0[/col][col silver]32/9[/col][col]1[/col][col]0[/col][col]-2/9[/col][col]5636/9[/col][/row]
[row][col silver]x₂[/col][col silver]0[/col][col gray]1[/col][col silver]0[/col][col silver]9/46[/col][col silver]-2/23[/col][col silver]22[/col][/row]
[row][col]x₁[/col][col]1[/col][col silver]2/9[/col][col]0[/col][col]0[/col][col]1/9[/col][col]422/9[/col][/row]
[row][col]F(X)[/col][col]0[/col][col silver]-4/3[/col][col]0[/col][col]0[/col][col]1/3[/col][col]422/3[/col][/row]
[/table]Исключаем новую базисную переменную x[sub]2[/sub] из остальных строк, для чего вычитаем из них строку x[sub]2[/sub], умноженную на соответствующий элемент столбца x[sub]2[/sub] (2/9 для x[sub]1[/sub], 32/9 для x[sub]5[/sub] и -4/3 для F(X)):
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]0[/col][col]0[/col][col]1[/col][col]-16/23[/col][col]2/23[/col][col]548[/col][/row]
[row][col]x₂[/col][col]0[/col][col]1[/col][col]0[/col][col]9/46[/col][col]-2/23[/col][col]22[/col][/row]
[row][col]x₁[/col][col]1[/col][col]0[/col][col]0[/col][col]-1/23[/col][col]3/23[/col][col]42[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]0[/col][col]0[/col][col]6/23[/col][col]5/23[/col][col]170[/col][/row]
[/table]Получаем новый опорный план X = (42, 22, 548, 0, 0). Он допустим, так как все свободные члены (42, 22, 548) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Оптимальный план можно записать как x[sub]1[/sub] = 42, x[sub]2[/sub] = 22, то есть при изготовлении 42 единиц продукции P[sub]1[/sub] и 22 единиц продукции P[sub]2[/sub] прибыль от их продажи будет максимальна и равна 170 руб. При этом x[sub]4[/sub] = x[sub]5[/sub] = 0, но x[sub]3[/sub] = 548, то есть сырьё S[sub]2[/sub] и S[sub]3[/sub] будет израсходовано полностью, остаток же сырья S[sub]1[/sub] составит 548 единиц.