Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Цель: освоить симплекс-метод, приобрести навыки использования информационных систем управления и управленческого учета для решения задач оптимизации
Задача 1 (Ассортиментная задача)
Цех кондитерской фабрики вырабатывает три ассортиментные группы конфет, условно обозначенные M1, М2, М3 /в ед./.
Для их производства используются основные виды ресурсов /сырья/ трех видов, условно названных П1, П2, П3 /в ед./.
Расход каждого ресурса на производство единицы продукции является заданной величиной, определяется по рецептуре и обозначается символами а11, a12..., а33, где а - норма расхода, первая подстрочная 1 - номер ресурса, вторая подстрочная 1, 2, 3 - номер ассортиментной группы конфет.
Наличие каждого ресурса для производства всех, групп конфет принимается как известная величина и обозначается символами в1, в2, в3.
Прибыль на продукцию также принимается как известная величина и обозначается символами с1, с2, с3.
Перечисленные параметры являются величинами известными и выражаются в единых единицах измерения, кроме прибыли. Прибыль или другой какой показатель, являющийся критерием оптимальности, выражается в единицах измерения дохода /например, прибыли/, получаемого от производства единицы продукции в денежном или другом каком-нибудь выражении.
Поскольку решение задачи заключается в поиске такого плана производства, который обеспечивал бы в принятых условиях наибольший доход, принимаются те величины, которые являются неизвестными и обозначающими количества каждой группы конфет, включаемых в план производства: х1 для M1; х2 для М2; х3 для М3.
Экономико-математическая модель в символическом виде.
Система ограничений
Целевая функция /суммарный доход/ F = = мах
Условия неотрицательности неизвестных
Символическая модель, наполненная численной информацией, будет иметь следующий вид:
Прибыль от реализации выпускаемой продукции должна быть максимальной, то есть
Решение задачи.
Для решения задачи симплексным методом неравенства преобразуются в эквивалентные равенства путем добавления в каждое неравенство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:
Коэффициенты пря неизвестных записываются в симплексной таблице, в которой выполняются расчеты и отражаются полученные результаты.
Исходная таблица.
сj | p0 | x0 | ||||||
x1 | x2 | x3 | x4 | x5 | x6 | |||
x4 | ||||||||
x5 | ||||||||
x6 | ||||||||
Zj - Cj | -28 | -49 | -9 |
В столбцах таблицы записывают: в первом (Сj) - прибыль единицы продукции, которая вводится в план выпуска; во втором (Р0) – неизвестные, включаемые в план; в третьем (Х0) - – свободные величины; в остальных - коэффициенты при неизвестных уравнений. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.
В нижней строке (целевой) записываются получаемые расчетным путем показатели: в столбце х0 - суммарная прибыль планового выпуска, в остальных столбцах - прибыль единицы продукции с отрицательным знаком.
В последних трех столбцах коэффициенты при дополнительных неизвестных, равные единице, расположены по диагонали. Эта часть таблицы, называемая единичной подматрицей, необходима для вычислительных и аналитических целей.
При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделяется. В нашем примере таким столбцом будет х0, имеющий в целевой строке наибольшую по модулю величину - 49.
1-ая итерация
сj | p1 | x0 | x1 | x2 | x3 | x4 | x5 | x6 |
x2 | 1/2 | 5/28 | 1/25 | |||||
x5 | 21/2 | 5/4 | -3/4 | |||||
x6 | -1/14 | -3/14 | ||||||
Zj - Cj | -7/2 | -1/4 | 7/4 |
Затем элементы столбца x0 (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отношением принимается за ключевую и также для удобства выделяется. В нашем случае 700/I4 = 25, 630/21= 30, 162/6 = 27. Наименьшее отношение 25 имеет срока х4, она и будет ключевой. Ключевой элемент 28.
Далее элементы таблицы преобразуются и записываются в новую таблицу. Первоначально преобразуют элементы ключевой строки путем деления их на ключевой элемент. Преобразованные элементы записывают в том же самом месте.
В столбцах Р0 и Сj занимают место вводимая в план неизвестная x2 с прибылью 49 (итерация 1-я). Остальные элементы преобразуются по следующему правилу:
- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столбца;
- соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключевой момент;
- частное от деления вычитают из значения элемента, которое он имел до преобразования, и полученный результат будет преобразованным элементом, который записывается в новую таблицу в том же самом месте.
Следуя этому правилу, преобразование элементов столбца х0 будет:
630 -
162 -
0 -
Включение на первой итерации в план неизвестной х2 (выпуска продукции П вида) обеспечит сумму прибыли 1225 руб.
Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент - 7/2. Он находится в столбце х1, который принимается за ключевой, а ключевой строкой будет х6 (25:1/2=50; 105:21/2=10; 12:3=4). Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу.
2-я итерация
сj | p2 | x0 | x1 | x2 | x3 | x4 | x5 | x6 |
x2 | 4/21 | 1/14 | -1/6 | |||||
x5 | 3/2 | -7/2 | ||||||
x1 | -1/42 | -1/14 | 1/3 | |||||
Zj - Cj | -1/3 | 3/2 | 7/6 |
В полученном на 2-й итерации плане ключевым столбцом будет х3, ключевой строкой х5 (23:4/21=121; 63:3/2=42, при отрицательном элементе отношение не определяется), ключевым элементом 3/2. Элементы ключевой строки преобразуются делением их на ключевой элемент. Остальные элементы преобразуются рассмотренным выше или более упрощенным способом, смысл которого заключается в следующем:
- для преобразуемого элемента в его столбце уже преобразованный элемент ключевой строки (в новой таблице), а в его строке - еще не преобразованный элемент ключевого столбца (в предыдущей таблице);
- найденные элементы перемножаются и полученный результат вычитается из значения элемента, которое он имел до преобразования.
3-я итерация
сj | p2 | x0 | x1 | x2 | x3 | x4 | x5 | x6 |
x2 | 1/14 | -8/23 | 5/18 | |||||
x5 | 2/3 | -7/3 | ||||||
x1 | -1/14 | 1/63 | 5/18 | |||||
Zj - Cj | 3/2 | 2/9 | 7/18 |
Этот новый результат является преобразованным элементом и записывается в новой таблице в том же самом месте. По этому правилу преобразуем элементы столбца х6. Дня элемента -1/6 в его столбце уже преобразованный элемент ключевой строки в новой таблице -7/3. Этот элемент умножается на еще не преобразованный элемент ключевого столбца 4/21. Полученный результат вычитается из преобразуемого элемента и записывается в новой таблице:
-1/6 - (-7/3 * 4/21) = 5/18
Так же и для двух других элементов:
1/3 – [(-7/3) - (-1/42)] = 5/18; 7/6 – [(-7/3) * (-1/3)] = 7/18
Остальные элементы преобразованы в таком же порядке и записаны в таблицу 3.
В последней таблице целевая строка имеет только положительные элементы. Это значит, что составленный план оптимален и дальнейшее улучшение его невозможно.
Как видно из таблицы, оптимальный план предусматривает выпуск продукции П1 5 ед. (х1 = 5), П2 вида 15 ед. (х2 = 15), П1 вида 42 ед. (х3 = 42). Дополнительные неизвестные в план не вошли, следовательно, х4 = 0, х5 = 0, х6= 0. Подставив значения неизвестных в уравнения, получим:
14*5 + 28*15 + 5*42 + 0 = 700
21*5 + 21*15 + 6*42 + 0 = 630
6*6+ 6*15 + 1*42 + 0 = 162
F = 28*5 + 49*15 + 9*42 = 1253
При постановке задачи были приняты ограничения только по запасам сырья. Другие ограничения не учитывались. Но если бы в плане требовалось предусмотреть ассортиментные соотношения (например, выпуск продукции I вида должен быть не меньше выпуска продукции II вида, т.е. х1 х2), то в систему неравенстве добавляется это ограничение:
Эта система преобразуется в симплексные уравнения и решается по изложенным правилам.
Проведем анализ оптимального плана.
а) Запасы сырья трех видов используются полностью без остатка, так как х4 = х5 = х6 = 0.
б) Рассмотрим элементы матрицы.
Элементы столбца х1 свидетельствуют: если запасы муки будут увеличены на I ед. (х4 = 1), то выпуск продукции II вида увеличится на 1/14 ед. (х4 = 15 + 1/14), выпуск продукции III вида не изменится, выпуск продукции I вида уменьшится на 1/14 ед. (5 - 1/14). Сумма прибыли увеличится на 1,5 руб.
Элементы столбца х5 показывают, что увеличение запасов сахара на I ед. (х5 = I) позволит увеличить выпуск продукции III вида на 2/3 ед., I вида на 1/63 ед., прибыль на 2/9 руб. и снизить выпуск продукции II вида на 8/23 ед. Изменения объемов производства и суммы прибыли вызовет и увеличение запасов жира (см.столбец х6). Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.
Элементы целевой строки оптимального плана называются двойственными сценками, которые определяют величину изменения прибыли при изменении запасов сырья на I ед.
Дата публикования: 2015-01-10; Прочитано: 174 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!