Основные задачи математического программирования

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

В общем виде математическая постановка экстремальной за­дачи состоит в определении наибольшего или наименьшего зна­чения целевой функции f (х1, х2, ..., xn) при условиях gi (х1, х2, ..., xn) £ b, (i = 1, m), где f и gi – заданные функции, a bi – неко­торые действительные числа.

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

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

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

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

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

Отдельными классами задач математического программи­рования являются задачи целочисленного, параметрического и дробно-линейного программирования.

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

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

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

Выделяют отдельные классы задач стохастического и дина­мического программирования.

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

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

 

3.9. Линейное программирование: экономическое планирование и геометрическая интерпретация

 

Линейное программирование в соответствии с его происхождением следует подробнее расшифровать так: “Составление оптимальных планов производства на основе линейных экономических моделей”. Из экономики название перешло в общие математические исследования линейных задач оптимизации, т.е. задач об экстремумах линейных целевых функций при ограничениях в виде линейных неравенств и линейных уравнений.

В качестве примера экономической задачи планирования решаемой с помощью линейного программирования рассмотрим завод, вы­пускающий два вида кафельных плиток для настила пола; для изго­товления каждого вида требуется одинаковое количество сырья, т. е. песка, гравия и цемента, но один вид плитки окрашивается и требует некоторого количества красящего вещества. На производство тонны окрашенной плитки требуется два часа машинного времени, три часа рабочего времени и два литра краски. Для производства тонны пли­ток второго типа (без краски) требуется час машинного времени, три часа рабочего времени и не требуется краски. Доход от производства плиток первого типа составляет 3 ф. ст. (фунта стерлингов), а от производства плиток второго типа – 2 ф. ст. Всего в наличии имеется 10 ч. машинного времени, 24 ч. рабочего времени и 8 л кра­ски. Требуется определить, сколько тонн плиток каждого типа следу­ет произвести, чтобы получить максимальную прибыль.

Приведенную выше информацию можно представить в форме таблицы.

 

Таблица 2.9.1.

 

Исходные данные	Технические показатели	Всего в наличии единиц
Плитки первого типа, х1	Плитки второго типа, х2
Машинное время
Рабочее время
Краска
Прибыль

 

Пусть произведено х1 тонн плиток первого типа и х2 тонн – второго типа. Переменные х1 и х2 не могут принимать отрицательные значе­ния и должны удовлетворять условиям

 

 

Из первой строки таблицы видно, что для производства x1 тонн плиток первого типа требуется 2x1 часов машинного времени, а для x2 тонн плиток второго типа – x2 часов. Общее количество машинного вре­мени не должно превышать 10 ч. Алгебраически это можно выразить в виде

 

2x₁+x₂≤ 10

Для тех же аргументов x1 и x2 из следующих двух строк таблицы получаем:

 

3x₁ + 3x₂ ≤ 24; 2x₁ ≤ 8.

 

Таким образом, всего имеется три ограничения:

 

 

Каждая пара значений х1 и х2 удовлетворяющая указанным ограничениям, называется допустимым решением или допустимой програм­мой (реально допустимым проектом). Общая прибыль получается из последней строки таблицы следующим образом:

 

z=3x₁ + 2x₂

или

3x₁ + 2x₂ –z = 0.

 

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

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

Так как в задаче всего две переменные х1 и х2, оптимальную программу можно получить графически. Рассматривая сначала в ограничениях знаки равенства, получаем:

 

 

Эти уравнения представляют собой уравнение трех прямых линий (см. рис. 9). Горизонтальная ось этой диаграммы представляет х1, а. вертикальная ось – х2. Прямая АВ, представляющая первое урав­нение из последней системы, пересекает оси координат в точках х1 = 5 и х2 = 10- Пря­мая ЕА, представляющая второе уравнение, пересекает эти оси в точ­ках х1 = 8 и х2 = 8, а линия DB, представляющая третье уравнение, пересекает горизонтальную ось в точке х1 = 4.

Согласно ограничениям (2.5), переменные могут принимать только неотрицательные значения, таким образом, все допустимые решения представлены точками на оси Xi или над ней, а также на оси х^ или справа от нее. Последнее неравенство (2.6) ограничивает допустимые значения Xi точками на линии DB или слева от нее. Аналогично, пер­вые два неравенства запрещают допустимым точкам лежать над пря­мой АВ и справа от прямой ЕА. Эта задача, как говорят, ограничена и граница допустимой области показана на рисунке штриховкой. Мно­жество точек внутри границы является допустимым решением задачи. Однако из этого множества представляет интерес только оптималь­ное решение.

 

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

 

