XIV Аттетков и др. Методы оптимизации (1081420), страница 6
Текст из файла (страница 6)
В данном случае и целевая функция, и ограничения линейны относительно парамегаров оптимизации х з 1 = 1, и,. Поэтому рассмотренная задача оптимального планирования выпуска продукции является задачей линейноео программирования. Пример 1.12 (транспортная задача). Пусть необходимо составить план перевозок некоторого товара с т складов в и магазинов так, чтобы затраты на эти перевозки были минимальными. Предположим, что на г'-м складе, г = 1, ш, имеется а; единиц товара, а г-й магазин, 1' = 1, и, сделая заказ на б единиц этого товара, причем стоимость его перевозки с г-го склада в 1-й магазин равна с, .
Обозначим через хг планируемое количество товара, перевозимое с г-го склада в 1-й магазин, тогда стоимость его перевозки составит е, х, Общие затраты на перевозки -- это сумма затрат на перевозки со всех складов во все магазины. Поэтому оптимальный план перевозок соответствует минимуму целевой функции т в Я = ~~г ~~г гл;хг. — + гага !ив Задачи овгииааьного вчанированил что должно быть достигнуто выбором тп значений т,, ) О, которые в данном случае являя>тся параметрами оптимизации. Но при этом необходимо обеспечить потребности магазинов, т.е.
должны быть выполнены ограничения типа равенства т яг! ю=! у =1,п. Однако с любого склада нельзя вывезти товара больше, чем там его находится. Следовательно, должны быть выполнены ограничения типа неравенства Отметим, что сформулированная задача оптимизации, отно- сящаяся к классу задач линейного программирования, имеет решение, если сумма заказов магазинов не превышает суммар- ного запаса товара на всех складах, т.е. п чп Ьу < ~! а!. 1=! Пример 1.13 (задача о диете).
Рассмотрим задачу построения оптимального рациона питания. Обозначим: и число видов пищевых продуктов; т число видов питательных веществ; а; -- число единиц ю;го питательного вещества в единице у-го продукта; б,, - ежегодная потребность в г-м питательном веществе; с стоимость единицы у-го продукта. Выясним, сколько единиц каждого пищевого продукта нужно употребить за рассматриваемый период (в данном случае за год) таким образом, чтобы, обеспечив потребности в каждом питательном веществе, затратить минимальное количество денег.
40 1. ЗАДА ЧИ ОПТИМИЗАЦИИ т Назовем рационом вектор х = (х1 хз ... х„), где х ежегодное потребление 1-го пищевого продукта. Речь идет., таким образом, о построении рациона минимальной стоимости. Математически эта задача может быть сформулирована следующим образом: минимизировать целевую функцию (1.15) при ограничениях аИху>б1, г=1гт; Е 1 (1.16) х > О, 1 = 1,п. ~д,х; >б, (1.17) г=1 где г1гь г =1,гг, цена единицы г-го изделия, а б заданный нижний уровень эффективности.
При этих ограничениях необходимо минимизировать нелинейную целевую функцию Пример 1.14. Предположим, что предприятие может производить н изделий, причем затраты на производство х, еди- НИЦ г-ГО ИЗДЕЛИЯ СОСтаВЛЯЮт Я(Х,) = а1Х,', ГДЕ аг ЗатРатЫ ,йг на производство одного г-го изделия (при мелкосерийном или индивидуальном производстве обычно йг > 1, а при крупно- серийном — бг ( 1). Предположим также, .что должно быть выполнено так называемое условие на ассортимент: предприятие должно выпустить не менее б, единиц гаго изделия, т.е. имеем п ограничений типа неравенства х; > б1, г = 1, и. Если эффективность производства изделий определить как суммарную выручку от их продажи, то получим еще одно ограничение типа неравенства ЬА.
Задачи оптимального планирования характеризующую суммарные затраты на производство изделий. Следовательно, сформулированная задача является задачей нединейноео программирования. Пример 1.15. Пусть сеть газопроводов связывает между собой па месторождений Ао г =1, т, газа и и пунктов В, 1 = = 1, и, его потребления с известными значениями р: ) О расхода газа в единицу времени. Производительность д, г-го месторождения, г = 1,т, ограничена заданным значением С;, т.е. заданы ограничения типа неравенства О < д,; < Сг Затраты на добычу газа на г-м месторождении, г = 1, т, являются функцией р;(д,) производительности д,.
Сеть состоит из К участков, причем стоимость подачи газа по а-му участку, й = 1, Л, является функцией ~ь(да) расхода дь через этот участок. В пунктах потребления газа имеем ограничения типа равенства ~дь=р+ ~ д д=1» аЕВ~ где В и В, множества участков сети с входящими в у-й пункт и выходящими из него потоками газа соответственно. Аналогично для месторождений газа получаем ограничения типа равенства д,= ~ дю 1=1,пз. яеА, Оптимальным планом добычи газа на месторождениях и распределения потоков газа по участкам сети газопроводов будет план, который удовлетворяет указанным ограничениям и обеспечивает минимум общих затрат на добычу и подачу газа.
Все ограничения в сформулированной задаче линейные. Поэтому в частном случае линейных функций ~р;(д,) и 1ь(дь) она будет задачей линейного программирования, но в общем случае --. задачей нелинейного программирования. 42 Ь ЗАДА ЧИ ОПТИМИЗАЦИИ 1.5. Классы задач оптимизации Как и в любой классификации, разделение задач оптимизации на отдельные классы достаточно условно. Отметим, что одна и та же прикладная задача может приводить к разным задачам оптимизации в зависимости от того, какая математическая модель используется при рассмотрении реального объекта оптимизации.
Ясно, что желательно применять более простые модели, но в то же время достаточно полно отражающие свойства объекта, существенные с точки зрения поставленной цели, выраженной в критерии оп~~имальности. Поэтому при выборе либо разработке математической модели или же при обосновании ее упрощения необходимо достаточно четко представлять,к какому классу будет относиться поставленная задача оптимизации и какие методы применимы для ее решения. Пусть )о(ж) це,левая функция, количественно выражающая некоторый критерий оптимальности и зависящая от координат и, у = 1, п, точки а б Бо. Эти координаты являются параметрами оптимизации 1иногда их называют также переменными задачи оптимизации или просто переменными задачи). При математической формулировке задачи оптимизации целевую функцию выбирают с таким знаком., чтобы решение задачи соответствовало поиску минимума этой функции.
Поэтому формулировку обшей задачи матпематпическоео проераммирое ания обычно записыва1от так: зв(т) ь пнп., ш е Й, (1.18) где Й С 1к" — множество возможных альтернатив, рассматриваемых при поиске решения задачи. Любую точку з Е П называют допустпимым решением задачи математического программирования, а само множество --. множеством допустимых решений или, короче, допуспьимызл 1.я. Классы задач ццтииизации мнозхестпвом. Точку х' Е Й, в которой функция ~с(х) достигает своего наименьшего значения, называют оншимальным решением задачи.
При отсутствии ограничений множество Й совпадает с областью определения О(Д) с тт" целевой функции. Если же рассматриваемые альтернативы должны удовлетворять некоторым ограничениям, то множество допустимых решений сужается. Задачу (1.18) в дальнейшем будем называть задачей минимизации целевой функции на множестве Й, понимая под этим нахождение наименьшего значения функции Д(х) на Й и точек х Е Й, в которых оно достигается. Но целевая функция может и не достигать на Й наименьшего значения. Тогда говорят о точной нижней грани шГ 1с(х) функции )с(х) на этом множестве еен и вместо (1.18) используют запись (1.19) Ях) — тшт, хЕЙ. Отличие (1.18) от (1.19) в том, что в первом случае предполагают сутцсствование точки х* Е Й, в которой целевая функция достигает своего наименьшего значения на множестве Й, а во втором случае такая точка может и нс существовать.
Поэтому решение общей задачи математического программирования состоит в том, чтобы в первом случае найти точные (или с некоторой заданной точностью) значения координат х, у = 1, н, точки х* Е Й и значение целевой функции 1с(х*) = тттш)с(х), яен а во втором случае построить такую последовательность (х„1 точек х б Й,которой бы соответствовала последовательность тт1с(хц)), схоДЯЩаЯсЯ к знатению шт Д(х), и вычислить это вен значение с заданной точностью. Отметим,что в болыпинствс прикладных задач имеет место первый случай, .поэтому использование записи вида (1.19) будем оговаривать особо.
Если Ях) линейная функция, то ее область определения совпадает с %'.". В 11" такую функцию с помощью стандартного 44 к злдлчи оцтимизлции скалярного произведения можно представить в виде тв(х) = = (с, х), где с = (с~....., с„) Е К" — известный вектор.
Ясно, что целевая функция в тв(х) = (с, х) = ~~', аз ту может достигать наименьшего значения Д(х*) на множестве Й лишь в точках границы дй этого множества. Если в задаче нет ограничений, то Й = К"' и точная нижняя грань линейной функции равна — оо. Поэтому в случае линейной целевой функции задача оптимизации (1.20) (с,х) — +шш, хЕК", имеет смысл лишь при наличии ограничений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
