Линейное программирование применяется для. Теория линейного программирования

Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера (см. ).

Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?

Обозначим: Х 1 - число изготовленных стульев, Х 2 - число сделанных столов. Задача оптимизации имеет вид:

45 Х 1 + 80 Х 2 → max ,

5 Х 1 + 20 Х 2 ≤ 400 ,

10 Х 1 + 15 Х 2 ≤ 450 ,

В первой строке выписана целевая функция - прибыль при выпуске Х 1 стульев и Х 2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х 1 и Х 2 . При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если Х 1 = 0, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то Х 1 положительно. Но невозможно представить себе отрицательный выпуск - Х 1 не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.

Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х 1 , а по вертикальной оси ординат - значения Х 2 . Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х 1 , Х 2) объемов выпуска в виде треугольника (рис.1).

Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - материал останется.

Аналогичным образом можно изобразить и ограничения по труду (рис.2).

Таким образом, ограничения по труду также изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось Х 1 , соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х 2 , соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не равенство - часть рабочих будет простаивать.

Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?

Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).

Таким образом, множество возможных значений объемов выпуска стульев и столов (Х 1 , Х 2), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений

5 Х 1 + 20 Х 2 = 400 ,

10 Х 1 + 15 Х 2 = 450 .

Из первого уравнения: 5 Х 1 = 400 - 20 Х 2 , Х 1 = 80 - 4 Х 2 . Подставляем во второе уравнение: 10 (80 - 4 Х 2) + 15 Х 2 = 800 - 40Х 2 + 15 Х 2 = 800 - 25 Х 2 = 450, следовательно, 25 Х 2 = 350, Х 2 = 14, откуда Х 1 = 80 - 4 х 14 = 80 -56 = 24. Итак, четвертая вершина четырехугольника - это (24, 14).

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

Целевая функция 45 Х 1 + 80 Х 2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х 1 + 80 Х 2 = 2200 проходит между прямыми ограничений 5 Х 1 + 20 Х 2 = 400 и 10 Х 1 + 15 Х 2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).

Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.

Двойственная задача . Каждой задаче линейного программирования соответствует так называемая двойственная задача. В ней по сравнению с исходной задачей строки переходят в столбцы, неравенства меняют знак, вместо максимума ищется минимум (или наоборот, вместо минимума - максимум). Задача, двойственная к двойственной - эта сама исходная задача. Сравним исходную задачу (слева) и двойственную к ней (справа):

45 Х 1 + 80 Х 2 → max , 400 W 1 + 450 W 2 → min ,

5 Х 1 + 20 Х 2 ≤ 400 , 5 W 1 + 10 W 2 ≥ 45,

10 Х 1 + 15 Х 2 ≤ 450 , 20 W 1 + 15 W 2 ≥ 80,

Х 1 ≥ 0 , W 1 ≥ 0,

Х 2 ≥ 0 . W 2 ≥ 0.

Почему двойственная задача столь важна? Можно доказать, что оптимальные значения целевых функций в исходной и двойственной задачах совпадают (т.е. максимум в исходной задаче совпадает с минимумом в двойственной). При этом оптимальные значения W 1 и W 2 показывают стоимость материала и труда соответственно, если их оценивать по вкладу в целевую функцию. Чтобы не путать с рыночными ценами этих факторов производства, W 1 и W 2 называют "объективно обусловленными оценками" сырья и рабочей силы.

Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.

Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.

Рассмотрим несколько задач линейного программирования.

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

Табл.3. Исходные данные в задаче об оптимизации смеси.

3,8 К + 4,2 С → min ,

0,10 К + 0,25 С ≥ 1,00 ,

1,00 К + 0,25 С ≥ 5,00 ,

110,00 К + 120,00 С ≥ 400,00 ,

Ее графическое решение представлено на рис.4.

Рис.4. Графическое решение задачи об оптимизации смеси.

