Решения задачи планирования производства симплекс методом (стр. 8 из 10)
Все элементы полученной таблицы необходимо разделить на разрешающий элемент asr:
Таблица 3. Итерация №1
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
| X6 | 825/2 | 0 | 15/4 | 5/4 | 3/4 | 5/2 | 1 | 0 | -1/4 | 0 | 0 |
| X7 | 215 | 0 | 3/2 | -1/2 | 7/2 | 1 | 0 | 1 | -1/2 | 0 | 0 |
| X1 | 375/2 | 1 | 1/4 | 3/4 | 1/4 | 1/2 | 0 | 0 | 1/4 | 0 | 0 |
| X9 | 215/2 | 0 | 5/4 | 7/4 | 5/4 | -1/2 | 0 | 0 | -3/4 | 1 | 0 |
| X10 | 615/2 | 0 | 7/4 | 1/4 | 15/4 | 7/2 | 0 | 0 | -1/4 | 0 | 1 |
| Y | 11250 | 0 | -35 | 8 | -30 | -26 | 0 | 0 | 15 | 0 | 0 |
XБ1=(x6, x7, x1, x9, x10)T.
Базис XБ1=(x6, x7, x1, x9, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a92=5/4 определяет необходимость перехода к базису XБ2=(x6, x7, x1, x2, x10)T. Приведем результат пересчета симплекс-таблицы для базиса XБ2.
Таблица 4. Итерация №2.
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
| X6 | 90 | 0 | 0 | -4 | -3 | 4 | 1 | 0 | 2 | -3 | 0 |
| X7 | 86 | 0 | 0 | -13/5 | 2 | 8/5 | 0 | 1 | 2/5 | -6/5 | 0 |
| X1 | 166 | 1 | 0 | 2/5 | 0 | 3/5 | 0 | 0 | 2/5 | -1/5 | 0 |
| X2 | 86 | 0 | 1 | 7/5 | 1 | -2/5 | 0 | 0 | -3/5 | 4/5 | 0 |
| X10 | 157 | 0 | 0 | -11/5 | 2 | 21/5 | 0 | 0 | 4/5 | -7/5 | 1 |
| Y | 14260 | 0 | 0 | 57 | 5 | -40 | 0 | 0 | -6 | 28 | 0 |
Базис XБ2=(x6, x7, x1, x2, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a65=4 определяет необходимость перехода к базису XБ3=( x5, x7, x1, x2, x10)T. Приведем результат пересчета симплекс-таблицы для базиса XБ3.
Таблица 5. Итерация №3
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
| X5 | 45/2 | 0 | 0 | -1 | -3/4 | 1 | 1/4 | 0 | 1/2 | -3/4 | 0 |
| X7 | 50 | 0 | 0 | -1 | 16/5 | 0 | -2/5 | 1 | -2/5 | 0 | 0 |
| X1 | 305/2 | 1 | 0 | 1 | 9/20 | 0 | -3/20 | 0 | 1/10 | 1/4 | 0 |
| X2 | 95 | 0 | 1 | 1 | 7/10 | 0 | 1/10 | 0 | -2/5 | 1/2 | 0 |
| X10 | 125/2 | 0 | 0 | 2 | 103/20 | 0 | -21/20 | 0 | -13/10 | 7/4 | 1 |
| Y | 15160 | 0 | 0 | 17 | -25 | 0 | 10 | 0 | 14 | -2 | 0 |
Базис XБ3=(x5, x7, x1, x2, x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a104=103/20 определяет необходимость перехода к базису XБ4=(x5, x7, x1, x2, x4)T. Приведем результат пересчета симплекс-таблицы для базиса XБ4.
Таблица 6. Итерация №4
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 | X9 | X10 |
| X5 | 3255/103 | 0 | 0 | -73/103 | 0 | 1 | 10/103 | 0 | 32/103 | -51/103 | 15/103 |
| X7 | 1150/103 | 0 | 0 | -231/103 | 0 | 0 | 26/103 | 1 | 42/103 | -112/103 | -64/103 |
| X1 | 15145/103 | 1 | 0 | 85/103 | 0 | 0 | -6/103 | 0 | 22/103 | 10/103 | -9/103 |
| X2 | 8910/103 | 0 | 1 | 75/103 | 0 | 0 | 25/103 | 0 | -23/103 | 27/103 | -14/103 |
| X4 | 1250/103 | 0 | 0 | 40/103 | 1 | 0 | -21/103 | 0 | -26/103 | 35/103 | 20/103 |
| Y | 15463,4 | 0 | 0 | 2751/103 | 0 | 0 | 505/103 | 0 | 792/103 | 669/103 | 500/103 |
Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T.
3.4 Результат решения задачи планирования производства
В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем наложенным ограничениям и обеспечивает максимальную стоимость данного набора (максимум целевой функции f(x)= 60x1+50x2+37x3+45x4+56x5=15463,4 рублей). Таким образом, можно оптимально спланировать объем производства продукции при наличии заданного количества ресурсов: продукции типа A нужно выпустить 147 единиц, продукции типа B – 86 единиц, продукции типа D – 12 единиц, продукции типа E – 31 единицу, а продукцию типа D – для достижения максимальной прибыли в данных условиях производить не выгодно.
При этом ресурсы типа 1, 3, 4, 5 будут использованы полностью, а 11 единиц ресурса типа 2 останутся неизрасходованными.
4. Программа для решения задач ЛП симплекс методом
В процессе выполнения дипломной работы был реализован и отлажен программный интерфейс под ОС Windows XP (также протестирован под Windows Vista), решающий задачи ЛП симплекс методом (в частности поставленную задачу планирования производства).
Программа осуществляет: решение задач ЛП симплекс методом; сохранение и загрузка исходных данных в файл/из файла; вывод решения по шагам; экспорт решения в документ MS word; системный код программы написан в среде объектно-ориентированного программирования С++.
4.2 Графическое представление программы
Главное окно программы «Исходные данные»:
Рис.5 Главное окно программы Simplex: 1 – Кнопки загрузка/сохранение исходных данных в файл. 2 – Число переменных, в нашем случае количество производимой продукции. 3 – Число ограничений, в нашем случае количество запасов ресурсов на складе. 4 – Целевая функция, в нашем случае максимизация. 5 – Система ограничений в форме Такера. 6 – Кнопка для решения задачи и перехода к окну «Решение».
Окно программы «Решение»:
Рис.6 Окно программы Simplex, для просмотра решения по шагам: 1 – Поле для вывода пошагового решения задачи. 2 – Кнопка для экспорта результатов работы программы в документ MS Word.
1 – Определяем число переменных; 2 – Определяем максимизируем или минимизируем целевую функцию; (см. Рис.7)
Рис.7 Работа с программой
3 – Определяем число ограничений; 4 – Определяем знаки неравенств для системы ограничений; 5 – Указываем дополнительные ограничения неотрицательности; (см. Рис.8)
Рис.8 Работа с программой
Приступаем к вводу исходных данных: 6 – поля для ввода коэффициентов целевой функции (в нашем случае это цена единицы продукции типа A,…,E); 7 – поля для ввода запасов каждого ресурса; 8 – поля для ввода набора производимой продукции. Заполнив все поля, приступаем к решению задачи: 9 – нажимаем кнопку «Решить». (см. Рис.9)
Рис.9 Работа с программой
После нажатия кнопки «Решения» программа производит необходимые вычисления и автоматически переходит ко второму окну, в котором отображается пошаговое решение поставленной задачи в виде симплекс таблиц, с указанием необходимых дополнительных данных. А именно: 10 - исходные данные; 11 - система ограничений в форме Такера; 12 - целевая функция; 13 – исходная симплекс таблица; (см. Рис.10)
Рис.10 Работа с программой
14 - разрешающий элемент каждой таблицы, 15 - переход от старого базиса к новому, 16 - количество итераций, 17 - информация об оптимальности решения, 18 – Ответ, в нашем случае максимум целевой функции (максимальная прибыль), 19 – оптимальный набор производимой продукции (количество изделий A,…,E). (см. Рис.11)
Рис.11 Работа с программой
Логическая структура программы решающей задачи ЛП симплекс методом приведена на Рис.12, Рис.13, Рис.14.
Рис.12 Симплекс метод
Рис.13 Поиск r-столбца
Рис.14 Поиск s-строки
Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования производственной деятельности. В этих условиях только научный подход к экономике предприятий позволит обеспечить высокие темпы развития промышленности. Научного подхода требует и решение тактических и стратегических задач.
В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение как в экономических исследованиях и планировании, так и в других задачах. Этому способствует развитие таких разделов математики как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники.
Уже накоплен большой опыт постановки и решения экономических и тактических задач с помощью математических методов. Особенно успешно развиваются методы оптимального управления. Экономика и производство развивается быстро там, где широко используются математические методы.