Менеджмент: конспект лекций

программирования только последним условием целочисленности. Однако наличие этого условия позволяет (в данном конкретном случае) легко решить задачу перебором. Действительно, как ограничение по стоимости, так и ограничение по площади дают, что Х ≤ 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 1 Х 1 + С 2 Х 2 + С 3 Х 3 + …. + С n Х n → max,

А 1 Х 1 + А 2 Х 2 + А 3 Х 3 + …. + А n Х n ≤ В .

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

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

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

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

Методы направленного перебора . Из них наиболее известен метод ветвей и границ. Суть метода такова. Каждому подмножеству Х множества возможных решений Х 0 ставится в соответствие число – «граница» А (Х ). При решении задачи минимизации необходимо, чтобы А (Х 1) ≥ А (Х 2 ), если Х 1 входит в Х 2 или совпадает с Х 2 .

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

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

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

Один из разделов дискретной математики, часто используемый при принятии решений – теория графов. Граф – совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами (дуги называют также ребрами). На только что введенное понятие графа «навешиваются» новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой.

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

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

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

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

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

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

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