Международный школьный научный вестник
Научный журнал для старшеклассников и учителей ISSN 2542-0372

О журнале Выпуски Правила Олимпиады Учительская Поиск Личный портфель

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ИЗ КУРСА ЭКОНОМИКИ

Удалов М.О. 1
1 МОУ "Тверской лицей"
оптимизационное моделирование
симплекс метод
1. Алгоритм и пример симплекс метода [Электронный ресурс]. – Режим доступа: http://www.ikasteko.ru/page/algoritm_simpleks_metoda
2. Исследование информационных моделей. Элективный курс: Учебное пособие / Н.Д. Угринович – М.: БИНОМ. Лаборатория знаний, 2004. – 183 с.
3. Оптимизационные модели в экономике. Способы нахождения оптимальных решений [Электронный ресурс]. – Режим доступа: https://studopedia.ru/7_133687_optimizatsionnie-modeli-v-ekonomike-sposobi-nahozhdeniya-optimalnih-resheniy.html
4. Симплексный метод решения задач линейного программирования [Электронный ресурс]. – Режим доступа: https://studopedia.ru/22_110893_simpleksniy-metod-resheniya-zadach-lineynogo-programmirovaniya.html

В данной работе представлен материал по оптимизационному моделированию в экономике, в процессе которого осуществляется поиск наиболее оптимального пути развития системы с использованием линейного программирования.

Цель данной работы заключается в том, чтобы получить дополнительные знания и навыки по этой теме.

Задача состоят в том, чтобы подобрать соответствующий материал с последующей систематизацией, обобщением и иллюстрацией текста.

Работа состоит из двух частей: теоретической (дано описание информационных оптимизационных моделей в экономике) и практической (приведён пример поиска оптимального решения с использованием табличного процессора MS Excel 10).

Информационные оптимизационные модели

Оптимизационное моделирование

В сфере управления сложными системами (например, в экономике) применяется оптимизационное моделирование, в процессе которого осуществляется поиск наиболее оптимального пути развития системы.

Критериями оптимальности могут быть различные параметры, например, в экономике можно стремиться к максимальному количеству выпускаемой продукции, а можно – к её низкой себестоимости. Оптимальное развитие соответствует экстремальному (максимальному или минимальному) значению выбранного целевого параметра.

Развитие сложных систем зависит от множества факторов (параметров), следовательно, целевой параметр зависит от множества параметров. Выражением такой зависимости является целевая функция.

K = F(X1, X2, …, Xn),

где K – целевой параметр;

X1, X2, …, Xn – параметры, влияющие на развитие системы.

Если целевая функция нелинейная, цель исследования состоит в нахождении экстремума этой функции и определении значений параметров, при которых этот экстремум достигается, иначе поиск оптимального решения осуществляется при наличии определённых ограничений на параметры. Если ограничения на параметры также имеют линейный характер, то такие задачи являются задачами линейного программирования (поиск экстремумов линейной функции, на которую наложены ограничения) [2].

Линейное программирование