На рис.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая 1,00К + 0,25С = 5,00 (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси абсцисс и (0,20) на оси ординат. Обратите внимание, что допустимые значения параметров (К, С) лежат выше прямой (1), в отличие от ранее рассмотренных случаев в предыдущей производственной задаче.

Прямая (2) - это прямая 110,00 К + 120,00 С = 400,00 (ограничение по калориям). Обратим внимание, что в области неотрицательных С она расположена всюду ниже прямой (1). Действительно, это верно при К=0, прямая (1) проходит через точку (0,20), а прямая (2) - через точку (0, 400/120). Точка пересечения двух прямых находится при решении системы уравнений

1,00 К + 0,25 С = 5,00 ,

110,00 К + 120,00 С = 400,00 .

Из первого уравнения К = 5 - 0,25 С. Подставим во второе: 110 (5- 0,25 С) + 120 С = 400, откуда 550 - 27,5 С + 120 С = 400. Следовательно, 150 = - 92,5 С, т.е. решение достигается при отрицательном С. Это и означает, что при всех положительных С прямая (2) лежит ниже прямой (1). Значит, если выполнено ограничения по Н, то обязательно выполнено и ограничение по калориям. Мы столкнулись с новым явлением - некоторые ограничения с математической точки зрения могут оказаться лишними. С экономической точки зрения они необходимы, отражают существенные черты постановки задачи, но в данном случае внутренняя структура задачи оказалась такова, что ограничение по калориям не участвует в формировании допустимой области параметров и нахождении решения.

Прямая (4) - это прямая 0,1 К + 0,25 С = 1 (ограничение по веществу Т). Она проходит, как и показано на рисунке, через точки (10,0) на оси абсцисс и (0,4) на оси ординат. Обратите внимание, что допустимые значения параметров (К,С) лежат выше прямой (4), как и для прямой (1).

Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых). Область допустимых значений параметров (К, С) можно назвать "неограниченным многоугольником". Минимум целевой функции 3,8 К + 4,2 С может достигаться только в вершинах этого "многоугольника". Вершин всего три. Это пересечения с осями абсцисс (10,0) и ординат (0,20) прямых (1) и (4) (в каждом случае из двух пересечений берется то, которое удовлетворяет обоим ограничениям). Третья вершина - это точка пересечения прямых (1) и (4), координаты которой находятся при решении системы уравнений

0,10 К + 0,25 С = 1,00 ,

1,00 К + 0,25 С = 5,00 .

Из второго уравнения К = 5 - 0,25 С, из первого 0,10 (5 - 0,25 С) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1, откуда С = 0,5/0,225 = 20/9 и К = 5 - 5/9 = 40/9. Итак, А = (40/9; 20/9).

Прямая (3) на рис.4 - это прямая, соответствующая целевой функции 3,8 К + 4,2 С. Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен 3,8х40/9 + 4,2х20/9 = 236/9. Задача об оптимизации смеси полностью решена.

Двойственная задача, построенная по описанным выше правилам, имеет приведенный ниже вид (мы повторяем здесь и исходную задачу об оптимизации смеси, чтобы наглядно продемонстрировать технологию построения двойственной задачи):

3,8 К + 4,2 С → min , W 1 + 5 W 2 + 400 W 3 → max ,

0,10 К + 0,25 С ≥ 1,00 , 0,1 W 1 + 1,10 W 2 + 110 W 3 ≤ 3,8 ,

1,00 К + 0,25 С ≥ 5,00 , 0,25W 1 + 0,25 W 2 + 120 W 3 ≤ 4,2 ,

110,00 К + 120,00 С ≥ 400,00 , W 1 ≥ 0 ,

К ≥ 0 , W 2 ≥ 0 ,

С ≥ 0 . W 3 ≥ 0 .

Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны 236/9. Интерпретация двойственных переменных: W 1 - "стоимость" единицы вещества Т, а W 2 - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом W 3 = 0, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, W 1 , W 2 , W 3 - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).

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

Табл.4. Производственные мощности (в шт.)

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

Задача линейного программирования имеет вид:

Х 1 ≥ 0 , Х 2 ≥ 0 , Х 3 ≥ 0 , (0)

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 ≤ 100 , (1)

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100 , (2)

