Содержание
Задание 1. Технологическая матрица затрат различных ресурсов на единицу каждой продукции А, вектор объемов ресурсов В и вектор удельной прибыли С при возможном выпуске четырех видов продукции с использованием трех видов ресурсов:
,, .
1.1. Сформулировать линейную производственную задачу и составить ее математическую модель.
1.2. Преобразовать данную задачу к виду основной задачи линейного программирования.
1.3. Решить ее симплексным методом, обосновывая каждый шаг процесса.
1.4. Найти оптимальную производственную программу.
1.5. Найти максимальную прибыль.
1.6. Найти остатки ресурсов различных видов и указать «узкие места» производства.
1.7. В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных.
1.8. Проверить выполнение соотношения: Н = Q-1B.
1.9. Если по оптимальной производственной программе какие-то два вида продукции не должны выпускаться, то в таблице исходных данных вычеркнуть соответствующие два столбца, составить математическую модель задачи оптимизации производственной программы с двумя оставшимися переменными, сохранив прежнюю нумерацию переменных и решить графически.
1.10. Сформулировать задачу, двойственную линейной производственной задаче, как задачу определения расчетных оценок ресурсов.
1.11. Найти решение двойственной задачи, пользуясь второй основной теоремой двойственности (о дополняющей нежесткости).
1.12. Указать оценку единицы каждого ресурса.
1.13. Указать минимальную суммарную оценку всех ресурсов.
1.14. Указать оценки технологий.
Решение.
1.1) В общем виде задача может быть сформулирована следующим образом: предположим, предприятие или цех может выпускать 3 вида продукции, используя 4 вида ресурсов. При этом известно количество каждого вида ресурса, расход каждого вида ресурса на выпуск каждого вида продукции, прибыль, получаемая с единицы выпущенной продукции. Требуется составить такой план производства продукции, при котором прибыль, получаемая предприятием, была бы наибольшей.
Математическая модель задачи в следующем: найти производственную программу, максимизирующую прибыль:
при ограничениях по ресурсам:
где по смыслу задачи .
Получили задачу линейного программирования.
1.2) Для построения первого опорного плана приведем систему неравенств к системе уравнений:
.
Решим задачу симплексным методом. Переменные х5, х6, х7 будут базисными. Решим систему уравнений относительно базисных переменных:
Функцию цели запишем в виде: .
Полагая, что свободные переменные х1 = 0, х2 = 0, х3 = 0, x4 = 0, получим первый опорный план (0, 0, 0, 0, 110, 126, 114), z = 0, в котором базисные переменные х5 = 110, х6 = 126, х7 = 114, следовательно, товары не продаются и прибыль равна нулю, а ресурсы не используются.