Линейное программирование (ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач ЛП следующие:

1. показатель оптимальности L(X) представляет собой линейную функцию от элементов решения X = (x1, x2, … xn). В качестве показателя оптимальности часто выступают экономические показатели: выручка, себестоимость, прибыль и пр.;

2. ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств. Ограничения в экономических задачах могут быть по спросу, по запасам ресурсов, по трудоемкости, по затратам времени и пр.

Основные правила построения оптимизационной модели: число ограничений должно быть больше либо равно числу искомых переменных; в ограничениях левая и правая части должны иметь одинаковые единицы измерения.

Допустимое решение – это совокупность чисел (план) X = (x1, x2, … xn), удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция (ЦФ) принимает свое максимальное (минимальное) значение.

В случае, если количество искомых величин х две, то удобно решение задачи представить в графической форме.

В случае, если количество искомых величин х более двух, то применяют метод перебора всех возможных вариантов с помощью компьютера (в Excel это надстройка “Поиск решения”).

На основе оптимизационных моделей были созданы различные вариации экономических задач:

задача о размещении (ТЗ – транспортная задача) – это задача линейного программирования (ЛП), в которой работы и ресурсы измеряются в одних и тех же единицах. Примером типичной транспортной задачи (ТЗ) является транспортировка продукции, находящейся на складах по предприятиям-потребителям.

распределительная задача (РЗ) линейного программирования (ЛП), в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов [3].

Решение линейных задач симплекс методом

Симплексный метод линейного программирования относится к универсальным методам, обеспечивающим эффективное решение экономических задач. Сущность симплексного метода заключается в нахождении оптимального решения задачи путем последовательного рассмотрения и анализа её допустимых базисных решений (рис. 1) [4, 1].

Рис. 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. Построение и исследование оптимизационной модели в табличном процессоре MS Excel 2010

Надстройка “Поиск решения”

Возможности электронных таблиц Microsoft Excel 10 не ограничиваются вычислениями по формулам и построением диаграмм и графиков. Задачи оптимизационного моделирования можно решать с помощью надстройки электронных таблиц Поиск решения.

Процедура поиска решения позволяет найти оптимальное значение формулы, содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки [2].

Компьютерная модель

Установим надстройку Поиск решения, войдя в приложение Microsoft Excel 2010.

1. В появившемся диалоговом окне ввести команду [Файл - Параметры – Надстройки]. В окне Параметры Excel щёлкнуть по кнопке Перейти и поставить галочку Поиск решения < OK > .

2. Ячейки B2, C2, D2 выделить для хранения значений параметров X1, X2 и X3.

В ячейку B4 ввести формулу =B2+C2+D2.

В ячейку B7 ввести формулу вычисления количества заготовок типа А:

=10*B2+3*C2+8*D2.

В ячейку B8 ввести формулу вычисления количества заготовок типа Б:

=3*B2+6*C2+4*D2 (рис. 2).

Рис. 2. Таблица с введёнными формулами

Исследование модели

Для поиска оптимального набора значений параметров, который соответствует минимальному значению целевой функции, воспользуемся надстройкой Поиск решения.

В табличном процессоре Microsoft Excel 10 ввести команду [Данные – Поиск решения]. В диалоговом окне Поиск решения установить:

• адрес целевой ячейки;

• вариант оптимизации значения целевой ячейки (максимизация, минимизация или подбор значения);

• адреса ячеек, значения которых изменяются в процессе поиска решения (в которых хранятся значения параметров);

• ограничения (типа “равно” для ячеек, хранящих количество заготовок, и типа “больше или равно” для параметров) (рис. 3) и нажать на кнопку Параметры.

Рис.3. Диалоговое окно Поиск решения

В окне Параметры установить галочку на Показывать результаты итераций < OK >.

Во вновь открывшемся диалоговом окне Параметры поиска решения выбрать метод решения: Поиск решения линейных задач симплекс методом и нажать на кнопку Найти решение.

В окне Показать предварительное решение периодически нажимать на кнопку Продолжить до тех пор, пока не появится окно Результаты поиска решения (рис. 4, табл. 2, рис. 5).

Рис. 4. Результаты итераций

Таблица 2. Показатели итераций на листе приложения

 

 

 

 

 

 

Рис. 5. Диалоговое окно Результаты поиска решения

Таким образом, для изготовления 500 деталей А и 300 деталей Б из 70 листов материала 20 листов необходимо раскроить по первому, 20 листов – по второму и 30 листов – по третьему варианту (табл. 2).

Для получения Отчётов в окне Результаты поиска решения (рис. 5) последовательно выделять Результаты, Устойчивость, Пределы и нажимать на <ОК>.

Во вновь открывшемся диалоговом окне Показать предварительное решение периодически нажимать на кнопку Продолжить до тех пор, пока не появится ссылка отчёта внизу листа приложения.

Заключение

Таким образом, данные модели основаны на математическом аппарате теории программирования (“планирование”). Математическое программирование – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются как в экономических, так и в других системах для решения так называемых распределительных задач. Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности [3].

Типичным примером такой задачи является рассмотренная в проекте организация выпуска продукции на оборудовании различных типов.

Программное обеспечение

1. Операционная система Windows 10

2. Приложение Microsoft Office Excel 2010

3. Приложение Microsoft Office Word 2010


Библиографическая ссылка

Удалов М.О. РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ИЗ КУРСА ЭКОНОМИКИ // Международный школьный научный вестник. – 2022. – № 1. ;
URL: https://school-herald.ru/ru/article/view?id=1502 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674