Разработка модели и решение задачи линейного программирования (на примере задачи оптимального раскроя)

ВВЕДЕНИЕ 2
1. ТЕОРИЯ И МЕТОДЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ЗАДАЧИ РАСКРОЯ МАТЕРИАЛА 4
1.1. Общая математическая формулировка решаемой экономико-математической задачи 4
1.2. Методы решения задачи 7
2. ЗАДАЧА ОПТИМАЛЬНОГО РАСКРОЯ МАТЕРИАЛА 9
2.1. Вербальная постановка задачи 9
2.2. Разработка экономико-математической модели задачи (прямой и двойственной). 10
2.2.1. Математическая модель постановки прямой задачи 10
2.2.2.Математическая модель постановки двойственной задачи. 11
2.3. Решение поставленной задачи симплексным методом 12
2.4. Решение поставленной задачи с помощью средств EXСEL (надстройки «Поиск решения», «Анализ данных»). 15
2.5. Интерпретация результатов расчетов и выработка управленческого решения (с учетом решения двойственной задачи). 20
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 22

Решим прямую задачу с помощью средств Exсel.На листе Exсelсформируем модель для поиска оптимального решения.Для этого на рабочем листе Exсel выделим несколько областей:- область в которую будут выводиться значения неизвестных переменных ;- ячейка, в которой будет рассчитываться значение целевой функции . В данную ячейку введем формулу для расчета ;- область для ввода ограничений. В каждую ячейку области введем формулу для расчета ограничений (без правой части). Для поиска решения зададим команду Данные – Поиск решения. В окне «Поиск решения» установим следующие параметры:- в графе «Оптимизировать целевую функция» укажем адрес целевой ячейки;- выберем «Минимум»;- в графе «Изменяя ячейки переменных» введем интервал, в который должны быть выведены значения ;- в графе «В соответствии с ограничениями»с помощью кнопки «Добавить» введем ограничения со ссылками на ячейки, в которых были введены формулы ограничений, а также добавить ограничения на целочисленность значений ;- поставим галочку «Сделать переменные без ограничений неотрицательными»;- в выпадающем списке «Выберите метод решения» выберем «Поиск решения линейных задач симплекс-методом».Нажмем кнопку «Найти решение» (рис. 1).Рис. 1 Поиск решения задачи с помощью пакета «Поиск решения» в MiсrosoftExсelПосле этого будет найдено оптимальное решение:.Определим искомый объем сырья в штуках по формуле:Выполним проверку решения.Для этого найдем произведение матрицы и вектора. Числа в строках полученного вектора должны быть большеили равны заданным объемам рудстоек. Действительно, эта проверка дала положительный результат.Выполним перемножение массивов и, найдем сумму значений полученного вектора. Эта сумма действительно равна 0, т.е. значению В отчете по результатам (рис. 2) приведены значения неизвестных и целевой функции, а также данные о выполнении ограничений. В графе Статус указаны связанные и несвязанные переменные.MiсrosoftExсel 14.0 Отчет о результатахЛист: [Заказ331249.xlsx]прямая задачаОтчет создан: 22.12.2014 11:02:58Результат: Решение найдено. Все ограничения и условия оптимальности выполнены.Модуль поиска решенияПараметры поиска решенияЯчейка целевой функции (Минимум)ЯчейкаИмяИсходное значениеОкончательное значение$B$16F= Отходы Сj00Ячейки переменныхЯчейкаИмяИсходное значениеОкончательное значениеЦелочисленное$B$12:$B$15ОграниченияЯчейкаИмяЗначение ячейкиФормулаСостояниеДопуск$B$18ограничение1 Отходы Сj3000$B$18>=3000Привязка0$B$19ограничение2 Отходы Сj3000$B$19>=2000Без привязки1000$B$20ограничение3 Отходы Сj2000$B$20>=2000Привязка0$B$12:$B$15=Целочисленное     Рис. 2Отчет по результатам решенияРешим двойственную задачу с помощью средств Exсel.На листе Exсelсформируем модель для поиска оптимального решения.Для этого на рабочем листе Exсel выделим несколько областей:- область в которую будут выводиться значения неизвестных переменных ;- ячейка, в которой будет рассчитываться значение целевой функции . В данную ячейку введем формулу для расчета ;- область для ввода ограничений. В каждую ячейку области введем формулу для расчета ограничений (без правой части). Для поиска решения зададим команду Данные – Поиск решения. В окне «Поиск решения» установим следующие параметры:- в графе «Оптимизировать целевую функция» укажем адрес целевой ячейки;- выберем «Максимум»;- в графе «Изменяя ячейки переменных» введем интервал, в который должны быть выведены значения ;- в графе «В соответствии с ограничениями»с помощью кнопки «Добавить» введем ограничения со ссылками на ячейки, в которых были введены формулы ограничений;- поставим галочку «Сделать переменные без ограничений неотрицательными»;- в выпадающем списке «Выберите метод решения» выберем «Поиск решения линейных задач симплекс-методом».Нажмем кнопку «Найти решение» (рис. 3).Рисунок 3 – Поиск оптимального решениядвойственной задачи в пакете «Поиск решения» в MiсrosoftExсel.После этого будет найдено оптимальное решение:Выполним проверку решения.Для этого найдем произведение матрицы и вектора. Числа в строках полученного вектора должны быть не меньше заданных величин прибыли от реализации готовой продукции. Действительно, эта проверка дала положительный результат.Выполним перемножение массивов и , найдем сумму значений полученного вектора. Эта сумма действительно равна 0, т.е. значению 2.5. Интерпретация результатов расчетов и выработка управленческого решения (с учетом решения двойственной задачи).Посколькурешения прямой и двойственной задач равны между собой (), то найденный план искомой задачи действительно является оптимальным.Таким образом получили, что ЛПБ нужно заключить договор с леспромхозамина объем поставок древесного сырья равный 4000 шт., чтобы выполнить заказ угольных шахт с минимальными отходами древесиныЗАКЛЮЧЕНИЕВ результате выполнения данной работы были изучены математические модели и методы решения задач линейного программирования, получены практические навыки решения данного типа задач на примере задачи оптимизации раскроя материала.Получены следующие результаты:1)Изучена задача оптимизации раскроя материала и методы ее решения.2) Разработана математическая модель задачи оптимизации раскроя материала на примере лесоперерабатывающей промышленности.3) Разработаны математические методы решения поставленной задачи оптимизации раскроя материала. 4) Реализованы предложенные алгоритмы планирования производственной программы.СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫАбчук В.А. Экономико-математические методы «Союз» Санкт-Петербург 1999-318 с.Антипина Н.М., Протасов Ю.М., Юров В.М. Методы математического программирования. – М.: МГОУ, 2013.Афанасьев М. Ю., Матюшок В.М., Багриновский К. А. Прикладные задачи исследования операций. - М.: ИНФРА-М. Учебное пособие.- М.: Инфра-М, 2006. (Электронная библиотека Znanium.сom). Кремер Н.Ш. Исследование операций в экономике. – М.: ЮНИТИ, 2010.Ляшенко И.Н., Карагодова Е.А. Линейное и нелинейное программирование. «Вища школа», 1975. - 369 с.Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач / И.В. Орлова. - 2-e изд., испр. и доп. - М.: Вузовский учебник: НИЦ Инфра-М, 2012. (Электронная библиотека Znanium.сom). Шапкин А.С., Мазаева Н.П. Математические методы и модели исследования операций: Учебник. – 2-е изд., перераб. и доп. – М.: Дашков и К, 2005. – 400 с.ШелобаевС.И. Математические методы и модели в экономике, финансах, бизнесе: Учеб. пособие для вузов. – 2-е изд., перераб. и доп. – М.: ЮНИТИ, 2005. – 400 с.