91143

Понятие математического программирования

Лекция

Информатика, кибернетика и программирование

Базисом математического программирования является понятие целевой функции в общем случае от n переменных. xi xn а оптимальность решения основывается на методах отыскания экстремальных значений этой целевой функции mx Z или min Z среди множества возможных значений xi. Данная задача не имеет решения для произвольной функции F и разрешима только для отдельных классов функции F. Это в частности методы поиска экстремума функции F для одной переменной xi.

Русский

2015-07-13

457 KB

2 чел.

Лекция 1

 Понятие математического программирования

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

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

Возьмем пример: человек вышел утром из дому, чтобы ехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.

Однако возьмем другой пример. Допустим, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где разместить остановки? И так далее.

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

В теории оптимизации изучаются:

1) построение математических моделей задач оптимизации;

2) поиск экстремальных значений функций;

3) проблемы установления признаков оптимальности;

4) методы вычисления оптимальных решений.

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

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

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

Z=F(x1, x2, …., xi, xn)

а оптимальность решения основывается на методах отыскания экстремальных значений этой целевой функции max Z или min Z среди множества возможных значений xi.

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

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

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

И задача оптимизации формулируется следующим образом:

имеется система ограничений

 обеспечивающие экстремум функции

Z=F(х1х2, ..., хn).

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

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

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

  •  задачи линейного программирования;
  •  задачи целочисленного программирования;
  •  задачи нелинейного программирования.

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

Целевая функция

+….+CnXn

Ограничения

……………………

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

Если ставится условие, целочисленности переменных Xi, то это уже задачи целочисленного программирования.

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

 Формулировка задачи линейного программирования

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

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

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Основным понятием ЛП является понятие целевой функции

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

 (2.1.2)

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

при условии, что   (2.1.3)

Где X - это множество допустимых значений

На переменные Х как правило накладываются ограничения

и условия неотрицательности:

 Графическое решение задачи линейного программирования.

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

Графическое изображение неравенства Х  7

Данная прямая разделяет плоскость на три множества точек: точки, для которых х = 7, т.е. точки, лежащие на самой прямой; точки, для которых х < 7, область слева от прямой; и точки, для которых х > 7, т.е. точки, принадлежащие области, лежащей справа от прямой. Последнее множество нас не интересует. Область, не подлежащую рассмотрению, обычно принято заштриховывать.

Предположим, что х + у 10. Какую часть плоскости описывает данное неравенство? Схема поиска ответа на этот вопрос аналогична схеме, используемой в предыдущем примере. Во-первых, проведем прямую х + у = 10. Обратимся к графику. Как и в предыдущем примере, проведенная прямая разделяет плоскость на три множества точек: точки, для которых х + у = 10, принадлежащие прямой; точки, для которых х + у < 10, принадлежащие области, лежащей ниже прямой; и точки, для которых х + у > 10, принадлежащие области, лежащей выше указанной прямой.

Графическое изображение неравенства x + y ≤ 10

Полезным приемом при определении недопустимой области на графике является следующая процедура. Необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением. Если неравенство не выполняется, то точка является недопустимой и принадлежит, следовательно, недопустимой области. Удобной для использования при подстановке в неравенство точкой является начало координат. Подставим х = у = 0 в неравенство х + у 10. Получим 0 + 0 10. Данное утверждение является верным, следовательно, начало координат — допустимое решение, и недопустимой областью является часть плоскости, лежащая по другую сторону прямой.

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


Пример

Задача раскроя. Из листов материала размером 6м*13м нужно выкроить заготовки двух типов в таких количествах:

Тип заготовки

Размер заготовки

Число штук

A

4м*5м

800

B

2м*3м

400

Израсходовав при этом возможно меньше материала.

Варианты раскроя

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

Тип заготовки

Варианты раскроя

1

2

А

3

2

В

1

6

Целевая функция

F=x1+x2------------------>MIN

Система ограничений

x1,x2, >= 0

Строим график ограничений

При Х1=0;  2Х2=800;  Х2=400

При Х2=0;  3Х1=800;  Х1=266

При Х1=0;  6Х2=400;  Х2=66,6

При Х2=0;  1Х1=400;  Х1=400

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

F =x1 + x2 = const 

Для этого выбирается точка внутри многоугольника {300,100}. При этом линия уровня

Х1+Х2=400

При движении линии уровня в сторону уменьшения целевой функции последней разрешенной точкой является точка А. Координаты этой точки есть решение системы уравнений

Решение Х1=250

 Х2=25

Т.е необходимо взять 250+25 стандартных листов размером 13*6 метров и 250 листов раскроить по варианту 1, а 25 листов по варианту 2. Это оптимальное решение

Проверка

3*250+2*25=800

1*250+6*25=400

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

 Анализ чувствительности при решении задач линейного программирования

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

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

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

Пример. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: Х и Y. Завод располагает фондом рабочего времени в 4000 чел.-ч. в неделю. Для производства одной детали типа X требуется 1 чел.-ч, а для производства одной детали типа Y — 2 чел.-ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа Х и 1750 деталей типа Y в неделю. Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30$., а от производства одной детали типа Y — 40$.?