Х 1 / 200 ≤ 100 , (3)

Х 2 / 120 ≤ 100 , (4)

Х 3 / 80 ≤ 100 , (5)

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max .

Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.

Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно сразу отбросить.

Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане Х 3 = 0, т.е. самовары выпускать невыгодно.

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

В качестве примера рассмотрим решение задачи рациональности использования времени работы производственного оборудования.
В соответствии с оперативным планом участок шлифовки за первую неделю декабря выпустил 500 колец для подшипников типа А, 300 колец для подшипников типа Б и 450 колец для подшипников типа В. Все кольца шлифовались на двух взаимозаменяемых станках разной производительности. Машинное время каждого станка составляет 5000 мин. Трудоемкость операций (в минутах на одно кольцо) при изготовлении различных колец характеризуется следующими данными (табл. 6.5).
Таблица 6.5
Следует определить оптимальный вариант распределения операций по станкам и время, которое было бы затрачено при этом оптимальном варианте. Задачу выполним симплексным методом.
Для составления математической модели данной задачи введем следующие условные обозначения: jc, х2, хъ, - соответственно количество колец для подшипников типов Л, Б, В, производимых на станке I; х4, х5, х6, - соответственно количество колец для подшипников типов А, Б, В, производимых на станке II.
Линейная форма, отражающая критерий оптимальности, будет иметь вид:
min а(х) = 4x,-f 10x2-f 10x3-f 6x4-f 8х5+20х6 при ограничениях
4х, -f 10х2 -f 10;t3 lt; 5000
6х4 -f 8х5 -f 20х6 ~lt; 5000
х, = 500
х2 +х5 = 300
х3 +х6 = 450
Xj^0,j=l, ..., 6

