XIV Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ИЗ КУРСА ЭКОНОМИКИ
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В данной работе представлен материал по оптимизационному моделированию в экономике, в процессе которого осуществляется поиск наиболее оптимального пути развития системы с использованием линейного программирования.
Цель данной работы заключается в том, чтобы получить дополнительныезнания и навыки по этой теме.
Задача состоят в том, чтобы подобрать соответствующий материал с последующей систематизацией, обобщением и иллюстрацией текста, а также практического решения конкретной задачи в табличном процессоре MicrosoftExcel 10 с использованием надстройки Поиск решения и симплекс метода.
Основная часть
Глава 1. Информационные оптимизационные модели
§ 1.Оптимизационное моделирование
В сфере управления сложными системами (например, в экономике) применяется оптимизационное моделирование, в процессе которого осуществляется поиск наиболее оптимального пути развития системы.
Критериями оптимальности могут быть различные параметры, например, в экономике можно стремиться к максимальному количеству выпускаемой продукции, а можно – к её низкой себестоимости. Оптимальное развитие соответствует экстремальному (максимальному или минимальному) значению выбранного целевого параметра.
Развитие сложных систем зависит от множества факторов (параметров), следовательно, целевой параметр зависит от множества параметров. Выражением такой зависимости является целевая функция.
K = F(X1, X2, …, Xn),
где K – целевой параметр;
X1, X2, …, Xn – параметры, влияющие на развитие системы.
Если целевая функция нелинейная, цель исследования состоит в нахождении экстремума этой функции и определении значений параметров, при которых этот экстремум достигается, иначе поиск оптимального решения осуществляется при наличии определённых ограничений на параметры. Если ограничения на параметры также имеют линейный характер, то такие задачи являются задачами линейного программирования (поиск экстремумов линейной функции, на которую наложены ограничения) [2].
§ 2. Линейное программирование
Линейное программирование(ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач ЛП следующие:
показатель оптимальности L(X) представляет собой линейную функцию от элементов решения X = (x1, x2, … xn). В качестве показателя оптимальности часто выступают экономические показатели: выручка, себестоимость, прибыль и пр.;
ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств. Ограничения в экономических задачах могут быть по спросу, по запасам ресурсов, по трудоемкости, по затратам времени и пр.
Основные правилапостроения оптимизационной модели: число ограничений должно быть больше либо равно числу искомых переменных; в ограничениях левая и правая части должны иметь одинаковые единицы измерения.
Допустимое решение– это совокупность чисел (план) X = (x1, x2, … xn), удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция (ЦФ) принимает свое максимальное (минимальное) значение.
В случае, если количество искомых величин х две, то удобно решение задачи представить в графической форме.
В случае, если количество искомых величин х более двух, то применяют метод перебора всех возможных вариантов с помощью компьютера (в Excel это надстройка “Поиск решения”).
На основе оптимизационных моделей были созданы различные вариации экономических задач:
задача о размещении (ТЗ – транспортная задача) – это задача линейного программирования (ЛП), в которой работы и ресурсы измеряются в одних и тех же единицах. Примером типичной транспортной задачи (ТЗ) является транспортировка продукции, находящейся на складах по предприятиям-потребителям.
распределительная задача (РЗ)линейного программирования (ЛП), в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов [3].
§ 3.Решение линейных задач симплекс методом
Симплексный метод линейного программирования относится к универсальным методам, обеспечивающим эффективное решение экономических задач. Сущность симплексного метода заключается в нахождении оптимального решения задачи путем последовательного рассмотрения и анализа её допустимых базисных решений (рис. 1) [4, 1].
Рис. 1. Блок-схема решения распределительной задачи симплекс методом
Практическая часть
Глава 2. оптимизационное моделирование в экономике
Рассмотрим в качестве примера экономического моделирования поиск вариантов оптимального раскроя листов материала на заготовки определённого размера.
§ 1.Содержательная постановка задачи
В ходе производственного процесса из листов материала получают заготовки деталей 2-х типов А и Б тремя различными способами, при этом количество получаемых заготовок при этих способах различны. В таблице на пересечении строк и столбцов записаны количества заготовок типов А и Б при соответствующих способах раскроя (табл. 1).
Таблица 1. Исходные данные
|
Типы заготовки |
Способы раскроя |
||
|
1-й способ |
2-й способ |
3-й способ |
|
|
А |
10 |
3 |
8 |
|
Б |
3 |
6 |
4 |
Необходимо выбрать оптимальное сочетание способов раскроя, для того чтобы получить 500 заготовок типа А и 300 заготовок типа Б при расходовании наименьшего количества листов материала.
§ 2.Формальная модель
Параметрами, значения которых требуется определить, являются количество листов материала, которые будут раскроены различными способами:
X1 – количество листов, раскроенное способом 1;
X2 – количество листов, раскроенное способом 2;
X3 – количество листов, раскроенное способом 3;
Целевая функция, выражающая количество листов материала, которое надо минимизировать, примет вид:
F = X1 + X2 + X3.
Ограничения накладываются требуемыми количествами заготовок типов А и Б, тогда с учётом количества заготовок, получаемых различными способами, должны выполняться два равенства:
10 * X1 + 3 * X2 + 8 * X3 = 500;
3 * X1 + 6 * X2 + 4 * X3 = 300.
Кроме того, количество листов не могут быть отрицательными, поэтому должны выполняться неравенства:
X1 0; X2 0; X3 0.
Таким образом, необходимо найти удовлетворяющие ограничениям значения параметров, при которых целевая функция принимает минимальное значение [2].
Глава 3. Построение и исследование оптимизационной модели в табличном процессоре MSExcel 2010
§ 1.Надстройка “Поиск решения”
Возможности электронных таблиц Microsoft Excel 10 не ограничиваются вычислениями по формулам и построением диаграмм и графиков. Задачи оптимизационного моделирования можно решать с помощью надстройки электронных таблиц Поиск решения.
Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки [2].
§ 2.Компьютерная модель
Установим надстройку Поиск решения, войдя в приложение MicrosoftExcel 2010.
1. В появившемся диалоговом окне ввести команду [Файл - Параметры – Надстройки].В окне Параметры Excel щёлкнуть по кнопке Перейти и поставить галочку Поиск решения < OK > (рис.1, рис.2).
Рис. 1. Диалоговое окно Параметры Excel
Рис. 2. Диалоговое окно Надстройки
2. Ячейки B2, C2, D2 выделить для хранения значений параметров X1, X2 и X3.
В ячейку B4 ввести формулу =B2+C2+D2.
В ячейку B7 ввести формулу вычисления количества заготовок типа А:
=10*B2+3*C2+8*D2.
В ячейку B8 ввести формулу вычисления количества заготовок типа Б:
=13*B2+6*C2+4*D2(рис. 3, рис. 4).
Рис. 3. Таблица с введёнными формулами
Рис. 4. Таблица с начальными значениями данных
§ 3.Исследование модели
Для поиска оптимального набора значений параметров, который соответствует минимальному значению целевой функции, воспользуемся надстройкой Поиск решения.
В табличном процессоре Microsoft Excel 10 ввести команду [Данные – Поиск решения]. В диалоговом окне Поиск решения установить:
адрес целевой ячейки;
вариант оптимизации значения целевой ячейки (максимизация, минимизация или подбор значения);
адреса ячеек, значения которых изменяются в процессе поиска решения (в которых хранятся значения параметров);
ограничения (типа “равно” для ячеек, хранящих количество заготовок, и типа “больше или равно” для параметров) (рис. 5) и нажать на кнопку Параметры.
Рис.5. Диалоговое окно Поиск решения
В окне Параметры установить галочку на Показывать результаты итераций < OK > (рис. 6).
Рис. 6. Диалоговое окно Параметры
Во вновь открывшемся диалоговом окне Параметры поиска решения выбрать метод решения: Поиск решения линейных задач симплекс методом и нажать на кнопку Найти решение (рис. 7).
Рис.7 Диалоговое окно Параметры поиска решения
В окне Показать предварительное решение периодически нажимать на кнопку Продолжить до тех пор, пока не появится окно Результаты поиска решения (рис. 8, табл. 1, рис. 9).
Рис. 8. Результаты итераций
Таблица 1. Показатели итераций на листе приложения
Рис. 9. Диалоговое окно Результаты поиска решения
Таким образом, для изготовления 500 деталей А и 300 деталей Б из 70 листов материала 20 листов необходимо раскроить по первому, 20 листов – по второму и 30 листов – по третьему варианту.
Для получения Отчётов (рис. 12, рис. 13, рис. 14) в окне Результаты поиска решения (рис. 10) выделять Результаты, Устойчивость, Пределы и нажимать на <ОК>.
Рис. 10. Создание отчётов
Во вновь открывшемся диалоговом окне Показать предварительное решение (рис. 11) периодически нажимать на кнопку Продолжить до тех пор, пока не появятся ссылка отчёта внизу листа приложения.
Рис.11. Промежуточные результаты создания отчётов
Рис. 12. Отчёт по результатам
Рис. 13. Отчёт по устойчивости
Рис. 14. Отчёт по пределам
Заключение
Таким образом, данные модели основаны на математическом аппарате теории программирования(“планирование”). Математическое программирование – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются как в экономических, так и в других системах для решения так называемых распределительных задач. Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности [3].
Типичным примером такой задачи является рассмотренная в проекте организация выпуска продукции на оборудовании различных типов.
Список использованных источников и литературы
Алгоритм и пример симплекс метода [Электронный ресурс]. – Режим доступа: http://www.ikasteko.ru/page/algoritm_simpleks_metoda
Исследование информационных моделей. Элективный курс: Учебное пособие / Н.Д. Угринович – М.: БИНОМ. Лаборатория знаний, 2004. – 183 с.
Оптимизационные модели в экономике. Способы нахождения оптимальных решений [Электронный ресурс]. – Режим доступа: https://studopedia.ru/7_133687_optimizatsionnie-modeli-v-ekonomike-sposobi-nahozhdeniya-optimalnih-resheniy.html
Симплексный метод решения задач линейного программирования [Электронный ресурс]. – Режим доступа: https://studopedia.ru/22_110893_simpleksniy-metod-resheniya-zadach-lineynogo-programmirovaniya.html
Программное обеспечение
Операционная система Windows 10
Приложение Microsoft Office Excel 2010
Приложение Microsoft Office Word 2010