Решить задачу симплекс-методом.
Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в таблице. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.
Тип оборудования
Затраты времени (оборуд.-час) на обработку
одного изделия Общий фонд полезного рабочего времени оборудования (ч)
А В
Фрезерное 10 8 168
Токарное 5 10 180
Шлифовальное 6 12 144
Прибыль от реализации одного изделия (руб.) 14 18
Найти план выпуска изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Решение
Пусть будет изготовлено х1 единиц изделий вида А и х2 единиц изделий вида В.
На изготовление х1 изделий вида А будет затрачено 10х1 часов работы фрезерного оборудования, 5х1 часов работы токарного оборудования, 6х1 часов работы шлифовального оборудования. На изготовление х2 изделий вида В будет затрачено 8х2 часов работы фрезерного оборудования, 10х2 часов работы токарного оборудования, 12х2 часов работы шлифовального оборудования. Учитывая размеры общего фонда полезного рабочего времени оборудования, получаем систему ограничений:
Совокупная прибыль от реализации изделий видов А и В составит:
(руб.).
Требуется найти план, обеспечивающий наибольшую прибыль производству, т. е. найти допустимый план, для которого функция
принимает наибольшее значение.
Итак, пришли к следующей задаче линейного программирования:
при условиях
Приведем задачу к каноническому виду
. Введем дополнительные переменные у1, у2, у3 ≥ 0, преобразующие систему ограничений в систему равенств:
Необходимо найти .
Правые части уравнений неотрицательны. Система уравнений является разрешенной относительно переменных y1, у2, уз, которые могут считаться базисными переменными допустимого начального базисного решения:
У1 = 168, у2 = 180, уз = 144, х1 = 0, х2 = 0.
Составим начальную симплекс-таблицу задачи:
max с 14 18 0 0 0
№ Базис Сбаз. х1
х2
у1
у2
у3 в
1 у1
0 10 8 1 0 0 168 168/8=21
2 у2
0 5 10 0 1 0 180 180/10=18
3 у3 0 6 12 0 0 1 144 144/12=12
-14 -18 0 0 0 0
Оценки в нижней строке будем вычислять по формуле .
;
.
Значение целевой функции для начального базисного решения равно:
.
Этап 1
Шаг 1. Поскольку и , начальное базисное решение не является оптимальным. Введем в новое базисное решение х2, так как отрицательная оценка больше по модулю.
Выделим разрешающий столбец – столбец переменной х2.
Шаг 2