Учебный проект "Решение оптимизационных задач методами линейного программирования"

УЧЕБНЫЙ ПРОЕКТ

«РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

МЕТОДАМИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ»

2017 – 2018 учебный год

10 класс

Руководитель проекта: Бруханская Елена Александровна, учитель математики

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

Задачи:

1. Теоретическая часть исследования

2. Постановка и решение задачи минимизации транспортных расходов

3. Постановка и решение задачи максимизации прибыли

1. Теоретическая часть

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

     Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и другие). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.

     В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

     Наилучшие в определенном смысле решения задач принято называть оптимальными. Без использования принципов оптимизации в настоящее время не решается ни одна более или менее сложная проблема.

     Постановка задачи на оптимизацию и ее решение включает в себя ряд этапов:

- выбор и обоснование цели оптимизации;

- согласование цели с имеющимися возможностями, т.е. учет ограничений;

- реализация способа достижения цели при учете ограничений.

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

  В таких задачах, как правило, выделяют два аспекта:

     1) Ограничения - это то, что ограничивает наши решения. Как правило, ограничения записываются в виде равенств или неравенств.

     2) Целевая функция - это некоторое числовое значение, которое показывает, насколько хорошо мы решили задачу. Целевую функцию, нужно «минимизировать», если необходимо достичь наименьшего значения величины, например, найти самый короткий маршрут или уменьшить расходы. Иногда наоборот, целевую функцию необходимо максимизировать, сделать как можно больше - например, если целевая функция это прибыль предприятия от продажи товаров. Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.

     Как правило, такие задачи приходят к нам именно из жизни. Среди самых распространенных задач оптимизации, пришедших из жизни можно выделить следующие.

·         Производственная задача - существует некоторое предприятие, которое может выпускать некоторые изделия. На то, чтобы их выпустить, необходимы различные ресурсы. Задано, сколько и каких ресурсов необходимо для каждого изделия, задано, сколько ресурсов у нас имеется, и задано, сколько предприятие выручит за продажу произведенных изделий. Необходимо выбрать, какие изделия, и в каком количестве выпускать, чтобы прибыль предприятия была максимальной.

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

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

·         Задача о назначениях - существует некоторое количество людей, и некоторое количество работ, которые необходимо выполнить. Задано, какую стоимость нужно будет заплатить каждому человеку за выполнение каждой работы. Необходимо выбрать, какому человеку какую работу дать, чтобы все работы были выполнены, и необходимо было заплатить как можно меньше

·         Задача коммивояжера - существует некоторое количество городов, и указаны все расстояния между городами. Некому «коммивояжеру» необходимо посетить все города по одному разу (не заходя в один город дважды), при этом ему нужно передвигаться как можно меньше

·         Задача о ранце - существует некий ранец заданного объема. Также существует набор предметов, для каждого из которых задан их объем, и стоимость. Необходимо так наполнить ранец, чтобы все предметы в него влезли по объему, и их стоимость была максимальной

     Задачи математического программирования делятся на два больших класса:

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

     2. Если в задаче либо ограничения, либо целевая функция (либо и то, и другое) выражены в каком-либо другом виде, то данная задача называется задачей нелинейного программирования.

     Первые постановки задач линейного программирования были сформулированы известным советским математиком Л. В. Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

     Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

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

     Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.

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

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

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

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

Основные этапы решения оптимизационной задачи:

1.      Постановка задачи (сбор исходной информации, составление математической модели)

2.      Решение задачи (выбор метода решения, выполнение вычислений)

3.      Анализ решения

2. Задача минимизации транспортных расходов

     2.1. Постановка задачи.

     Основные методы решения  распределительных  задач, в  частности  линейного  программирования, построены  на  допущении, что  объёмы, имеющихся  в  наличии ресурсов (а_i), требуемые  объёмы (b_j )  и  затраты  (с_i,j) точно  известны.

     В нашем случае транспортная  задача  ставится  следующим  образом: имеется  три  пункта  отправления (базы) А₁, А₂, А_3, на которых  сосредоточены  запасы  однородного  товара  в  количестве  соответственно  250, 400 и 350  условных единиц. Имеется  пять  пунктов потребления  В₁, В₂, В₃, В₄ и В₅,  подавшие  заявки  соответственно  на 300, 160, 220, 180 и 140 единиц  товара. Известны  стоимости  С_i,j   перевозки  единицы   товара    от  каждого  пункта  отправления  А_i   до  каждого   пункта  назначения  В_j

   Требуется  составить  такой  план  перевозок   (откуда, куда  и  сколько  единиц  поставить), чтобы

     - вывезти весь хранящийся на базах запас товара;

     - все  заявки  были  выполнены.

     2.2. Решение задачи

     Построим математическую модель транспортной задачи.

     Обозначим через x_ij количество товара, направляемого из пункта А_i в пункт В_j (i = 1,2,3; j = 1,2,3,4,5). Таким образом, в задаче имеется 3 x 5  оптимизируемых переменных, и план в транспортной задаче имеет вид

     Составим уравнения, определяющие множество допустимых планов. План х = (х₁₁, х₁₂,…, х₃₅) является допустимым, если он обеспечивает вывоз всего хранящегося на базах товара:

