Задачи оптимизации при принятии решений

Надо спланировать перевозки, т.е. выбрать объемы Х_ij  поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во-первых, заданы запасы на складах:

X₁₁   + Х₁₂  + Х₁₃  + Х₁₄   = 60 ,

X₂₁   + Х₂₂  + Х₂₃  + Х₂₄   = 80 ,

X₃₁   + Х₃₂  + Х₃₃  + Х₃₄   = 60 .

Во-вторых, известны потребности  клиентов:

X₁₁   + Х₂₁ + Х₃₁  = 50 ,

X₁₂   + Х₂₂ + Х₃₂  = 40 ,

X₁₃   + Х₂₃ + Х₃₃  = 70 ,

X₁₄   + Х₂₄ + Х₃₄  = 40 .

Итак, всего 7 ограничений  типа равенств. Кроме того, все переменные неотрицательны - еще 12 ограничений.

Целевая функция - издержки по перевозке, которые необходимо минимизировать:

F = 2 X₁₁  + 5 Х₁₂  + 4 Х₁₃   + 5 Х₁₄  + X₂₁  + 2 Х₂₂   + Х₂₃  + 4 Х₂₄  +

+ +3 X₃₁  + Х₃₂  + 5 Х₃₃  + 2 Х₃₄  → min .

Кроме обсуждаемой, рассматриваются  также различные иные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.

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

3.2.2. Целочисленное  программирование

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

Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 20000 долларов США. При этом можно занять площадь не более 38 м². Имеется возможность приобрести станки типа А и станки типа Б. При этом станки типа А стоят 5000 долларов США, занимают площадь 8 м² (включая необходимые технологические проходы) и имеют производительность 7 тыс. единиц продукции за смену. Станки типа Б стоят 2000 долларов США, занимают площадь 4 м² и имеют производительность 3 тыс. единиц продукции за смену. Необходимо рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при заданных ограничениях максимум общей производительности участка.

Пусть Х - количество станков  типа А, а У - количество станков типа Б, входящих в комплект оборудования. Требуется выбрать комплект оборудования так, чтобы максимизировать производительность С участка (в тыс. единиц за смену):  

С = 7 Х + 3 У → max .

При этом должны быть выполнены  следующие ограничения:

по стоимости (в тыс. долларов США)

5 Х + 2 У ≤ 20,

по занимаемой площади (в  м² )

8 Х + 4 У ≤ 38,

а также вновь появляющиеся специфические ограничения по целочисленности, а именно,

Х ≥ 0 , У ≥ 0 , Х и У - целые числа.

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

Если Х = 4, то из ограничения по стоимости следует, что У = 0, а потому С = 7 Х = 28.

Если Х= 3, то из первого ограничения вытекает, что У ≤ 2, из второго У ≤ 3. Значит, максимальное С при условии выполнения ограничений достигается при У =2, а именно С = 21 + 6 = 27. 

Если Х= 2, то из первого ограничения следует, что У ≤ 5, из второго также У ≤ 5. Значит, максимальное С при условии выполнения ограничений достигается при У =5, а именно С = 14 + 15 = 29.

Если Х= 1, то из первого ограничения имеем У ≤ 7, из второго также У ≤ 7. Значит, максимальное С при условии выполнения ограничений достигается при У = 7, а именно С = 7 + 21 = 28.

Если Х= 0, то из первого ограничения вытекает У ≤ 10, из второго У ≤ 9. Значит, максимальное С при условии выполнения ограничений достигается при У = 9, а именно, С = 27.

Все возможные случаи рассмотрены. Максимальная производительность С = 29 (тысяч единиц продукции за смену) достигается при Х = 2, У = 5. Следовательно, надо покупать 2 станка типа А и 5 станков типа Б.

Задача о ранце. Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес каждого предмета известен.

Есть много эквивалентных  формулировок. Например, можно вместо ранца рассматривать космический  аппарат – спутник Земли, а  в качестве предметов - научные приборы. Тогда задача интерпретируется как  отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы.

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

Перейдем к математической постановке. Предполагается, что имеется n предметов, и для каждого из них  необходимо решить, класть его в  ранец или не класть. Для описания решения вводятся булевы переменные Х_k , k = 1,2,…, n (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом  Х_k = 1, если предмет размещают в ранце, и Х_k = 0, если нет, k = 1,2,…, n. Для каждого предмета известны две константы: А_k - вес k-го предмета, и  С_k - полезность k-го предмета, k = 1,2,…, n . Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид

C₁ Х₁ + С₂ Х₂ + С₃ Х₃ + …. + С_nХ_n  → max ,

А₁ Х₁ + А₂ Х₂ + А₃ Х₃ + …. + А_nХ_n   ≤ В.

В отличие от предыдущих задач, управляющие параметры Х_k , k = 1,2,…, n , принимают значения из множества, содержащего два элемента - 0 и 1.

К целочисленному программированию относятся задачи размещения (производственных объектов), теории расписаний, календарного и оперативного планирования, назначения персонала и т.д. (см., например, монографию [2]).

Укажем два распространенных метода решения задач целочисленного программирования

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

Методы направленного  перебора. Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х₀ ставится в соответствие число - "граница" А(Х). При решении задачи минимизации необходимо, чтобы А(Х₁) ≥ А(Х₂), если Х₁ входит в Х₂ или совпадает с Х₂ .

Каждый шаг метода ветвей и границ состоит в делении  выбранного на предыдущем шаге множества  Х_С  на два - Х_1С  и Х_2С. При этом пересечение Х_1С  и Х_2С пусто, а их объединение совпадает с  Х_С . Затем вычисляют границы  А(Х_1С ) и А(Х_2С) и выделяют "ветвь" Х_С+1  - то из множеств Х_1С  и Х_2С, для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа

Для каждой конкретной задачи целочисленного программирования (другими  словами, дискретной оптимизации) метод  ветвей и границ реализуется по-своему. Есть много модификаций этого  метода. 

 

3.2.3. Теория графов  и оптимизация

Один из разделов дискретной математики, часто используемый при  принятии решений - теория графов (см., например, учебные пособия [3,4]). Граф - это совокупность точек, называемых вершинами графа, некоторые из которых  соединены дугами (дуги назыыают также  ребрами). Примеры графов приведены  на рис.5.

	Рис.5. Примеры графов.

 

   

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

Рис.6. Примеры ориентированных  графов.

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

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

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

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

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

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

Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.7).

 

Рис.7. Исходные данные к задаче о кратчайшем пути. 

 

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

Таблица 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) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис.7 и в табл.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 → 3 → 5 → 4 .

Задача о кратчайшем пути для конкретных исходных данных (рис.7 и табл.4) полностью решена.

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

Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?

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