Здравствуйте, Посетитель - 399202!

Пусть изготовлено x[sub]1[/sub] деталей первого вида, x[sub]2[/sub] деталей второго вида и x[sub]3[/sub] деталей третьего вида (эти величины должны быть целыми и неотрицательными). Тогда время работы первого станка составит 2x[sub]1[/sub]+x[sub]2[/sub] часов, при этом оно не должно превышать 8 часов (фонд времени для первого станка). Соответственно, время работы второго станка - 2x[sub]2[/sub]+x[sub]3[/sub] часов (но не более 4 часов), третьего - 3x[sub]1[/sub]+2x[sub]3[/sub] часов (но не более 18 часов). Если прибыль от продажи деталей первого, второго и третьего вида составляет 6, 12 и 2 соответственно, то суммарная прибыль будет равна 6x[sub]1[/sub]+12x[sub]2[/sub]+2x[sub]3[/sub]. Требуется установить, при каких x[sub]1[/sub], x[sub]2[/sub] и x[sub]3[/sub] она будет наибольшей.
Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 6x[sub]1[/sub]+2x[sub]2[/sub]+12x[sub]3[/sub] [$8594$] max при системе ограничений:

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

(с экономической точки зрения дополнительные переменные обозначают неиспользованные остатки фонда времени). Полагая свободные переменные x[sub]1[/sub], x[sub]2[/sub], x[sub]3[/sub] равными 0, получим начальный опорный план X = (0, 0, 0, 8, 14, 18).
1. Составим симплекс-таблицу:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]x₅[/col][col]4[/col][col]0[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₆[/col][col]18[/col][col]3[/col][col]0[/col][col]2[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-6[/col][col]-2[/col][col]-12[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Этот опорный план допустим, так как все свободные члены (8, 4, 18) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -12. Соответствующая ему переменная x[sub]3[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (8/0, 4/1, 18/2) = ([$8734$], 4, 9). Наименьшее среди них равно 4. Соответствующая ему переменная x[sub]5[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col silver]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col]2[/col][col]1[/col][col silver]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col silver]x₅[/col][col silver]4[/col][col silver]0[/col][col silver]2[/col][col gray]1[/col][col silver]0[/col][col silver]1[/col][col silver]0[/col][/row]
[row][col]x₆[/col][col]18[/col][col]3[/col][col]0[/col][col silver]2[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-6[/col][col]-2[/col][col silver]-12[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 1. Заменяем строку x[sub]5[/sub] на строку x[sub]3[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col silver]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col]2[/col][col]1[/col][col silver]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col silver]x₃[/col][col silver]4[/col][col silver]0[/col][col silver]2[/col][col gray]1[/col][col silver]0[/col][col silver]1[/col][col silver]0[/col][/row]
[row][col]x₆[/col][col]18[/col][col]3[/col][col]0[/col][col silver]2[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-6[/col][col]-2[/col][col silver]-12[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]3[/sub] из остальных строк, для чего вычитаем из них строку x[sub]3[/sub], умноженную на соответствующий элемент столбца x[sub]3[/sub] (0 для x[sub]4[/sub], 2 для x[sub]6[/sub] и -12 для F(X)):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]x₃[/col][col]4[/col][col]0[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₆[/col][col]10[/col][col]3[/col][col]-4[/col][col]0[/col][col]0[/col][col]-2[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]48[/col][col]-6[/col][col]22[/col][col]0[/col][col]0[/col][col]12[/col][col]0[/col][/row]
[/table]
2. Получаем новый опорный план X = (0, 0, 4, 8, 0, 10). Он допустим, так как все свободные члены (4, 8, 10) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -6 в столбце x[sub]1[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]1[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (8/2, 4/0, 10/3) = (4, [$8734$], 10/3). Наименьшее среди них равно 10/3. Соответствующая ему переменная x[sub]6[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col silver]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]x₃[/col][col]4[/col][col silver]0[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col silver]x₆[/col][col silver]10[/col][col gray]3[/col][col silver]-4[/col][col silver]0[/col][col silver]0[/col][col silver]-2[/col][col silver]1[/col][/row]
[row][col]F(X)[/col][col]48[/col][col silver]-6[/col][col]22[/col][col]0[/col][col]0[/col][col]12[/col][col]0[/col][/row]
[/table]
Разрешающий элемент равен 3. Заменяем строку x[sub]6[/sub] на строку x[sub]1[/sub], разделив все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]8[/col][col silver]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]x₃[/col][col]4[/col][col silver]0[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col silver]x₁[/col][col silver]10/3[/col][col gray]1[/col][col silver]-4/3[/col][col silver]0[/col][col silver]0[/col][col silver]-2/3[/col][col silver]1/3[/col][/row]
[row][col]F(X)[/col][col]48[/col][col silver]-6[/col][col]22[/col][col]0[/col][col]0[/col][col]12[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]1[/sub] из остальных строк, для чего вычитаем из них строку x[sub]1[/sub], умноженную на соответствующий элемент столбца x[sub]1[/sub] (2 для x[sub]4[/sub], 0 для x[sub]3[/sub] и -6 для F(X)):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]4/3[/col][col]0[/col][col]11/3[/col][col]0[/col][col]1[/col][col]4/3[/col][col]-2/3[/col][/row]
[row][col]x₃[/col][col]4[/col][col]0[/col][col]2[/col][col]1[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₁[/col][col]10/3[/col][col]1[/col][col]-4/3[/col][col]0[/col][col]0[/col][col]-2/3[/col][col]1/3[/col][/row]
[row][col]F(X)[/col][col]68[/col][col]0[/col][col]14[/col][col]0[/col][col]0[/col][col]8[/col][col]2[/col][/row]
[/table]
3. Получаем новый опорный план X = (10/3, 0, 4, 4/3, 0, 0). Он допустим, так как все свободные члены (10/3, 4, 4/3) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Так как переменные x[sub]1[/sub]...x[sub]6[/sub] должны быть целочисленными (количество деталей не может быть дробным), то оптимальный план можно записать как x[sub]1[/sub] = 3, x[sub]2[/sub] = 0, x[sub]3[/sub] = 4, F = 6[$183$]3 + 12[$183$]4 = 66. При этом использование фонда времени составит
2[$183$]3+0[$183$]4=6 часов для первого станка, 2[$183$]0+1[$183$]4=4 часов для второго станка и 3[$183$]3+2[$183$]4=17 часов для третьего станка. Следовательно, для первого и третьего станков имеет место недоиспользование фонда времени на 2 часа и 1 час соответственно.
Отметим также, что x[sub]2[/sub]=0, то есть выпуск деталей второго вида невыгоден.