В теории принятия решений большое место занимают оптимизационные задачи Среди них наиболее известны задачи линейного программирования, в которых максимизируемая функция $$F(X) $$ является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.
Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Изготовление стула требует 10 человеко-часов, стола - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?
Обозначим: $$Х_1$$ - число изготовленных стульев, $$Х_2 $$ - число сделанных столов. Задача оптимизации имеет вид:
$$45 Х_1 + 80 Х_2 \to max\\ 5 Х_1 + 20 Х_2 \le 400,\\ 10 Х_1 + 15 Х_2 \le 450,\\ Х_1 \ge 0,\\ Х_2 \ge 0.$$В первой строке выписана целевая функция - прибыль при выпуске $$Х_1$$ стульев и $$Х_2$$ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных $$Х_1$$ и $$Х_2.$$ При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если $$Х_1 = 0$$, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то $$Х_1$$ положительно. Но невозможно представить себе отрицательный выпуск - $$Х_1$$ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.
Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения $$Х_1$$, а по вертикальной оси ординат - значения $$Х_2$$. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения вектора $$(Х_1, Х_2) $$ объемов выпуска в виде треугольника (рис. 8.1).
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось $$Х_1$$, соответствующую стульям, в точке (80, 0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось $$Х_2$$, соответствующую столам, в точке (0, 20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не точное равенство - материал останется.
(рис 8.1)
Аналогичным образом можно изобразить и ограничения по труду (рис. 8.2).
(рис 8.2)
Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось $$Х_1$$, соответствующую стульям, в точке (45, 0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось $$Х_2$$, соответствующую столам, в точке (0, 30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не точное равенство - часть рабочих будет простаивать.
Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо "совместить" рис. 8.1 и рис. 8.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис. 8.3).
(рис 8.3)
Таким образом, множество возможных значений объемов выпуска стульев и столов $$(Х_1, Х_2) $$, или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис. 8.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис. 8.1 и рис. 8.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 \times 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 долларам США.
Двойственная задача. Каждой задаче линейного программирования соответствует так называемая
Почему
Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.
Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.
Рассмотрим несколько типовых задач линейного программирования .
Задача о диете (упрощенный вариант) . Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).
| Содержание в 1 унции К | Содержание в 1 унции С | Потребность | |
|---|---|---|---|
| Вещество Т | 0,10 мг | 0,25 мг | 1,00 мг |
| Вещество Н | 1,00 мг | 0,25 мг | 5,00 мг |
| Калории | 110,00 | 120,00 | 400,00 |
| Стоимость 1 унции, в центах | 3,8 | 4,2 |
Пищевая ценность рациона (в калориях) должна быть не менее заданной. Пусть для простоты смесь для цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в табл. 8.1.
Задача линейного программирования имеет вид:
$$3,8 К + 4,2 С \to min ,\\ 0,10 К + 0,25 С \ge 1,00 ,\\ 1,00 К + 0,25 С \ge 5,00 ,\\ 110,00 К + 120,00 С \ge 400,00 ,\\ К \ge 0 ,\\ С \ge 0.$$Ее графическое решение представлено на рис. 8.4
(рис 8.4) Графическое решение задачи об оптимизации смеси
На рис. 8.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) на рис. 8.5 - это прямая, соответствующая целевой функции $$3,8 К + 4,2 С.$$ Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен $$3,8\times40/9 + 4,2\times20/9 = 236/9$$. Задача об оптимизации смеси полностью решена.
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны $$236/9$$. Интерпретация двойственных переменных: $$W_1 $$ - "стоимость" единицы вещества Т, а $$W_2$$ - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом $$W_3 = 0$$, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, $$W_1 , W_2 , W_3$$ - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).
Планирование номенклатуры и объемов выпуска. Вернемся к организации производства. Предприятие может выпускать автоматические кухни (вид кастрюль), кофеварки и самовары. В табл. 8.2 приведены данные о производственных мощностях, имеющихся на предприятии (в штуках изделий).
| Кухни | Кофеварки | Самовары | |
|---|---|---|---|
| Штамповка | 20000 | 30000 | 12000 |
| Отделка | 30000 | 10000 | 10000 |
| Сборка | 20000 | 12000 | 8000 |
| Объем выпуска | Х1 | Х2 | Х3 |
| Удельная прибыль (на одно изделие) | 15 | 12 | 14 |
При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.
Задача линейного программирования имеет вид:
$$Х_1 \ge 0 , Х_2 \ge 0 , Х_3 \ge 0 $$ $$Х_1 / 200 + Х_2 / 300 + Х_3 / 120 \le 100 $$ $$Х_1 / 300 + Х_2 / 100 + Х_3 / 100 \le 100 $$ $$Х_1 / 200 \le 100 $$ $$Х_2 / 120 \le 100 $$ $$Х_3 / 80 \le 100 $$ $$F = 15 Х_1 + 12 Х_2 + 14 Х_3 \to max.$$Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).
Наконец, целевая функция $$F$$ - общая прибыль предприятия.
Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно из формулировки задачи линейного программирования исключить.
Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане $$Х_3 = 0$$, т.е. самовары выпускать невыгодно.
Методы решения задач линейного программирования. Методы решения задач линейного программирования относятся к вычислительной математике, а не к экономике. Однако экономисту полезно знать о свойствах интеллектуального инструмента, которым он пользуется.
С ростом мощности компьютеров необходимость применения изощренных математических методов снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, оно весьма мало (доли секунд). Поэтому разберем лишь три метода.
Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа $$2Х_1 + 5Х_2 \le 10$$, то, очевидно, $$0 \le Х_1 \le 10/2 = 5 и 0 \le Х_2 \le 10/5 = 2$$. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.
Проведем перебор точек параллелепипеда с шагом $$1/10^n$$ последовательно при $$n=2,3,\dots$$, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до $$1/10^n$$.)
Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - с помощью т.н. метода случайного поиска) менять ее координаты на определенную величину $$\Delta$$, переходя каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до $$\Delta$$. Если необходимо, в окрестности найденного решения проводим направленный перебор с шагом $$\Delta/2 $$, $$\Delta/4$$ и т.д.)
Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл. 8.2.
Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:
$$F = 15 Х_1 + 12 Х_2 + 14 Х_3 \to max .\\ Х_1 / 200 + Х_2 / 300 + Х_3 / 120 \le 100 ,\\ Х_1 / 300 + Х_2 / 100 + Х_3 / 100 \le 100 ,\\ Х_3 / 80 \le 100.$$Неотрицательность переменных не будем специально указывать, поскольку в задачах линейного программирования это предположение всегда принимается.
В соответствии с симплекс-методом введем т.н. "свободные переменные" $$Х_4, Х_5, Х_6$$, соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:
$$Х_1 / 200 + Х_2 / 300 + Х_3 / 120 + Х_4 = 100 ,\\ Х_1 / 300 + Х_2 / 100 + Х_3 / 100 + Х_5 = 100 ,\\ Х_3 / 80 + Х_6 = 100 ,\\ 15 Х_1 + 12 Х_2 + 14 Х_3 = F.$$У этой системы имеется очевидное решение, соответствующее одной из вершин многогранника допустимых значений переменных:
$$Х_1 = Х_2 = Х_3 = 0, Х_4 = Х_5 = Х_6 = 100, F = 0.$$В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.
В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это $$Х_1.$$
Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной $$Х_1$$:
$$100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + \infty.$$Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.
Умножим первую строку на 200, чтобы получить $$Х_1$$ с единичным коэффициентом:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000.$$Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с $$Х_1$$, получим
$$7/900 Х_2 + 4/900 Х_3 - 2/3 Х_4 + Х_5 = 100/3.$$Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит $$F$$, получим:
$$2 Х_2 - 11 Х_3 - 3000 Х_4 = F - 300000.$$В результате система уравнений преобразуется к виду, в котором переменная $$Х_1$$ входит только в первое уравнение:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000 ,\\ 7/900 Х_2 + 4/900 Х_3 - 2/3 Х_4 + Х_5 = 100/3,\\ Х_3 / 80 + Х_6 = 100 ,\\ 2 Х_2 - 11 Х_3 - 3000 Х_4 = F - 300000.$$Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:
$$Х_1 = 20000, Х_2 = Х_3 = Х_4 = 0, Х_5 = 100/3, Х_6 = 100, F = 300000.$$В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.
Повторим описанную выше операцию. В строке с $$F$$ имеется еще один положительный коэффициент - при $$Х_2$$ (если бы положительных коэффициентов было несколько - мы взяли бы максимальный из них). На основе коэффициентов при $$Х_2$$ (а не при $$Х_1$$, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:
$$20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + \infty$$Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при $$Х_2$$ равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим $$Х_2$$, предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при $$Х_2$$ стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:
$$Х_1 + 9/7 Х_3 + 1800/7 Х_4 - 600/7 Х_5 = 120000/7, Х_2 + 4/7 Х_3 - 600/7 Х_4 + 900/7 Х_5 = 30000/7, Х_3 / 80 + Х_6 = 100 , - 85/7 Х_3 - 19800/7 Х_4 - 1800/7 Х_5 = F - 308571.$$Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при $$Х_3 = Х_4 = Х_5 = 0$$. Из остальных уравнений следует, что при этом $$Х_1 = 120000/7 = 17143, Х_2 = 30000/7 = 4286, Х_6 = 100$$. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.
Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т.е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В книге [8.1] приведен обширный перечень публикаций, посвященный многочисленным применениям линейного программирования в металлургии, угольной, химической, нефтяной, бумажной и прочих отраслях промышленности, в проблемах транспорта и связи, планирования производства, конструирования и хранения продукции, сельском хозяйстве, в научных исследованиях, в том числе экономических, и даже при регулировании уличного движения.
В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 8.3.
В этой таблице, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада $$i, i = 1,2,3$$, потребителю $$j, j = 1,2,3,4$$. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется $$50+70 =120$$ единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл. 8.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
| Потреби-тель 1 | Потреби-тель 2 | Потреби-тель 3 | Потреби-тель 4 | Запасы на складах | |
|---|---|---|---|---|---|
| Склад 1 | 2 | 5 | 5 | 5 | 60 |
| Склад 2 | 1 | 2 | 1 | 4 | 80 |
| Склад 3 | 3 | 1 | 5 | 2 | 60 |
| Потреб-ности | 50 | 40 | 70 | 40 | 200 |
Надо спланировать перевозки, т.е. выбрать объемы $$Х_{ij}$$ поставок товара со склада i потребителю $$j,$$ где $$i = 1,2,3; j = 1,2,3,4$$. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:
$$X_{11} + Х_{12} + Х_{13} + Х_{14} = 60 ,\\ X_{21} + Х_{22} + Х_{23} + Х_{24} = 80 ,\\ X_{31} + Х_{32} + Х_{33} + Х_{34} = 60.$$Во-вторых, известны потребности клиентов:
$$X_{11} + Х_{21} + Х_{31} = 50,\\ X_{12} + Х_{22} + Х_{32} = 40,\\ X_{13} + Х_{23} + Х_{33} = 70,\\ X_{14} + Х_{24} + Х_{34} = 40.$$Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.
Целевая функция - издержки по перевозке, которые необходимо минимизировать:
$$F = 2 X_{11} + 5 Х_{12} + 4 Х_{13} + 5 Х_{14} + X_{21} + 2 Х_{22} + Х_{23} + 4 Х_{24} + +3 X_{31} + Х_{32} + 5 Х_{33} + 2 Х_{34} \to min.$$Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.
Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):
$$С = 7 Х + 3 У \to max.$$При этом должны быть выполнены следующие ограничения:
по стоимости (в тыс. долларов США)
$$5 Х + 2 У \le 20,$$по занимаемой площади (в м2 )
$$8 Х + 4 У \le 38,$$а также вновь появляющиеся специфические ограничения по целочисленности, а именно,
$$Х \ge 0 , У \ge 0 , Х и У$$ - целые числа.
Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором.
Действительно, как ограничение по стоимости, так и ограничение по площади дают, что $$Х \le 4$$. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.
Если $$Х = 4$$, то из ограничения по стоимости следует, что $$У = 0$$, а потому $$С = 7 Х = 28$$.
Если $$Х= 3$$, то из первого ограничения вытекает, что $$У \le 2$$, из второго $$У \le 3$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У =2$$, а именно $$С = 21 + 6 = 27$$.
Если $$Х= 2$$, то из первого ограничения следует, что $$У \le 5$$, из второго также $$У \le 5$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У =5$$, а именно $$С = 14 + 15 = 29$$.
Если $$Х= 1$$, то из первого ограничения имеем $$У \le 7$$, из второго также $$У \le 7$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У = 7$$, а именно $$С = 7 + 21 = 28$$.
Если $$Х= 0$$, то из первого ограничения вытекает $$У \le 10$$, из второго $$У \le 9$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У = 9$$, а именно, $$С = 27$$.
Все возможные случаи рассмотрены. Максимальная производительность $$С = 29$$ (тысяч единиц продукции за смену) достигается при $$Х = 2, У = 5$$. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.
Задача о ранце. Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.
Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат - спутник Земли, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы.
С точки зрения экономики предприятия и организации производства более актуальна другая интерпретация задачи о ранце, в которой в качестве "предметов" рассматриваются заказы (или варианты выпуска партий тех или иных товаров), в качестве полезности - прибыль от выполнения того или иного заказа, а в качестве веса - себестоимость заказа.
Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные $$Х_k , k = 1,2,\dots, n$$ (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом $$Х_k = 1$$, если предмет размещают в ранце, и $$Х_k = 0$$, если нет, $$k = 1,2,\dots, n$$. Для каждого предмета известны две константы: $$А_k$$ - вес $$k$$ -го предмета, и $$С_k$$ - полезность $$k$$ -го предмета, $$k = 1,2,\dots, n.$$ Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид
$$C_1 Х_1 + С_2 Х_2 + С_3 Х_3 + \dots. + С_nХ_n \to max,\\ А_1 Х_1 + А_2 Х_2 + А_3 Х_3 + \dots. + А_nХ_n \le В.$$В отличие от предыдущих задач, управляющие параметры $$Х_k , k = 1,2,\dots, n $$, принимают значения из множества, содержащего два элемента - 0 и 1.
К
Укажем два распространенных метода решения задач
Метод приближения непрерывными задачами. В соответствии с ним сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки.
Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству $$Х$$ множества возможных решений $$Х_0$$ ставится в соответствие число - "граница" $$А(Х) $$. При решении задачи минимизации необходимо, чтобы $$А(Х_1) \ge А(Х_2) $$, если $$Х_1$$ входит в $$Х_2$$ или совпадает с $$Х_2.$$
Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества $$Х_С$$ на два - $$Х_{1С}$$ и $$Х_{2С}$$. При этом пересечение $$Х_{1С}$$ и $$Х_{2С}$$ пусто, а их объединение совпадает с $$Х_С$$. Затем вычисляют границы $$А(Х_{1С} ) $$ и $$А(Х_{2С})$$ и выделяют "ветвь" $$Х_{С+1}$$ - то из множеств $$Х_{1С}$$ и $$Х_{2С}$$, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа
Для каждой конкретной задачи
Один из разделов дискретной математики, часто используемый при принятии решений - теория графов. Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами (дуги называют также ребрами). Примеры графов приведены на рис. 8.5
(рис 8.5) Примеры графов
На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис. 8.6.
(рис 8.6) Примеры ориентированных графов
Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Задача коммивояжера. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.
Многие постановки экономического содержания сводятся к
Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис. 8.7).
(рис 8.7) Исходные данные к задаче о кратчайшем пути
Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл. 8.4). В этой таблице двум вершинам - началу пути и концу пути - ставится в соответствие время в пути. В табл. 8.4 рассматриваются пути без промежуточных остановок. Более сложные маршруты составляются из элементарных отрезков, перечисленных в табл. 8.4.
| Начало дуги | Конец дуги | Время в пути |
|---|---|---|
| 1 | 2 | 7 |
| 1 | 3 | 1 |
| 2 | 4 | 4 |
| 2 | 6 | 1 |
| 3 | 2 | 5 |
| 3 | 5 | 2 |
| 3 | 6 | 3 |
| 5 | 2 | 2 |
| 5 | 4 | 5 |
| 6 | 5 | 3 |
Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?
Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.
Для исходных данных, представленных на pис. 8.7 и в табл. 8.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому $$С(3) = 1$$. Кроме того, очевидно, что $$С(1) = 0$$.
В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение
$$С(4) = min \{С(2) + 4; С(5) + 5\}.$$Таким образом, проведена реструктуризация (упрощение) задачи - нахождение $$С(4) $$ сведено к нахождению $$С(2) $$ и $$С(5) $$.
В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение
$$С(5) = min \{С(3) + 2; С(6) + 3\}.$$Мы знаем, что $$С(3) = 1$$. Поэтому
$$С(5) = min \{3; С(6) + 3\}.$$Поскольку очевидно, что $$С(6) $$ - положительное число, то из последнего соотношения вытекает, что $$С(5) = 3$$.
В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение
$$С(2) = min \{С(1) + 7; С(3) + 5; С(5) + 2\}.$$Нам известно, что $$С(1) = 0, С(3) = 1, С(5) = 3$$. Поэтому
$$С(2) = min \{0 + 7; 1 + 5; 3 + 2\} = 5.$$Теперь мы можем найти $$С(4) $$:
$$С(4) = min \{С(2) + 4; С(5) + 5\} = min \{5 + 4; 3 + 5\} = 8.$$Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:
$$1 \to 3 \to 5 \to 4.$$Задача о кратчайшем пути для конкретных исходных данных (рис. 8.7 и табл. 8.4) полностью решена.
Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис. 8.8).
(рис 8.8) Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 8.8, можно также задать таблицей (табл. 8.5).
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 0 | 1 | 2 |
| 0 | 2 | 3 |
| 0 | 3 | 1 |
| 1 | 2 | 4 |
| 1 | 3 | 1 |
| 1 | 4 | 3 |
| 2 | 3 | 1 |
| 2 | 4 | 2 |
| 3 | 4 | 2 |
Решение
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.
Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл. 8.6).
| Пункт отправления | Пункт назначения | План перевозок | Пропускная способность |
|---|---|---|---|
| 0 | 1 | 2 | 2 |
| 0 | 2 | 3 | 3 |
| 0 | 3 | 1 | 1 |
| 1 | 2 | 0 | 4 |
| 1 | 3 | 0 | 1 |
| 1 | 4 | 2 | 3 |
| 2 | 3 | 1 | 1 |
| 2 | 4 | 2 | 2 |
| 3 | 4 | 2 | 2 |
Задача линейного программирования при максимизации потока. Дадим формулировку
Здесь $$F$$ - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен
О многообразии оптимизационных задач. В различных
Кроме затронутых выше методов решения задач оптимизации, напомним о том, что гладкие функции оптимизируют, приравнивая 0 производную (для функций нескольких переменных - частные производные). При наличии ограничений используют
Представляют интерес задачи оптимизации с
1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:
$$400 W_1 + 450 W_2 \to min,\\ 5 W_1 + 10 W_2 \ge 45,\\ 20 W_1 + 15 W_2 \ge 80,\\ W_1 \ge 0, W_2 \ge 0.$$2. Решите задачу линейного программирования:
$$W_1 + 5 W_2 \to max, \\ 0,1 W_1 + W_2 \le 3,8 ,\\ 0,25 W_1 + 0,25 W_2 \le 4,2 ,\\ W_1 \ge 0 , W_2 \ge 0.$$3. Решите задачу
$$Х $$ и $$У $$ - целые числа.
4. Решите задачу о ранце:
$$Х_1 + Х_2 + 2Х_3 + 2Х_4 + Х_5 + Х_6 \to max,\\ 0,5 Х_1 + Х_2 + 1,5Х_3 + 2Х_4 + 2,5Х_5 + 3Х_6 \le 3.$$Управляющие параметры $$Х_k, k = 1,2,\dots, 6 ,$$ принимают значения из множества, содержащего два элемента - 0 и 1.
5. Транспортная сеть (с указанием расстояний) приведена на рис. 8.9. Найдите кратчайший путь из пункта 1 в пункт 4.
(рис 8.9) Исходные данные к задаче о кратчайшем пути
6. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 8.10) ограничена (табл. 8.7)?
(рис 8.10) Транспортная сеть к задаче о максимальном потоке
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 1 | 4 | 3 |
| 2 | 5 | 2 |
| 3 | 2 | 2 |
| 3 | 4 | 2 |
| 3 | 6 | 1 |
| 4 | 7 | 4 |
| 5 | 8 | 3 |
| 6 | 5 | 2 |
| 6 | 7 | 1 |
| 6 | 8 | 1 |
| 7 | 8 | 3 |
7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в ттабл. 8.8.
| Город отправления | Город назначения | Затраты на проезд |
|---|---|---|
| А | Б | 2 |
| А | В | 1 |
| А | Д | 5 |
| Б | А | 3 |
| Б | В | 2 |
| Б | Д | 1 |
| В | А | 4 |
| В | Б | 1 |
| В | Д | 2 |
| Д | Ф | 5 |
| Д | Б | 3 |
| Д | В | 3 |
В теории принятия решений большое место занимают оптимизационные задачи Среди них наиболее известны задачи линейного программирования, в которых максимизируемая функция $$F(X) $$ является линейной, а ограничения А задаются линейными неравенствами. Начнем с примера.
Производственная задача. Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Изготовление стула требует 10 человеко-часов, стола - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?
Обозначим: $$Х_1$$ - число изготовленных стульев, $$Х_2 $$ - число сделанных столов. Задача оптимизации имеет вид:
$$45 Х_1 + 80 Х_2 \to max\\ 5 Х_1 + 20 Х_2 \le 400,\\ 10 Х_1 + 15 Х_2 \le 450,\\ Х_1 \ge 0,\\ Х_2 \ge 0.$$В первой строке выписана целевая функция - прибыль при выпуске $$Х_1$$ стульев и $$Х_2$$ столов. Ее требуется максимизировать, выбирая оптимальные значения переменных $$Х_1$$ и $$Х_2.$$ При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также и ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны. Если $$Х_1 = 0$$, то это значит, что стулья не выпускаются. Если же хоть один стул сделан, то $$Х_1$$ положительно. Но невозможно представить себе отрицательный выпуск - $$Х_1$$ не может быть отрицательным с экономической точки зрения, хотя с математической точки зрения такого ограничения усмотреть нельзя. В четвертой и пятой строчках задачи и констатируется, что переменные неотрицательны.
Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения $$Х_1$$, а по вертикальной оси ординат - значения $$Х_2$$. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения вектора $$(Х_1, Х_2) $$ объемов выпуска в виде треугольника (рис. 8.1).
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей второй строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось $$Х_1$$, соответствующую стульям, в точке (80, 0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось $$Х_2$$, соответствующую столам, в точке (0, 20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а не точное равенство - материал останется.
(рис 8.1)
Аналогичным образом можно изобразить и ограничения по труду (рис. 8.2).
(рис 8.2)
Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем отсечения от первого квадранта примыкающей к началу координат зоны. Отсечение проводится прямой, соответствующей третьей строке исходной задачи, с заменой неравенства на равенство. Прямая пересекает ось $$Х_1$$, соответствующую стульям, в точке (45, 0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось $$Х_2$$, соответствующую столам, в точке (0, 30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, а не точное равенство - часть рабочих будет простаивать.
Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих рук, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо "совместить" рис. 8.1 и рис. 8.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис. 8.3).
(рис 8.3)
Таким образом, множество возможных значений объемов выпуска стульев и столов $$(Х_1, Х_2) $$, или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис. 8.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис. 8.1 и рис. 8.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 \times 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 долларам США.
Двойственная задача. Каждой задаче линейного программирования соответствует так называемая
Почему
Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации задачи линейного программирования выделяются тем, что в них ограничения - системы линейных неравенств или равенств. Ограничения задают выпуклые линейные многогранники в конечном линейном пространстве. Целевые функции также линейны.
Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации организации производства и производственных процессов, например, процессов загрузки станков и раскройки листов материалов. После второй мировой войны аналогичными задачами занялись в США. В 1975 г. Т. Купманс (1910-1985, родился в Нидерландах, работал в основном в США) и академик АН СССР Л.В. Канторович были награждены Нобелевскими премиями по экономике.
Рассмотрим несколько типовых задач линейного программирования .
Задача о диете (упрощенный вариант) . Предположим для определенности, что необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ (для простоты, тиамина Т и ниацина Н).
| Содержание в 1 унции К | Содержание в 1 унции С | Потребность | |
|---|---|---|---|
| Вещество Т | 0,10 мг | 0,25 мг | 1,00 мг |
| Вещество Н | 1,00 мг | 0,25 мг | 5,00 мг |
| Калории | 110,00 | 120,00 | 400,00 |
| Стоимость 1 унции, в центах | 3,8 | 4,2 |
Пищевая ценность рациона (в калориях) должна быть не менее заданной. Пусть для простоты смесь для цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в табл. 8.1.
Задача линейного программирования имеет вид:
$$3,8 К + 4,2 С \to min ,\\ 0,10 К + 0,25 С \ge 1,00 ,\\ 1,00 К + 0,25 С \ge 5,00 ,\\ 110,00 К + 120,00 С \ge 400,00 ,\\ К \ge 0 ,\\ С \ge 0.$$Ее графическое решение представлено на рис. 8.4
(рис 8.4) Графическое решение задачи об оптимизации смеси
На рис. 8.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) на рис. 8.5 - это прямая, соответствующая целевой функции $$3,8 К + 4,2 С.$$ Она проходит между прямыми (1) и (4), задающими ограничения, и минимум достигается в точке А, через которую и проходит прямая (3). Следовательно, минимум равен $$3,8\times40/9 + 4,2\times20/9 = 236/9$$. Задача об оптимизации смеси полностью решена.
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны $$236/9$$. Интерпретация двойственных переменных: $$W_1 $$ - "стоимость" единицы вещества Т, а $$W_2$$ - "стоимость" единицы вещества Н, измеренные "по их вкладу" в целевую функцию. При этом $$W_3 = 0$$, поскольку ограничение на число калорий никак не участвует в формировании оптимального решения. Итак, $$W_1 , W_2 , W_3$$ - это т.н. объективно обусловленные оценки (по Л.В. Канторовичу) ресурсов (веществ Т и Н, калорий).
Планирование номенклатуры и объемов выпуска. Вернемся к организации производства. Предприятие может выпускать автоматические кухни (вид кастрюль), кофеварки и самовары. В табл. 8.2 приведены данные о производственных мощностях, имеющихся на предприятии (в штуках изделий).
| Кухни | Кофеварки | Самовары | |
|---|---|---|---|
| Штамповка | 20000 | 30000 | 12000 |
| Отделка | 30000 | 10000 | 10000 |
| Сборка | 20000 | 12000 | 8000 |
| Объем выпуска | Х1 | Х2 | Х3 |
| Удельная прибыль (на одно изделие) | 15 | 12 | 14 |
При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.
Задача линейного программирования имеет вид:
$$Х_1 \ge 0 , Х_2 \ge 0 , Х_3 \ge 0 $$ $$Х_1 / 200 + Х_2 / 300 + Х_3 / 120 \le 100 $$ $$Х_1 / 300 + Х_2 / 100 + Х_3 / 100 \le 100 $$ $$Х_1 / 200 \le 100 $$ $$Х_2 / 120 \le 100 $$ $$Х_3 / 80 \le 100 $$ $$F = 15 Х_1 + 12 Х_2 + 14 Х_3 \to max.$$Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).
Наконец, целевая функция $$F$$ - общая прибыль предприятия.
Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно из формулировки задачи линейного программирования исключить.
Отметим сразу любопытный факт. Как будет установлено, в оптимальном плане $$Х_3 = 0$$, т.е. самовары выпускать невыгодно.
Методы решения задач линейного программирования. Методы решения задач линейного программирования относятся к вычислительной математике, а не к экономике. Однако экономисту полезно знать о свойствах интеллектуального инструмента, которым он пользуется.
С ростом мощности компьютеров необходимость применения изощренных математических методов снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, оно весьма мало (доли секунд). Поэтому разберем лишь три метода.
Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа $$2Х_1 + 5Х_2 \le 10$$, то, очевидно, $$0 \le Х_1 \le 10/2 = 5 и 0 \le Х_2 \le 10/5 = 2$$. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.
Проведем перебор точек параллелепипеда с шагом $$1/10^n$$ последовательно при $$n=2,3,\dots$$, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до $$1/10^n$$.)
Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - с помощью т.н. метода случайного поиска) менять ее координаты на определенную величину $$\Delta$$, переходя каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до $$\Delta$$. Если необходимо, в окрестности найденного решения проводим направленный перебор с шагом $$\Delta/2 $$, $$\Delta/4$$ и т.д.)
Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл. 8.2.
Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:
$$F = 15 Х_1 + 12 Х_2 + 14 Х_3 \to max .\\ Х_1 / 200 + Х_2 / 300 + Х_3 / 120 \le 100 ,\\ Х_1 / 300 + Х_2 / 100 + Х_3 / 100 \le 100 ,\\ Х_3 / 80 \le 100.$$Неотрицательность переменных не будем специально указывать, поскольку в задачах линейного программирования это предположение всегда принимается.
В соответствии с симплекс-методом введем т.н. "свободные переменные" $$Х_4, Х_5, Х_6$$, соответствующие недоиспользованным мощностям, т.е. от системы неравенств перейдем к системе уравнений:
$$Х_1 / 200 + Х_2 / 300 + Х_3 / 120 + Х_4 = 100 ,\\ Х_1 / 300 + Х_2 / 100 + Х_3 / 100 + Х_5 = 100 ,\\ Х_3 / 80 + Х_6 = 100 ,\\ 15 Х_1 + 12 Х_2 + 14 Х_3 = F.$$У этой системы имеется очевидное решение, соответствующее одной из вершин многогранника допустимых значений переменных:
$$Х_1 = Х_2 = Х_3 = 0, Х_4 = Х_5 = Х_6 = 100, F = 0.$$В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.
В соответствии с симплекс-методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это $$Х_1.$$
Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной $$Х_1$$:
$$100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + \infty.$$Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.
Умножим первую строку на 200, чтобы получить $$Х_1$$ с единичным коэффициентом:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000.$$Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с $$Х_1$$, получим
$$7/900 Х_2 + 4/900 Х_3 - 2/3 Х_4 + Х_5 = 100/3.$$Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит $$F$$, получим:
$$2 Х_2 - 11 Х_3 - 3000 Х_4 = F - 300000.$$В результате система уравнений преобразуется к виду, в котором переменная $$Х_1$$ входит только в первое уравнение:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000 ,\\ 7/900 Х_2 + 4/900 Х_3 - 2/3 Х_4 + Х_5 = 100/3,\\ Х_3 / 80 + Х_6 = 100 ,\\ 2 Х_2 - 11 Х_3 - 3000 Х_4 = F - 300000.$$Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:
$$Х_1 = 20000, Х_2 = Х_3 = Х_4 = 0, Х_5 = 100/3, Х_6 = 100, F = 300000.$$В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.
Повторим описанную выше операцию. В строке с $$F$$ имеется еще один положительный коэффициент - при $$Х_2$$ (если бы положительных коэффициентов было несколько - мы взяли бы максимальный из них). На основе коэффициентов при $$Х_2$$ (а не при $$Х_1$$, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:
$$20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + \infty$$Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при $$Х_2$$ равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим $$Х_2$$, предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при $$Х_2$$ стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:
$$Х_1 + 9/7 Х_3 + 1800/7 Х_4 - 600/7 Х_5 = 120000/7, Х_2 + 4/7 Х_3 - 600/7 Х_4 + 900/7 Х_5 = 30000/7, Х_3 / 80 + Х_6 = 100 , - 85/7 Х_3 - 19800/7 Х_4 - 1800/7 Х_5 = F - 308571.$$Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при $$Х_3 = Х_4 = Х_5 = 0$$. Из остальных уравнений следует, что при этом $$Х_1 = 120000/7 = 17143, Х_2 = 30000/7 = 4286, Х_6 = 100$$. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.
Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т.е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В книге [8.1] приведен обширный перечень публикаций, посвященный многочисленным применениям линейного программирования в металлургии, угольной, химической, нефтяной, бумажной и прочих отраслях промышленности, в проблемах транспорта и связи, планирования производства, конструирования и хранения продукции, сельском хозяйстве, в научных исследованиях, в том числе экономических, и даже при регулировании уличного движения.
В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться. Поэтому затраты на доставку товара с определенного склада тому или иному потребителю можно считать известными.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 8.3.
В этой таблице, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада $$i, i = 1,2,3$$, потребителю $$j, j = 1,2,3,4$$. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется $$50+70 =120$$ единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл. 8.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
| Потреби-тель 1 | Потреби-тель 2 | Потреби-тель 3 | Потреби-тель 4 | Запасы на складах | |
|---|---|---|---|---|---|
| Склад 1 | 2 | 5 | 5 | 5 | 60 |
| Склад 2 | 1 | 2 | 1 | 4 | 80 |
| Склад 3 | 3 | 1 | 5 | 2 | 60 |
| Потреб-ности | 50 | 40 | 70 | 40 | 200 |
Надо спланировать перевозки, т.е. выбрать объемы $$Х_{ij}$$ поставок товара со склада i потребителю $$j,$$ где $$i = 1,2,3; j = 1,2,3,4$$. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:
$$X_{11} + Х_{12} + Х_{13} + Х_{14} = 60 ,\\ X_{21} + Х_{22} + Х_{23} + Х_{24} = 80 ,\\ X_{31} + Х_{32} + Х_{33} + Х_{34} = 60.$$Во-вторых, известны потребности клиентов:
$$X_{11} + Х_{21} + Х_{31} = 50,\\ X_{12} + Х_{22} + Х_{32} = 40,\\ X_{13} + Х_{23} + Х_{33} = 70,\\ X_{14} + Х_{24} + Х_{34} = 40.$$Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.
Целевая функция - издержки по перевозке, которые необходимо минимизировать:
$$F = 2 X_{11} + 5 Х_{12} + 4 Х_{13} + 5 Х_{14} + X_{21} + 2 Х_{22} + Х_{23} + 4 Х_{24} + +3 X_{31} + Х_{32} + 5 Х_{33} + 2 Х_{34} \to min.$$Кроме обсуждаемой, рассматриваются также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м2. Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м2 (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м2 и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.
Пусть Х - количество станков типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):
$$С = 7 Х + 3 У \to max.$$При этом должны быть выполнены следующие ограничения:
по стоимости (в тыс. долларов США)
$$5 Х + 2 У \le 20,$$по занимаемой площади (в м2 )
$$8 Х + 4 У \le 38,$$а также вновь появляющиеся специфические ограничения по целочисленности, а именно,
$$Х \ge 0 , У \ge 0 , Х и У$$ - целые числа.
Сформулированная математическая задача отличается от задачи линейного программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором.
Действительно, как ограничение по стоимости, так и ограничение по площади дают, что $$Х \le 4$$. Значит, Х может принимать лишь одно из 5 значений: 0, 1, 2, 3, 4.
Если $$Х = 4$$, то из ограничения по стоимости следует, что $$У = 0$$, а потому $$С = 7 Х = 28$$.
Если $$Х= 3$$, то из первого ограничения вытекает, что $$У \le 2$$, из второго $$У \le 3$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У =2$$, а именно $$С = 21 + 6 = 27$$.
Если $$Х= 2$$, то из первого ограничения следует, что $$У \le 5$$, из второго также $$У \le 5$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У =5$$, а именно $$С = 14 + 15 = 29$$.
Если $$Х= 1$$, то из первого ограничения имеем $$У \le 7$$, из второго также $$У \le 7$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У = 7$$, а именно $$С = 7 + 21 = 28$$.
Если $$Х= 0$$, то из первого ограничения вытекает $$У \le 10$$, из второго $$У \le 9$$. Значит, максимальное С при условии выполнения ограничений достигается при $$У = 9$$, а именно, $$С = 27$$.
Все возможные случаи рассмотрены. Максимальная производительность $$С = 29$$ (тысяч единиц продукции за смену) достигается при $$Х = 2, У = 5$$. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.
Задача о ранце. Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.
Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат - спутник Земли, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы.
С точки зрения экономики предприятия и организации производства более актуальна другая интерпретация задачи о ранце, в которой в качестве "предметов" рассматриваются заказы (или варианты выпуска партий тех или иных товаров), в качестве полезности - прибыль от выполнения того или иного заказа, а в качестве веса - себестоимость заказа.
Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные $$Х_k , k = 1,2,\dots, n$$ (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом $$Х_k = 1$$, если предмет размещают в ранце, и $$Х_k = 0$$, если нет, $$k = 1,2,\dots, n$$. Для каждого предмета известны две константы: $$А_k$$ - вес $$k$$ -го предмета, и $$С_k$$ - полезность $$k$$ -го предмета, $$k = 1,2,\dots, n.$$ Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид
$$C_1 Х_1 + С_2 Х_2 + С_3 Х_3 + \dots. + С_nХ_n \to max,\\ А_1 Х_1 + А_2 Х_2 + А_3 Х_3 + \dots. + А_nХ_n \le В.$$В отличие от предыдущих задач, управляющие параметры $$Х_k , k = 1,2,\dots, n $$, принимают значения из множества, содержащего два элемента - 0 и 1.
К
Укажем два распространенных метода решения задач
Метод приближения непрерывными задачами. В соответствии с ним сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки.
Методы направленного перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству $$Х$$ множества возможных решений $$Х_0$$ ставится в соответствие число - "граница" $$А(Х) $$. При решении задачи минимизации необходимо, чтобы $$А(Х_1) \ge А(Х_2) $$, если $$Х_1$$ входит в $$Х_2$$ или совпадает с $$Х_2.$$
Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества $$Х_С$$ на два - $$Х_{1С}$$ и $$Х_{2С}$$. При этом пересечение $$Х_{1С}$$ и $$Х_{2С}$$ пусто, а их объединение совпадает с $$Х_С$$. Затем вычисляют границы $$А(Х_{1С} ) $$ и $$А(Х_{2С})$$ и выделяют "ветвь" $$Х_{С+1}$$ - то из множеств $$Х_{1С}$$ и $$Х_{2С}$$, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа
Для каждой конкретной задачи
Один из разделов дискретной математики, часто используемый при принятии решений - теория графов. Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами (дуги называют также ребрами). Примеры графов приведены на рис. 8.5
(рис 8.5) Примеры графов
На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис. 8.6.
(рис 8.6) Примеры ориентированных графов
Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Задача коммивояжера. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.
Многие постановки экономического содержания сводятся к
Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис. 8.7).
(рис 8.7) Исходные данные к задаче о кратчайшем пути
Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл. 8.4). В этой таблице двум вершинам - началу пути и концу пути - ставится в соответствие время в пути. В табл. 8.4 рассматриваются пути без промежуточных остановок. Более сложные маршруты составляются из элементарных отрезков, перечисленных в табл. 8.4.
| Начало дуги | Конец дуги | Время в пути |
|---|---|---|
| 1 | 2 | 7 |
| 1 | 3 | 1 |
| 2 | 4 | 4 |
| 2 | 6 | 1 |
| 3 | 2 | 5 |
| 3 | 5 | 2 |
| 3 | 6 | 3 |
| 5 | 2 | 2 |
| 5 | 4 | 5 |
| 6 | 5 | 3 |
Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?
Решение. Введем обозначение: С(Т) - длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С(4) и указании пути, на котором этот минимум достигается.
Для исходных данных, представленных на pис. 8.7 и в табл. 8.4, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому $$С(3) = 1$$. Кроме того, очевидно, что $$С(1) = 0$$.
В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение
$$С(4) = min \{С(2) + 4; С(5) + 5\}.$$Таким образом, проведена реструктуризация (упрощение) задачи - нахождение $$С(4) $$ сведено к нахождению $$С(2) $$ и $$С(5) $$.
В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение
$$С(5) = min \{С(3) + 2; С(6) + 3\}.$$Мы знаем, что $$С(3) = 1$$. Поэтому
$$С(5) = min \{3; С(6) + 3\}.$$Поскольку очевидно, что $$С(6) $$ - положительное число, то из последнего соотношения вытекает, что $$С(5) = 3$$.
В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение
$$С(2) = min \{С(1) + 7; С(3) + 5; С(5) + 2\}.$$Нам известно, что $$С(1) = 0, С(3) = 1, С(5) = 3$$. Поэтому
$$С(2) = min \{0 + 7; 1 + 5; 3 + 2\} = 5.$$Теперь мы можем найти $$С(4) $$:
$$С(4) = min \{С(2) + 4; С(5) + 5\} = min \{5 + 4; 3 + 5\} = 8.$$Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков:
$$1 \to 3 \to 5 \to 4.$$Задача о кратчайшем пути для конкретных исходных данных (рис. 8.7 и табл. 8.4) полностью решена.
Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис. 8.8).
(рис 8.8) Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 8.8, можно также задать таблицей (табл. 8.5).
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 0 | 1 | 2 |
| 0 | 2 | 3 |
| 0 | 3 | 1 |
| 1 | 2 | 4 |
| 1 | 3 | 1 |
| 1 | 4 | 3 |
| 2 | 3 | 1 |
| 2 | 4 | 2 |
| 3 | 4 | 2 |
Решение
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.
Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 2. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл. 8.6).
| Пункт отправления | Пункт назначения | План перевозок | Пропускная способность |
|---|---|---|---|
| 0 | 1 | 2 | 2 |
| 0 | 2 | 3 | 3 |
| 0 | 3 | 1 | 1 |
| 1 | 2 | 0 | 4 |
| 1 | 3 | 0 | 1 |
| 1 | 4 | 2 | 3 |
| 2 | 3 | 1 | 1 |
| 2 | 4 | 2 | 2 |
| 3 | 4 | 2 | 2 |
Задача линейного программирования при максимизации потока. Дадим формулировку
Здесь $$F$$ - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен
О многообразии оптимизационных задач. В различных
Кроме затронутых выше методов решения задач оптимизации, напомним о том, что гладкие функции оптимизируют, приравнивая 0 производную (для функций нескольких переменных - частные производные). При наличии ограничений используют
Представляют интерес задачи оптимизации с
1. Изобразите на плоскости ограничения задачи линейного программирования и решите (графически) эту задачу:
$$400 W_1 + 450 W_2 \to min,\\ 5 W_1 + 10 W_2 \ge 45,\\ 20 W_1 + 15 W_2 \ge 80,\\ W_1 \ge 0, W_2 \ge 0.$$2. Решите задачу линейного программирования:
$$W_1 + 5 W_2 \to max, \\ 0,1 W_1 + W_2 \le 3,8 ,\\ 0,25 W_1 + 0,25 W_2 \le 4,2 ,\\ W_1 \ge 0 , W_2 \ge 0.$$3. Решите задачу
$$Х $$ и $$У $$ - целые числа.
4. Решите задачу о ранце:
$$Х_1 + Х_2 + 2Х_3 + 2Х_4 + Х_5 + Х_6 \to max,\\ 0,5 Х_1 + Х_2 + 1,5Х_3 + 2Х_4 + 2,5Х_5 + 3Х_6 \le 3.$$Управляющие параметры $$Х_k, k = 1,2,\dots, 6 ,$$ принимают значения из множества, содержащего два элемента - 0 и 1.
5. Транспортная сеть (с указанием расстояний) приведена на рис. 8.9. Найдите кратчайший путь из пункта 1 в пункт 4.
(рис 8.9) Исходные данные к задаче о кратчайшем пути
6. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис. 8.10) ограничена (табл. 8.7)?
(рис 8.10) Транспортная сеть к задаче о максимальном потоке
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 1 | 2 | 1 |
| 1 | 3 | 2 |
| 1 | 4 | 3 |
| 2 | 5 | 2 |
| 3 | 2 | 2 |
| 3 | 4 | 2 |
| 3 | 6 | 1 |
| 4 | 7 | 4 |
| 5 | 8 | 3 |
| 6 | 5 | 2 |
| 6 | 7 | 1 |
| 6 | 8 | 1 |
| 7 | 8 | 3 |
7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в ттабл. 8.8.
| Город отправления | Город назначения | Затраты на проезд |
|---|---|---|
| А | Б | 2 |
| А | В | 1 |
| А | Д | 5 |
| Б | А | 3 |
| Б | В | 2 |
| Б | Д | 1 |
| В | А | 4 |
| В | Б | 1 |
| В | Д | 2 |
| Д | Ф | 5 |
| Д | Б | 3 |
| Д | В | 3 |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.