Оптимизация использования ресурсов методами линейного программирования

Эта прибыль достигается лишь за счет рационального перераспределения ресурсов и соответствующей корректировки плана в связи с увеличением лимита дефицитного ресурса.Задача оптимального распределения топлива между печамиСодержательная постановка задачиПри выплавке стали в металлургических печах, используются различные виды топлива: мазут, природный газ и др. Причем длительность процесса в определенной степени зависит от тепло образовательной (теплотворной) способности топлива. А сама теплотворная способность зависит не только вида и сорта топлива, но и особенностей печи (конструктивных особенностей, износа и др.).Пусть необходимо распределить 4 сорта топлива (мазута) между 4-мя металлургическими печами. Запасы топлива, потребности печей, теплотворная способность Сij (ккал/т)i-го сорта топлива Мi при использовании его в j-ой печи Пj (количество тепловой энергии, выделяемой при сжигании 1т топлива) заданы в таблице(Таблица 2). Найти оптимальное распределение мазута между печами, при котором будет получено максимальное количество теплоты от сжигания всего объема топливаТаблица 2. Исходные данные для задачи оптимального распределенияСорт мазутаПечиЗапасы топливаai, тоннП1П2П3П4М1835963М2475,5640М3653650М445,57447Потребности печейbj, тонн37505073∑ai≤∑bjЛегко видеть, что в такой постановке, данная задача относится к типу транспортных задач линейного программирования: имеются запасы топлива (продукции), которые необходимо распределить между печами (потребителями).Формальная постановка задачиПостроим математическую модель задачи. Введем обозначения: – искомое количествоi-го сорта топлива направляемого в j-й агрегат (i=1,2,3,4;j= 1,2,3,4); – запас i-го сорта топлива (i=1, ...,4); –потребность в топливе j–го агрегата (j= 1,..,4) ; – количество тепла, выделяемого при сжигании 1 тi-го сорта топлива вj-м агрегате. Проверим баланс: = 63+40+50+47 = 200; = 37+50+50+73 = 210.Как мы видим, запасов мазута меньше, чем потребности печей,∑ai≤ ∑bj, т.е. мы имеем открытую задачу с дефицитом топлива.Введем фиктивный сорт топлива M5, запас которого а5 = 10;x5j– количество топлива, недопоставленного в j-й агрегат, (j=1, ...,4). Записываем ограничения по запасам топлива каждого сорта:Далее записываем условия полного удовлетворения потребности каждого агрегата в топливе:Критерий оптимальности – количество тепла, выделившегося при сжигании топлива:Решение задачиДля нахождения решения задачив среде MicrosoftExcel выполним следующие подготовительные действия:1. Внесем необходимые надписи в ячейки А4, B1-E1, A9-E9, A10-A14, H4-K4.Ячейки B10-E14 предназначены для вывода искомых переменных.2. В ячейки B2-E6 введем значения коэффициентов целевой функции.3. В ячейки G10-G14 введем значения, соответствующиеправым частям ограничений по запасам топлива.4. В ячейки B16-E16 введем значения, соответствующие правым частям ограничений по потребностям агрегатов (Приложение 3).После ввода исходных данных необходимо ввести формулу для вычисления значения целевой функции в ячейку G4. В ячейку G4 введем (с использованием мастера функцийfx ) формулу:=СУММПРОИЗВ(B2:E6; B10:E14),которая представляет целевую функцию (Приложение 3).В ячейку F10 введем формулу =СУММ(B10:E10), которая представляет левую часть первого ограничения по запасам топлива. Скопируем формулу, введённую в ячейку F10, в ячейки F11 –F14. Далее в ячейку В15 введем формулу =СУММ(B10:В14), которая представляет левую часть первого по потребностям агрегатов ограничения.Скопируем формулу, введённую в ячейку В15, в ячейки С15, D15 и E15. Для нахождения оптимального решения необходимо выполнить операцию главного меню Данные→Поиск решения. После открытия диалогового окна Параметры поиска решения выполнить следующие действия:В поле с именем Оптимизировать целевую функцию ввести абсолютный адрес ячейки $G$4;Для группы До (Равной) выбрать вариант направления оптимизации – Максимума;Для указания ячеек, отведенных под значения переменных, следует установить курсор в поле Изменяя ячейки переменных, после чего курсором выделить ячейки B10 – E14. При этом в поле Изменяя ячейки появится запись $B$10:$E$14;Для ввода ограниченийв поле В соответствии с ограничениями нажать клавишу Добавить . Появится диалоговое окно Добавление ограничений.В появившемся дополнительном окне в поле Ссылка на ячейки выделить ячейку F10 с записью левой части первого ограничения. В качестве знака ограничения из выпадающего списка (путем нажатия на стрелочку, расположенную справа) выбрать«=».В правом поле записать правую часть ограничения (выделить курсором ячейку G10, в которой находится число 63). В окне Добавление ограничения следует нажать клавишу Добавить. Аналогичным образом задать оставшиеся 8 ограничений.После этого следует нажать клавишу ОК, появится основное диалоговое окно со всеми записанными ограничениями.Далее следует указать на не отрицательность переменных и на линейность решаемой задачи.Для этого в основном диалоговом окне следует поставить галочку Сделать переменные без ограничений неотрицательными, а в поле Выберите метод решениявыбрать Поиск решения линейной задачи симплекс – методом, (в ранних версиях нажать на кнопку Параметры , при этом откроется дополнительноеокно Параметры поиска решения. В полях Линейная модель и Неотрицательные значения нужно установить галочки. После выполнения указанных действийследует нажать кнопкуОК). Для поиска, численного решения следует нажать кнопку Найти решение (Выполнить в ранних версиях Excel). Появится исходная таблица, в которой в ячейках B10:E14 будут записаны оптимальные значения искомых переменных(Приложение 3).Согласно полученного решения, топливо первого сорта следует направлять в четвертый агрегат в количестве 63 т., топливо второго сорта – во второй агрегат – 40 т., топливо третьего сорта следует распределить в количестве 37 т –в первый агрегат, 3 т – во второй, 10 т –в четвертый, топливо 4 сорта распределять в третий агрегат – 47 т. Второй агрегат недополучит 7 т., третий агрегат недополучит 3 т. При сжигании всего топлива при этом будет получено 1473ккал.Решение задачи при условии, что недогруженный агрегат должен полностью получить топливоРассмотрим теперь варианты решение задачи при следующих условиях:во вторую и в третью печь топливо должно быть поставлено в полном объеме.Как изменится математическая постановка с учетом дополнительного условия?Для каждой печи (2 и 3) мы должны один из коэффициентов сi2 (сi3), того вида топлива, который мы хотим ввести, сделать большой положительной величиной. В нашем случае не важно какого, главное, чтобы загрузить печь. Решение задачи для с12=20 и с13=20 приведено в приложении (Приложение 4). Мы видим, что вторая и третья печь полностью загружены топливом, но недогруженной теперь оказалась четвёртая печь.рис.10Список литературыПятецкий В.Е., Литвин И.З., Литвяк В.С. Математические методы моделирования и оптимизации производственно – экономических систем. М.: МИСиС, 2011.Пятецкий В.Е., Литвяк В.С., Литвин И.З., Методы принятия оптимальных управленческих решений. М.: МИСиС, 2014.Кандыбей Е.А Учебно-методическое пособие по дисциплине «Экономико-математические методы» по направлению подготовки бакалавров «Экономика».- М., ИЭАУ, 2012.Афанасьев М.Ю., Суворов Б.Р. Исследование операций вэкономике.-М.: Инфра-М, 2003.Макаров С.И. Экономико - математические методы и модели.- М.: Кнорус, 2007.ПриложенияПриложение 1. Представление исходных данных и результатов решения ЛП в среде Microsoft Excel(прямая задача)Приложение 2. Представление исходных данных и результатов решения ЛП в среде Microsoft Excel(двойственная задача)Приложение 3. Представление исходных данных и результатов решения ЛП в среде Microsoft Excel(транспортная задача)Приложение 4. Представление исходных данных и результатов решения ЛП в среде Microsoft Excel(транспортная задача, дополнительное условие)