Математический расчет объема выпуска продукции (стр. 1 из 4)
Задача №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=0X2=0X3=0 | X4=400X5=600X6=150X7=-50X8=-50X9=-30 |
Решение пробное.
Но так как в столбце bi есть отрицательные коэффициенты, то решение не ОПОРНОЕ.
Для решение задачи двойственным симплекс методом для начала необходимо добиться, что б решение было ОПОРНЫМ.
Находим в столбце Bi минимальный отрицательный коэффициент.
Bi=min{bi<0}=min{-50;-50;-30}= -50
Соответствует сразу двум строкам А7 и А8. Одна из этих строк будет разрешающей.
Для того что б определиться какую из двух строк выбрать в качестве разрешающей, для каждой найдем разрешающий столбец, а затем проверим при замене какой пары (разрешающая строка + разрешающий столбец) изменение функции цели будет больше (ту пару и будем менять)
1) А7- разрешающая строка
Ищем разрешающий столбец по правилу:
(так как среди оценочной строки имеются отрицательные оценки плана (задача максимизации), то среди отрицательных коэффициентов аij разрешающей строкивыбирается разрешающий элемент аrs для которого
соответствует столбцу А1Если заменим А1—А7 то функция цели изменится на:
2) А8- разрешающая строка
соответствует столбцу А2Если заменим А2—А8 то функция цели изменится на:
В первом случае изменение функции больше, поэтому выбираем пару А1-А7 меняем вектора местами и переходим к новой симплекс-таблице по правилу:
Переходим к новой симплекс таблице по следующему правилу:
1. все элементы разрешающей строки делим на разрешающий элемент
2. заполняем базисные столбцы
3. все остальные элементы симплекс таблицы находим по формуле:
| БП | 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 | 150 | 0 | 3 | 5 | 1 | 0 | 0 | 5 | 0 | 0 |
| 2 | A5 | 0 | 400 | 0 | 2 | 7 | 0 | 1 | 0 | 4 | 0 | 0 |
| 3 | A6 | 0 | 100 | 0 | 1/2 | 1/3 | 0 | 0 | 1 | 1 | 0 | 0 |
| 4 | A1 | 25 | 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 | 1250 | 0 | -20 | -50 | 0 | 0 | 0 | -25 | 0 | 0 | ||
Новое решение
| Свободные переменные | Базисные переменные |
| X2=0X3=0X7=0 | X1=50X4=150X5=400X6=100X8=-50X9=-30 |
Решение все еще не опорное, так как все еще есть bi<0
Находим разрешающую строку:
Bi=min{bi<0}=min{-50;-30}= -50
Соответствует строке А8
Разрешающий столбец:
соответствует столбцу А2Меняем А2—А8
Переходим к новой симплекс таблице:
| БП | 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 | 0 | 0 | 0 | 5 | 1 | 0 | 0 | 5 | 3 | 0 |
| 2 | A5 | 0 | 300 | 0 | 0 | 7 | 0 | 1 | 0 | 4 | 2 | 0 |
| 3 | A6 | 0 | 75 | 0 | 0 | 1/3 | 0 | 0 | 1 | 1 | 1/2 | 0 |
| 4 | A1 | 25 | 50 | 1 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 |
| 5 | A2 | 20 | 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 | 2250 | 0 | 0 | -50 | 0 | 0 | 0 | -25 | -20 | 0 | ||
Новое решение
| Свободные переменные | Базисные переменные |
| X3=0X7=0X8=0 | X1=50X2=50X4=0X5=300X6=75X9=-30 |
Решение все еще не опорное, так как все еще есть bi<0