,

и удовлетворяет заявки всех магазинов:

,

где все оптимизируемые переменные х_ij ≥ 0.

     Построим критериальную функцию.

     Из двух допустимых планов транспортной задачи лучшим считается тот, которому соответствуют меньшие транспортные издержки (общая стоимость перевозки товаров из мест хранения в места потребления). Таким образом, критериальной функцией является функция:

Е(х) = с₁₁х₁₁ + с₁₂ х₁₂  + с₁₃х₁₃ + с₁₄х₁₄ + с₁₅х₁₅.

Получили следующую задачу математического программирования:

Е(х) → min

Условия  транспортной  задачи  зададим транспортной  таблицей.

	В1	В2	В3	В4	В5	Запасы аi
А1	9	15	35	20	7	250
А2	15	35	12	11	6	400
А3	16	19	40	15	25	350
Заявки bi	300	160	220	180	140

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

	В1	В2	В3	В4	В5	Запасы аi
А1	9 110	15	35	20	7 140	250
А2	15 0	35	12 220	11 180	6	400
А3	16 190	19 160	40	15	25	350
Заявки           bj	300	160	220	180	140

План перевозок х₁ = (110,0,0,0,140,0,0,220,180,0,190,160,0,0,0) или в матричной форме:

                                            х =     .

Стоимость плана х₁:

Е₁(х) = 9*110 + 7*140 + 12*220 + 11*180 + 16*190 + 19*160 = 12 670.

Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов B_i к пунктам A_j  по минимальной стоимости C_j,i.

	В1	В2	В3	В4	В5	Запасы аi
А1	9 250	15	35	20	7	250
А2	15 50	35	12 220	11 130	6	400
А3	16	19 160	40	15 50	25 140	350
Заявки           bj	300	160	220	180	140

План перевозок х₂ = (250,50,0,0,0,160,0,220,0,0,130,50,0,0,140) или в матричной форме:

                                                 .

Стоимость плана х₂:

Е₂(х) = 9*250 + 15*50 + 19*160 + 12*220 + 11*130 + 15*50+ 25*140 = 14 360.

     Способ минимальной стоимости по всей таблице аналогичен предыдущим способам. Анализ стоимости перевозки проводим сразу же и по C_i,j  и по С_ji.

	В1	В2	В3	В4	В5	Запасы аi
А1	9 250	15	35	20	7	250
А2	15	35	12 80	11 180	6 140	400
А3	16 50	19 160	40 140	15	25	350
Заявки           bj	300	160	220	180	140

План перевозок х₃ = (250,0,0,0,0,0,0,80,180,140,50,160,140,0,0) или в матричной форме:

                                                 .

Стоимость плана х₃:

Е₃(х) = 9*250 + 16*50 + 19*160 + 12*80 + 40*140 + 11*180 + 6*140 = 15 470

     План, составленный способами минимальных стоимостей, обычно близок к оптимальному решению. В нашем примере общие затраты на транспортировку по плану, составленному первым способом Е₁(х) = 12 670, по второму  Е₂(х) = 14360, по третьему Е₃(х) = 15 470.

     Следовательно, решив данную задачу, получаем оптимальное решение, при котором  значение целевой функции равно 12 670.

3. Задача максимизации прибыли

3.1. Постановка задачи

     При продаже услуг А и В используется три вида ресурсов R₁, R₂, R₃. При продаже услуги А по цене 3 условные единицы и услуги В по цене 4 условные единицы используется три вида ресурсов R₁, R₂, R₃.

     Для продажи одной единицы услуги А требуется две единицы ресурса R₁, четыре единицы ресурса R₂ и две единицы ресурса R₃. Для продажи одной единицы услуги В – одна единица, пять единиц и четыре единицы ресурсов R₁, R₂ и R₃ соответственно. Обеспеченность торговых предприятий этими ресурсами: 120 единиц ресурса R₁, 280 единиц ресурса R₂ и 200 единиц ресурса R₃.

	Услуги
Ресурсы	А	В	Запас
R1	2	1	120
R2	4	5	280
R3	2	4	200
Цена	3	4

