Содержание
Задача № 26 3
Задача № 27 10
Задача 3 11
Задача 4 17
Задача № 26
Фирма специализируется на производстве буфетов. Она может производить три типа буфетов А, В, С, что требует различных затрат труда на каждой стадии производства:
Производственный участок
Затраты труда, чел-ч
А
В
С
Лесопилка
1
2
4
Сборочный цех
2
4
2
Отделочный цех
1
1
2
В течение недели можно планировать работу на лесопилке на 360 чел-ч, в сборочном цехе – на 520 чел-ч и в отделочном цехе – на 220 чел-ч. Прибыль от продажи каждого буфета типов А, В, С составляет соответственно 9, 11, 15 дол. Составьте оптимальный план производства.
Решение:
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 9x1 + 11x2 + 15x3 при следующих условиях-ограничений.
x1 + 2x2 + 4x3?360
2x1 + 4x2 + 2x3?520
x1 + x2 + 2x3?220
Для построения первого опорного плана в системе уравнений уже имеются базисные переменные.
1x1 + 2x2 + 4x3 + 1x4 + 0x5 + 0x6 = 360
2x1 + 4x2 + 2x3 + 0x4 + 1x5 + 0x6 = 520
1x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 220
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Базис
B
x1
x2
x3
x4
x5
x6
x4
360
1
2
4
1
0
0
x5
520
2
4
2
0
1
0
x6
220
1
1
2
0
0
1
F(X0)
0
-9
-11
-15
0
0
0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi/ai3
и из них выберем наименьшее:
min (360: 4, 520: 2, 220: 2 ) = 90
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
x6
min
x4
360
1
2
4
1
0
0
90
x5
520
2
4
2
0
1
0
260
x6
220
1
1
2
0
0
1
110
F(X1)
0
-9
-11
-15
0
0
0
0
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x3.
Получаем новую симплекс-таблицу:
Базис
B
x1
x2
x3
x4
x5
x6
x3
90
1/4
1/2
1
1/4
0
0
x5
340
11/2
3
0
-1/2
1
0
x6
40
1/2
0
0
-1/2
0
1
F(X1)
1350
-51/4
-31/2
0
33/4
0
0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi/ai1
и из них выберем наименьшее:
min (90: 1/4, 340: 11/2, 40: 1/2 ) = 80
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (1/2) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B
x1
x2
x3
x4
x5
x6
min
x3
90
1/4
1/2
1
1/4
0
0
360
x5
340
11/2
3
0
-1/2
1
0
2262/3
x6
40
1/2
0
0
-1/2
0
1
80
F(X2)
1350
-51/4
-31/2
0
33/4
0
0
0
Формируем следующую часть симплекс