Tw-city.info

IT Новости
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Оптимизационная задача линейного программирования

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

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Программа для чистки и оптимизации компьютера

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

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

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

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

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

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

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

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

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

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

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

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

В нашем случае транспортная задача ставится следующим образом: имеется три пункта отправления (базы) А 1 , А 2 , А 3, на которых сосредоточены запасы однородного товара в количестве соответственно 250, 400 и 350 условных единиц. Имеется пять пунктов потребления В 1 , В 2 , В 3 , В 4 и В 5 , подавшие заявки соответственно на 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 оптимизируемых переменных, и план в транспортной задаче имеет вид

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

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

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

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

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

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

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

Оптимизационная задача линейного программирования

На этом шаге мы рассмотрим некоторые понятия линейного программирования.

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

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича «Математические методы организации и планирования производства». Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода).

Линейное программирование — это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций (ИО), включая целочисленное, нелинейное и стохастическое программирование.

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

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

(1)

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

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f(Х) не ограничена сверху на допустимом множестве W.

Читать еще:  Программы для оптимизации реестра windows 7

Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

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

  • показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2, . , xn);
  • ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

(2)
(3)
(4)
(5)

При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной xj. Т.е. в разных ситуациях одна единица j-го товара будет приносить разный доход. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.

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

На следующем шаге рассмотрим построение модели линейного программирования на примере .

Оптимизационная задача линейного программирования

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

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

Средство обеспечения САПР – это совокупность однотипных компонентов. Выделяют следующие виды обеспечения САПР: техническое, математическое, программное, лингвистическое, информационное и организационное. Эффективность и производительность работы САПР в наибольшей степени зависит от его математического обеспечения. Математическое обеспечение (МО) САПР состоит из математических моделей, методов и алгоритмов, необходимых для решения задач автоматизированного проектирования, которые помогают справиться с поставленной задачей. Выделяют три основные задачи, рассматриваемые в математическом обеспечении САПР: задача анализа, задача оптимизации и задача синтеза [5].

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

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

В процессе принятия оптимальных решений теоретически наиболее эффективны методы математического программирования: линейное, нелинейное, динамическое программирование и т.д. [4].

Рассмотрим пример решения задачи линейного программирования (ЛП) для нахождения оптимальных условий изготовления изделий. Приведем решение с использованием симплекс-метода. Данный метод имеет ряд преимуществ: возможность найти оптимальное значение целевой функции, план выпуска каждого изделия, информацию о степени использования и резерве переменных.

Допустим, предприятие выпускает два вида изделий: А и В. Для их изготовления используется 3 вида станков (С1, С2, С3). Длительность обработки каждого изделия: на станке типа С1 изделий А – 12; изделий В – 4 единицы; на станке типа С2 изделий А – 4, изделий В – 4 единицы; на станке типа С3 изделий А – 3, изделий В – 12 единиц. Прибыль от реализации одного изделия А составляет 30 единиц, В – 40 единиц. Рабочее время станка С1 – 300 единиц, С2 – 120 единиц, С3 – 252 единиц. Необходимо определить такой план выпуска продукции А и В, чтобы прибыль предприятия была максимальна.

Решение данной задачи осуществляется с помощью симплекс-метода. Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом. [3].

Математическая модель данной задачи имеет вид:

где х1 – количество изделий А, х2 – количество изделий В.

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

Построим исходную симплекс-таблицу (табл. 1).

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

Решение происходит в три этапа:

  1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
  2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
  3. Решение симплексным методом;
  • Решение онлайн
  • Видеоинструкция
  • Оформление Word

Переход от задачи минимизации целевой функции к задаче максимизации

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

Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x1 + 2x2 — 2x3 → min при ограничениях:
4x1 + 3x2 — x3≤10
— 2x2 + 5x3≥3
x1 + 2x3=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x4; во втором неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
4x1 + 3x2-1x3 + 1x4 + 0x5 = 10
0x1-2x2 + 5x3 + 0x4-1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = — x1 — 2x2 + 2x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

Калькулятор симплекс-метода

Выполнено действий: 54

Как пользоваться калькулятором

  • Задайте количество переменных и ограничений
  • Введите коэффициенты целевой функции
  • Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
  • Выберите тип решения
  • Нажмите кнопку «Решить»

Что умеет калькулятор симплекс-метода

  • Решает основную задачу линейного программирования
  • Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
  • Работает с произвольным количеством переменных и ограничений

Что такое симплекс-метод

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

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

Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c1·x1 + c2·x2 + . + cn·xn

Ограничение — условие вида a1·x1 + a2·x2 + . + an·xn v b , где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x1 . xn.

Алгоритм решения основной задачи ЛП симплекс-методом

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

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

Формирование начального базиса

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

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

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

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x6
Столбец 4 является частью единичной матрицы. Переменная x4 входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x5 , предварительно разделив третью строку на 2.
Симплекс-таблица

Ссылка на основную публикацию
Adblock
detector