3.2. Решение задачи симплекс-методом

     Пусть Х₁ и Х₂ запланированный объем продажи услуг А и В, Е(Х) - искомая целевая функция, которую необходимо максимизировать.

Х₁ ≥ 0, Х₂ ≥ 0, Е(X) ≥ 0.

     Из таблицы   следует,   что   для   продажи   Х₁   единиц   услуги вида А необходимо 2Х₁   единиц   первого   ресурса,   4Х₁ – второго,  2Х₁ – третьего ресурса. Аналогично, для продажи Х₂ единиц услуги В –  Х₂ – первого, 5Х₂ – второго,  4Х₂ – третьего ресурса.

2Х₁ +  Х₂ ≤ 120,

4Х₁ + 5Х₂ ≤ 280,

2Х₁ + 4Х₂ ≤ 200,

Е(х)_max  = 3Х₁ + 4Х₂.

     Получили следующую математическую модель оптимизационной задачи:

     Введем дополнительные переменные Y₁, Y₂, Y₃ – остатки ресурсов R₁, R₂, R₃. Тогда исходные ограничения, записанные в виде неравенств, можно представить в виде равенств, прибавляя остаточную переменную к левой части ограничений: 

     Линейная модель, построенная для нашей задачи и приведенная к стандартной форме, имеет следующий вид: максимизировать

Е(Х)  = 3Х₁ + 4Х₂ + 0Y₁ + 0Y₂ + 0Y₃

при ограничениях

Х₁ ≥ 0, Х₂ ≥ 0, Y₁ ≥ 0 ,Y₂ ≥ 0 ,Y₃ ≥ 0.

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

     Представим целевую функцию и ограничения модели в стандартной форме: Е – 3Х₁ – 4Х₂ – 0Y₁ – 0Y₂ – 0Y₃ = 0.

     В качестве начального пробного решения используем решение системы уравнений, в которой Х₁ = Х₂ = 0. Тогда Y₁ = 120, Y₂ = 280, Y₃ = 200. Величина Е равна нулю, так как и Х₁ и Х₂ имеют нулевое значение.

Полученные результаты удобно представить в виде таблицы:

Базис	E	Х1	Х2	Y1	Y2	Y3		Решение
E	1	- 3	- 4	0	0	0	0	Е = 0
Y1	0	2	1	1	0	0	120	Y1 = 120
Y2	0	4	5	0	1	0	280	Y2 = 280
Y3	0	2	4	0	0	1	200	Y3 = 200

     Значение целевой функции Е = 3*0 + 4*0 + 0*120 + 0*280 + 0*200  равно нулю.

     Поиск нового решения осуществим методом Гаусса – Жордана.

Базис	E	X1	Х2	Y1	Y2	Y3		Решение
E	1	- 3	- 4	0	0	0	0	Е
Х2	0	2	1	1	0	0	120	Х2 = 120
Y2	0	4	5	0	1	0	280	Y2 = – 320
Y3	0	2	4	0	0	1	200	Y3 = – 280

Получили недостоверное решение.

Переходим к следующим итерациям.

     Используя данные, содержащиеся в симплекс-таблицах для оптимального решения, основные результаты можно представить в следующем виде: 

Переменные	Оптимальные значения
Х1	20
Х2	40
Еmax	220

Е_max = 3Х₁ + 4Х₂ + 0Y₁ + 0Y₂ + 0Y₃ = 220.

       Таким образом, максимальная прибыль от продажи двух видов услуг А и В в заданных условиях равна 220 условным единицам.

Заключение

     В процессе выполнения исследовательской работы «Решение оптимизационных задач методами линейного программирования»  мною изучены задачи на поиск оптимальных решений. Получены практические навыки решения некоторых задач методами линейного программирования. В результате решения задач были найдены оптимальные решения по уменьшению транспортных расходов и увеличению прибыли.

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

     Моя исследовательская деятельность была направлена на получение новых знаний; работа над собственно проектом - это результат моих усилий для получения практического результата. Данная исследовательская работа позволила мне проверить свои возможности в ситуациях, максимально приближенных к профессиональной деятельности, удовлетворила познавательные интересы в выбранной сфере деятельности, привила вкус к теории и практике исследовательской работы.

     Подводя итоги исследованию, можно сказать, что цель работы достигнута и получены следующие результаты:

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

2)      Решена задача минимизации транспортных расходов

3)      Решена задача максимизации прибыли

      4)   Расширены знания о существующих видах оптимизационных задач и способах их решения..

      Практической значимостью данной работы является привлечение внимания к изучению методов задач на поиск оптимальных решений в общеобразовательной школе при подготовке к ЕГЭ по математике профильного уровня (задача №17).

Краткое описание документа:

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

Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и другие). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.