Уравнения целевой функции представляют семейство параллельных прямых, и, задавая определенное значение Z, на этой же диаграмме можно получить одну из этих прямых. Например, если положить Z = 12, то полученное в результате уравнение 12 = 3х1 + 2х2 есть прямая линия, пере­секающая горизонтальную ось при х1 = 4, а вертикальную ось – при х2 = 6, как показано на рис. 9. Аналогично получают­ся другие прямые, и чем даль­ше линия от начала координат, тем больше значение целевой функции. В точке В х1 = 4 и х2 = 2. Подставляя эти значе­ния в целевую функцию, получаем Z = 16. Линия, представляющая Z =16, также изображена на рис. 9, причем она, как и следовало ожидать, проходит через точку В. В точке А, где пересекаются линии (1) и (2), х1 = 2 и х2 = 6; подставляя эти значения в целе­вую функцию, получаем Z = 18. Эта линия, очевидно, наиболее удалена от начала координат. Значения Z, представ­ленные линиями, более удаленными от начала координат, чем Z = 18, дают недопустимые решения. Таким образом, максимальная прибыль достигается при производстве 2 т плиток первого типа и 6 т – вто­рого типа при общей прибыли 18 ф. ст.

Отметим, что из всех точек особое внимание было обращено на узлы В и А. Можно доказать, что в этой и любой другой задаче линей­ного программирования оптимальное программирование всегда лежит в узле, где пересекаются две линии или более. Это возможно только в том случае, если график целевой функции не параллелен ни одной из граничных линий, в противном случае все точки этой линии дают оптимальное решение. Поэтому достаточно свести процесс исследо­вания к рассмотрению этих узлов. На рис. 9 таковыми являются точки О, D, В, А и Е. Начало координат (точка О), где х1 = 0 и х2 = 0, является допустимой точкой, и процесс исследования начинается с нее.

Для того, чтобы выяснить, сколько осталось неиспользованных времени и краски, значения переменных, заданные оптимальной про­граммой, подставляют в ограничения. При х1 = 2 и х2 = 6 левая часть первого неравенства-ограничения становится равной 10, следовательно, все имеющееся в наличии машинное время израсходовано. Аналогично, подстановка этих значений х1 и х2 во второе неравенство показывает, что его левая часть также равна 24 и, таким образом, была использо­вана вся наличная рабочая сила. Говорят, что оба первых ограниче­ния являются действенными, или критическими. Наконец, последнее ограничение показывает, что при производстве 2 т плитки первого типа остаются неиспользованны­ми 4 л краски..

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

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

Рис. 2.9.2. – Плоское графическое изображение условий задачи ЛП. Изо­бражение ограничений такое же, как на рис. 1. Целевая функция изобра­жена пиниями одинакового уровня z = 30, z = 42, z = 18 и др. По ним видно, что min z на множестве W достигается в точке D на пересечении прямых 4 и 6. Треугольник ОBЕ – первый симплекс, рассматриваемый при поиске допустимой точки симплекс-методом

 

Для решения задач ЛП чаще всего применяют симплекс-метод* (СМ), основанный на их алгебраизации, разработанной Дж. Данцигом и его школой. Это, подобно методу Гаусса решения линейных систем уравнений, конечный процесс, в прин­ципе дающий точный результат за конечное число вычислительных операций. Однако исследования сложности алгоритма СМ пока­зывают, что иногда это число может быть астрономически большим, и тогда решение недоступно никаким ЭВМ. Хотя расчетный опыт показывает, что такие " плохие" задачи почти не встречаются, в математике ведутся разработки более быстрых способов. Ока­зывается, для больших задач быстрее работают методы последова­тельных приближений и др. Несмотря на это, СМ в различных вариантах остается самым популярным для задач ЛП, особенно небольшой размерности.

Поясним идею СМ применительно к стандартной задаче ЛП (см. рис. 10). Очевидно, минимум или максимум линейной функ­ции z достигается в одной из вершин многогранника допустимых точек SI (возможно, в двух или нескольких вершинах — тогда нам нужна одна из них). Поиск точки минимума сводится к це­ленаправленному перебору вершин итак, чтобы функция z(x) уменьшалась. Но сначала надо найти одну из них.

 

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Популярное:

1. DSM-IV-TR: Основные характеристики.
2. I I. Цели, задачи, результаты выполнения индивидуального проекта
3. I. ОСНОВНЫЕ ЭТАПЫ НАПИСАНИЯ КУРСОВОЙ РАБОТЫ
4. I. Теоретические основы использования палочек Кюизенера как средство математического развития дошкольников.
5. I.1. Основные предпосылки и механизмы развития речевой деятельности
6. II. Основные задачи управления персоналом.
7. II. Основные принципы создания ИС и ИТ управления.
8. II. Решить следующие ниже финансовые задачи на листе “Задачи”.
9. II. Цели, задачи и предмет деятельности
10. III. Задачи, решаемые организацией с помощью ИСУ и ИТУ.
11. III. Основные идеологические течения в истории гражданского права. Идеализм и позитивизм
12. III. Основные учебники, учебные пособия, словари и хрестоматии.