Целевая функция Р - прибыль

Р=30х+40у в ф.ст.-------MAX

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

Фонд рабочего времени:    1 х + 2 у  4000 чел.-ч

Производственная мощность:   х   2250 деталей

 у  1750 деталей

Металлические стержни:   2 х + 5 у  10000 кг

Листовой металл:    5 х + 2 у  10000 кг

Условие неотрицательности:   х, у  0

В соответствии с ранее рассмотренной методикой ограничения отобразим на графике.

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

Р=30х+40у

Произвольно выбираются значения для х и у

Их можно выбрать в соответствии с ограничениями

Х=1000

У=1000

Подставив в целевую функцию имеем

Р=30*1000+40*1000=7000

Т Е

7000=30Х+40У

При Х=0 У=7000/40=175

При У=0 Х=7000/30=233

Оптимальное решение соответствует точке А с координатами являющиеся решением уравнений

5 х + 2 у  10000

1 х + 2 у  4000

Координаты точки А  (Х=1500 и У=1250). Т.е. для получения максимальной прибыли при данных ограничениях необходимо изготавливать в неделю 1500 деталей типа Х и 1250 деталей типа У. При этом прибыль составит

30*1500+40*1250=95000$

Все другие комбинации значений Х и У дадут меньшее значение прибыли.

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

1.На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции ?

Введем понятие

Ресурс лимитирующий - это прямые определяющие оптимальную точку А. В данном случае это ЛИСТЫ и ФОНД ВРЕМЕНИ

 Анализ воздействия изменений в обеспечении лимитирующим ресурсом

Если появляется дополнительное количество лимитирующего ресурса, то оптимальное решение может быть улучшено. При увеличении лимитирующего ресурса по ЛИСТАМ прямая 5х+2у=11000 12000 и т.д. перемещается параллельно самой себе в сторону от центра координат. Очевидно, что ее перемещение ограничено прямой х=2250. И новое оптимальное решение будет соответствовать точке В.

Координаты данной точки определяются решением 2-х уравнений

Х=2250

Х+2у=4000

Откуда у=875

Это соответствует х=2250 и у=875.  Т.е в неделю необходимо изготавливать 2250 деталей Х и 875 деталей У. Однако это потребует закупки 5*2250+2*850=13000 ЛИСТОВ вместо первоначальных 10000 ЛИСТОВ. При этом прибыль увеличится до величины 30*2250+40*875=102500$, т.е возрастет на 102500-95000=7500$, что на 7,8% больше базового варианта.

Однако необходимо принять во внимание, что изменение оптимального решения приведет к улучшению значения целевой функции только в том случае, если сумма дополнительных издержек по обеспечению дополнительным количеством ресурса не превышает сумму прибыли, полученной в результате его использования. Т.е. приобретение дополнительных 3000 ЛИСТОВ не должно увеличить расходы более чем на 7500$.

Если рассмотреть изменение лимитирующего ресурса ФОНД ВРЕМЕНИ, то прямая Х+2У соответствующая ФОНДУ ВРЕМЕНИ перемещается параллельно самой себе до точки В. Точка В лежит на пересечении прямых 2Х+5У=10000 и 5Х+2У=10000. Координатами точки В

2Х+5У=10000

5Х+2У=10000

Являются Х=1430 и У=1430. Т.е. ограничения на ФОНД ВРЕМЕНИ становятся Х+2У=1430+2*1430=4290. При этом прибыль станет равной 30*1430+40*1430=100100,что на 100100-95000=5100$, что на 5,3% больше базового варианта

Однако необходимо принять во внимание, что изменение оптимального решения приведет к улучшению значения целевой функции только в том случае, если сумма дополнительных издержек по обеспечению дополнительным количеством ресурса не превышает сумму прибыли, полученной в результате его использования. Т.е. увеличение ФОНДА ВРЕМЕНИ по затратам не должно превысить 5100$.

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


 

А также другие работы, которые могут Вас заинтересовать

63207. Спадкове право 27.55 KB
  Мета: розкрити основні поняття спадкового права; познайомити учнів з особливостями спадкового права з умовами відкриття спадщини й винесення права на спадщину; виховувати в учнів правову культуру та правову свідомість.
63211. Узагальнення знань за темою «Київська Русь у другій половині XI — першій половині XIII ст.» 380 KB
  Мета: повторити та узагальнити матеріал, вивчений із теми «Київська Русь у другій половині XI — першій половині XIII ст.», підготуватися до уроку тематичного оцінювання; розвивати в учнів уміння аналізувати матеріал, робити висновки, виділяти головне, удосконалювати навички роботи з історичними джерелами...
63214. Сім’я і шлюб 31.36 KB
  Мета: ознайомити учнів з основами сімейного права; залучити їх до роботи з текстом Сімейного кодексу; підвести учнів до розуміння важливості знання та дотримання норм сімейного права; виховувати повагу до людей старшого покоління.