Задача №11
G=5
N=25
Завод выпускает изделия трех моделей (1, 2 и 3). Для изготовления используются 2 вида ресурсов А и В, запасы которых составляют 400 и 600 единиц. Расход ресурсов на одно изделие каждой модели приведен в таблице:
Расход ресурса на одно изделие
Изделие 1
Изделие 2
Изделие 3
Ресурс А
G=5
3
5
Ресурс В
4
2
7
Трудоемкость изготовления изделия 1 вдвое больше, чем изделия модели 2 и в трое больше, чем модели 3. Численность рабочих завода позволяет выпускать 150 изделий модели 1 (если не одновременно изделия моделей 2 и 3). Анализ условий сбыта показывает, что минимальный спрос на продукцию завода составляет 50, 50 и 30 изделий моделей 1, 2 и 3 соответственно. Удельные прибыли от реализации изделий 1, 2 и 3 составляют N=25, 20 и 50$ соответственно.
Определить объемы выпуска изделий каждой модели, при которых прибыль будет максимальна.
Необходимо:
1) Составить математическую модель задачи целочисленного программирования.
2) Решить задачу симплекс-методом.
3) Произвести постоптимальный анализ.
4) Сформулировать двойственную задачу и от финального решения прямой задач перейти к решению двойственной задачи.
5) Найти целочисленное решение методом отсечения (достаточно пяти итераций).
1) Составим математическую модель задачи целочисленного программирования
Пусть х1 -выпущенное количество изделий модели 1
х2- выпущенное количество изделий модели 2
х3- выпущенное количество изделий модели 3
Хотим найти такой ассортимент выпускаемых товаров, при котором прибыль будет максимальна Прибыль от продаж 1 единицы каждого изделия 25, 20 и 50$ Записываем функцию цели:
Сырье которое используем в ходе производства ограничено запасами, построим ограничения по сырью, используя данные приведенные в таблице:
Численность рабочих позволяет выпускать только 150 единиц товара №1 если не производить в это же время товары 2 и 3.
Трудоемкость товара 1 вдвое больше чем товара 2 и втрое больше чем товара 3
По условию задачи сказано, что минимальный спрос на продукцию завода составляет 50, 50 и 30 изделий моделей 1, 2 и 3 соответственно:
Запишем все в математическую модель задачи:
2. Решим данную задачу симплекс методом
Перепишем условие мат. Модели таким образом, чтоб все ограничения задачи имели один знак. Для классической задачи МАКСИМУМ, знак ограничений должен быть типа «≤»
Для того что б последние 3 неравенства были такие как нам надо, домножаем их на «-1»
Перейдем к каноническому виду, для этого необходимо от неравенств-ограничений перейти к ограничениям-равенствам. Вводим дополнительные переменные. Так как все неравенства типа «≤», то дополнительные переменные вводим со знаком «+»
х1, х2, х3- свободные переменные
х4, х5, х6, х7, х8, х9- базисные переменные
Составим и заполним 1-ую симплексную таблицу
БП C1=25 С2=20 C3=50 C4=0 C5=0 C6=0 C7=0 C8=0 C9=0 Сб Вi A1 А2 A3 A4 A5 A6 A7 A8 A9 1 A4 0 400
5
3 5 1 0 0 0 0 0 2 A5 0 600
4
2 7 0 1 0 0 0 0 3 A6 0 150
1
1/2 1/3 0 0 1 0 0 0 4 A7 0
-50
-1
0
0
0
0
0
1
0
0
5 A8 0 -50
0
-1 0 0 0 0 0 1 0 6 A9 0 -30
0
0 -1 0 0 0 0 0 1 ∆j=W(j)-cj 0
-25
-20 -50 0 0 0 0 0 0
Находим пробное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi
Свободные переменные Базисные переменные
X1=0
X2=0
X3=0
X4=400
X5=600
X6=150
X7=-50
X8=-50
X9=-30
Решение пробное.
Но так как в столбце bi есть отрицательные коэффициенты, то решение не ОПОРНОЕ.
Для решение задачи двойственным симплекс методом для начала необходимо добиться, что б решение было ОПОРНЫМ.
Находим в столбце Bi минимальный отрицательный коэффициент.
Bi=min{bi<0}=min{-50;-50;-30}= -50
Соответствует сразу двум строкам А7 и А8. ............