Преобразуем условие задачи введением дополнительных (вспомогательных) и фиктивных переменных. Условие запишем так:
шіп lt;х(х) = 4дг, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Мх9 + Мх{0+Мх{,
Система уравнений, отражающая ограничительные условия машинного времени и количество произведенной продукции:
4х, + l(bc2 + 10х3 +х1 = 5000
6х4 + 8х5 + 20х6 + xs = 5000
Xj +х4 +х9 = 500
х2 +х5 +х10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Решение этой задачи представлено в табл. 6.6. Оптимальный вариант получен на седьмом этапе (итерации). Если бы на станке I производилось 125 колец подшипников типа А, 450 колец подшипников типа В, на станке II - 375 колец подшипников типа А и 300 колец подшипников типа Б, то при такой загрузке оборудования было бы высвобождено 350 мин машинного времени станка II. Общие затраты времени по оптимальному варианту составили бы 9650 мин, тогда как фактически затрачено 10000 мин машинного времени.
Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Ее смысл заключается в минимизации грузооборота при доставке товаров широкого потребления от производителя к потребителю, с оптовых складов и баз в розничные торговые предприятия. Она решается симплекс-методом или распределительным методом.
Решение транспортной задачи распределительным методом было дано в третьем издании учебника «Теория экономического анализа» («Финансы и статистика», 1996).

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

15. Аналитические методы. Методы линейного программирования.

15.1. Аналитические методы

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

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

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

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

Составной частью методов оптимизации является линейное программирование.

15.2. Основные понятия линейного программирования

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя,в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.

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

быть единственным для данной задачи;

измеряться в единицах количества;

линейно зависеть от входных параметров.

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

найти экстремум целевой функции

при ограничениях в виде равенств:

(2.2)

при ограничениях в виде неравенств:

(2.3)

и условиях неотрицательности входных параметров:

В краткой форме задача линейного программирования может быть записана так:

(2.5)

при условии

где
- входные переменные;

Числа положительные, отрицательные и равные нулю.

В матричной форме эта задача может быть записана так:

Задачи линейного программирования можно решить аналитически и графически.

15.3. Каноническая задача линейного программирования

, i=1,…,m,

, j=1,…,n.

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

15.4. Общая задача линейного программирования

Необходимо максимизировать (минимизировать) линейную функцию от n переменных.

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

, i =1,…, k ,

, i =1+ k ,…, m ,

, …,

Здесь k ≤ m , r ≤ n . Стандартная задача получается как частный случай общей приk = m , r = n ; каноническая – приk =0, r = n .

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1. Нормы расходов сырья

на производство

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3) , чтобы

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

при условиях-ограничениях:

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

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

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

Если бы первые работы Л.В.Канторовича получили в свое время должную оценку, то была бы велика вероятность еще большего продвижения линейного программирования в настоящее время. К сожалению, его работа оставалась в тени как в Советском Союзе, так и за его пределами, и, как отмечает Данциг: " ...и за это время линейное программирование стало настоящим искусством."

Оптимальный план любой линейной программы следует автоматически связывать с оптимальными ценами или, согласно Л.В.Канторовичу, с "объективно обусловленными оценками". Это нагромождение слов имело целью повысить "критикоустойчивость" термина. Суть экономического открытия Л.В.Канторовича заключается во взаимосвязи оптимальных решений и оптимальных цен.

Методы линейного программирования

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

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

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

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

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

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

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

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

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

2. Понятие линейного программирования. Виды задач линейного программирования

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

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

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

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

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

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

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

Графический метод решения задачи ЛП;

Симплексный метод;

Решение задачи ЛП средствами табличного процессора Excel;

3. Понятие нелинейного программирования

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

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

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

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

4. Динамическое программирование

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

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

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

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

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk(S,Xk) и переводит систему в некоторое новое состояние S"(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

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

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

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

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

целевая функция является аддитивной и равна сумме целевых функций каждого шага

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

X*=(X*1, X*2, …, X*k, …, X*n),

число которых и определяет количество шагов задачи.

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

Fn(S)=max{Wn(S,Xn)},

где максимум ищется по всем возможным значениям Xn.

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

Fk(S)=max{Wk(S,Xk)+Fk+1(S"(S,Xk))}. (1)

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Лабораторная работа №1 (Задача линейного программирования)

Для заданной математической постановки задачи ЛП, приняв дополнительно условие неотрицательности переменных, выполнить следующие действия:

Решить задачу графическим методом;

Привести задачу к канонической форме записи;

Составить симплексную таблицу;

Произвести решение задачи симплексным методом ручным способом или с использование компьютера;

Осуществить постановку двойственной задачи ЛП;

Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов;

Проверить результаты решения в табличном процессоре Excel;

Составить отчет с приведение результатов по каждому пункту.

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

, получим

изобразим граничные прямые.

Линейная функция F=f(x) является уравнением прямой линии c1x1 + c2x2 = const. Построим график целевой функции при f(x)=0. для построения прямой 3x1 + 4x2 = 0 строим радиус-вектор N = (3; 4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую F=0 перемещаем параллельно самой себе в направлении вектора N.

Из рисунка 1 следует, что опорной по отношению к построенному многоугольнику решений эта прямая становится в точке B, где функция F принимает максимальное значение. Точка В лежит на пересечении прямых 0,7x1 + 2x2 ≤ 13,1 и 2,3x1 + 2x2 =23/ Для определения ее координат решим систему уравнений:

Оптимальный план задачи: х1 = 6.187; х2 = 4.38, подставляя значения х1 и х2 в целевую функцию, получаем Fmax= 3*6.187+4*4.38=36.08.

Таким образом, для того, чтобы получить максимальную прибыль в размере 36.06 долларов, необходимо запланировать производство 6 ед. продукции P1 и 4 ед. продукции P2.

Канонический вид задачи ЛП. Запишем в канонической форме задачу распределения ресурсов. Добавив к исходной системе ограничений неотрицательные переменные х3 ≥ 0, х4 ≥ 0, х5 ≥ 0, имеем:

Симплексная таблица ЛП. В случае базисных переменных {x3, x4, x5} начальная симплекс таблица будет выглядеть:

Таблица 1.

Она уже соответствует опорному плану x(0) = Т (столбец свободных членов).