Статья:

Пример решения задачи линейного программирования

Конференция: CIX Студенческая международная научно-практическая конференция «Молодежный научный форум»

Секция: Технические науки

Выходные данные
Шмальц Т.А. Пример решения задачи линейного программирования // Молодежный научный форум: электр. сб. ст. по мат. CIX междунар. студ. науч.-практ. конф. № 40(109). URL: https://nauchforum.ru/archive/MNF_interdisciplinarity/40(109).pdf (дата обращения: 25.02.2024)
Лауреаты определены. Конференция завершена
Эта статья набрала 0 голосов
Мне нравится
Дипломы
лауреатов
Сертификаты
участников
Дипломы
лауреатов
Сертификаты
участников
на печатьскачать .pdfподелиться

Пример решения задачи линейного программирования

Шмальц Татьяна Александровна
студент, Технический институт (филиал) Северо-Восточный федеральный университет имени М.К. Аммосова в г. Нерюнгри, РФ, г. Нерюнгри
Самохина Виктория Михайловна
научный руководитель, канд. пед. наук, зав. кафедры МиИ, Технический институт (филиал) Северо-Восточный федеральный университет имени М.К. Аммосова в г. Нерюнгри, РФ, г. Нерюнгри

 

Математическое программирование является разделом математики, который исследует многомерные экстремальные задачи управления и планирования и разрабатывает методы их решения [3].

Математическое программирование ориентировано на решение задач о нахождении минимумов и максимумов функции, области значений аргументов которой ограничены системой равенств (каноническая модель) или неравенств (неканоническая модель). Функция F(x), оптимальное значение которой необходимо найти, называется целевой функцией, а дополнительные условия называются системой ограничения задачи.

Задача математического программирования является линейной, если целевая функция F(x) линейная, а система ограничений состоит из линейных уравнений или неравенств. Раздел математического программирования, описывающий методы решения таких задач, называется линейным программированием. Задача относится к нелинейному программированию, если функция F(x) или хотя бы одно из уравнений или неравенств из системы ограничений нелинейно [1].

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

К экономическим примерам задач линейного программирования относятся: задача производственного планирования, задача о смесях, задача  о раскрое, транспортная задача [3].

Рассмотрим транспортную задачу. Транспортная задача характеризуется тем, что в ней производится перевозка однородного груза из пунктов A к пунктам B, распределенная таким образом, что затраты материальных или временных ресурсов необходимых для доставки минимальны.

Решим пример транспортной задачи. Имеется пять поставщиков сырья, производящих: A1 - 140, A2 - 120, A3 - 110, A4 - 180, A5 - 150 тонн сырья в день. Переработку этого сырья осуществляют три фабрики, перерабатывающих: B1 - 160, B2 - 220, B3 - 170 тонн сырья в день.

Транспортные затраты перевозки сырья от поставщиков до фабрик составляют 300 денежных единиц за тонну на километр. Расстояние от поставщиков до фабрик приведено в таблице.

Таблица.

Расстояние от поставщиков до фабрик, в км

Поставщики

Фабрики

B1

B2

B3

A1

18

20

36

A2

31

14

19

A3

27

17

13

A4

44

37

32

A5

35

30

15

 

Требуется найти с помощью надстройки «Поиск решения» в Microsoft Excel оптимальное распределение поставок сырья от поставщиков до перерабатывающих фабрик, при котором совокупные транспортные издержки будут минимальны.

Для начала необходимо составить математическую модель. В задаче требуется определить минимальное значение целевой функции:

при выполнении условий:

Проверим тип транспортной задачи. Так как сумма объема производства сырья у пяти поставщиков больше, чем производственные возможности трех фабрик переработки, то есть: 140 + 120 + 110 + 180 + 150 > 160 + 220 + 170, то модель задачи открытая, то есть решение найти нельзя. Модель необходимо привести к закрытому типу [2]. Если производится больше сырья, чем потребляется, то необходимо добавить фиктивную фабрику, производственная возможность которой составит (140 + 120 + 110 + 180 + 150) – (160 + 220 + 170) = 150 тонн сырья в день.

После введения фиктивной фабрики задача становится закрытой, и её математическая модель будет иметь вид:

при выполнении условий:

Внесем имеющиеся данные в Excel. В ходе применения надстройки «Поиск решения» в программе должны заполниться значения, характеризующие количество тонн сырья, перевозимое от каждого поставщика к каждой фабрике (от 0 т.). На основе этих сведений заполняются следующие поля: суммарный план перевозки из пунктов производства и оптимальный план перевозок высчитываются как суммы соответствующих ячеек; общая стоимость перевозок (значение целевой функции) определяется как сумма произведений значений расстояния и транспортных затрат (300 д.е.) с объемами перевозок, то есть формула целевой функции примет вид: СУММПРОИЗВ(B4:E8*300; B13:E17) [4]. Результаты поиска решения отображены на рисунке.

 

Рисунок. Оптимальное распределение поставок сырья на фабрики

 

В результате решения задачи была получена минимальная общая стоимость перевозок сырья на фабрики по переработке сырья - 2844000 денежных единиц. При этом перевозка сырья на фабрику B1 осуществляется от поставщиков A1 (140 ед.) и A4 (20 ед.), на фабрику B2 - от поставщиков A2 (120 ед.) и A3 (100 ед.), на фабрику B3 - от поставщиков A3 (10 ед.), A4 (10 ед.) и A5 (150 ед.) и на фиктивную фабрику B4 - от поставщика A4 (150 ед.).

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

 

Список литературы:
1. Анисимова Н.П., Ванина Е.А. Линейное программирование: учеб.-метод. пособие. СПб.: НИУ ВШЭ, 2012. 70с.
2. Болотникова О.В., Тарасов Д.В., Тарасов Р.В. Линейное программирование: транспортные и сетевые модели: учеб. пособие. Пенза: Изд-во ПГУ, 2016. 88 с.
3. Киселева Э.В., Соловьева С.И. Математическое программирование (линейное программирование): учеб. пособие. Новосибирск: НГАСУ, 2002. 146 с.
4. Сигал И.Х., Иванова А.П. Транспортная задача: мет. указания. М.: МГУПС (МИИТ), 2015. 80 с.