Здравствуйте, Посетитель - 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
1[/col][col]x
2[/col][col]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
5[/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
6[/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
1[/col][col]x
2[/col][col silver]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
5[/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
6[/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
1[/col][col]x
2[/col][col silver]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
3[/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
6[/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
1[/col][col]x
2[/col][col]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
3[/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
6[/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
1[/col][col]x
2[/col][col]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
3[/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
6[/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
1[/col][col]x
2[/col][col]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
3[/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
1[/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
1[/col][col]x
2[/col][col]x
3[/col][col]x
4[/col][col]x
5[/col][col]x
6[/col][/row]
[row][col]x
4[/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
3[/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
1[/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, то есть выпуск деталей второго вида невыгоден.