Начнем с некоторых методов, используемых в стратегическом менеджменте, а затем перейдем к оптимизационным задачам.
Рассмотрим несколько широко используемых практических инструментов принятия решений в стратегическом менеджменте.
Информация и инструменты стратегического планирования. Исходными пунктами
На основе перечисленных данных в соответствии с миссией фирмы выбираются цели на длительную перспективу и анализируются ресурсы, которые для этого необходимы. Инструментами
При анализе "разрывов " сравнивают три возможных сценария развития фирмы:
Разницу между результатами по сценариям Б и А называют оперативным разрывом, а между результатами по сценариям В и Б - стратегическим разрывом. Эта терминология подчеркивает роль нововведений в стратегическом плане фирмы - разработки новых продуктов или выхода на новые рынки, или и того и другого вместе.
Матрица портфеля Бостонской консалтинговой группы. Может оказаться полезным анализ портфеля предприятия (табл.4.1). Надо иметь в виду, что речь идет не о стратегическом планировании для всего предприятия, а для его "стратегических подразделений ". Они выделяются комбинациями "продукт-рынок ", которые:
| Высокий | 1. Звезды | 3. Знак вопроса |
| Низкий | 2. Дойные коровы | 4. Собаки |
| Рост спроса / рыночная доля | Высокая | Низкая |
Внеся товары (с учетом их доли в обороте фирмы) в соответствующие клетки табл.4.1, можно рассчитать долю особо успешных товаров типа 1 (Звезды), которые, возможно, нуждаются в дальнейшем финансировании для увеличения и закрепления успеха. Хотя рост спроса на товары типа 2 (Дойные коровы) низок, но из-за большой доли рынка они могут еще долго приносить хороший доход на мало меняющихся (стагнирующих) рынках. Судьба товаров типа 3 (Знак вопроса) неясна. Оправданы ли большие финансовые затраты на расширение их доли на рынке? Товары типа 4 (Собаки) "зарабатывают " лишь себе на жизнь.
На основе анализа табл.4.1 можно проанализировать несколько возможных стратегий:
При определении целей и стратегий дальнейшего развития стратегические подразделения нуждаются во взаимной координации, однако без подавления их самобытности (другими словами, со стороны руководства фирмы должно осуществляться контролируемое децентрализованное руководство). Руководство фирмы должно направить отдельные подразделения на привлекательные рынки, обнаружить и использовать синергетический эффект от их взаимодействия и рационально распределить ресурсы. Так, руководство фирмы должно способствовать тому, чтобы "дойные коровы " передали часть дохода "звездам ".
В табл. 4.1 сопоставлены такие характеристики выпускаемого товара, как "рост спроса " и "доля рынка". Ясно, что высокий рост соответствует ранней стадии жизненного цикла товара, а низкий - поздней стадии. Обычно высокая доля рынка сигнализирует о продолжительном периоде получения прибыли, а низкая - о коротком. Так, высокая доля рынка может быть из-за слабой конкуренции. Рыночный лидер может иметь преимущество в издержках на одно изделие -
Методы списка и суммарной оценки. Широко используемыми и весьма полезными инструментами
| Продукты Факторы | А | Б | В |
|---|---|---|---|
| Степень |
Хорошо | средне | плохо |
| Число возможных покупателей | Плохо | хорошо | Средне |
| Готовность к |
Средне | хорошо | Хорошо |
| Барьеры для вхождения новых продавцов | Хорошо | плохо | Плохо |
| Обеспеченность сырьем | Плохо | средне | Хорошо |
Обратите внимание, что оценки даются в качественном виде (измерены в порядковой шкале - см. ниже). Любая количественная определенность была бы при подобных оценках лишь иллюзией.
Целесообразно разделить факторы на "обязательные ", "необходимые " и "желательные ", т.е. ввести веса факторов, выраженные в качественном виде. Правило принятия решения может иметь вид: "Форсируй планирование тех стратегий типа "продукт-рынок ", при которых все обязательные факторы и по меньшей мере два необходимых соответствуют оценке "хорошо " ".
Методу проверочного списка, в котором как оценки отдельных факторов, так и веса факторов и способы принятия решений имеют качественный характер, соответствует количественный двойник - метод суммарной оценки.
Конечно, с числами оперировать гораздо легче, чем с качественными оценками. Недаром математики обычно рвутся "оцифровать" качественные факторы и веса. Но при этом, как мы знаем из теории измерений, в окончательные выводы может быть внесен субъективизм, связанный с выбором способа "оцифровки" качественных оценок и весов.
Рассмотрим условный пример по вычислению и использованию единой суммарной оценки. Пусть оценки факторов 1 и 2 для продуктов А и Б даны в табл.4.3 (для простоты изложения мы опускаем способы получения численных значений в табл.6 и не рассматриваем погрешности этих значений).
Для получения суммарной оценки необходимо знать веса факторов. Пусть фактор 1 оценивается экспертами как вдвое более важный, чем фактор 2. Поскольку сумма весов факторов должна составлять 1, то вес фактора 1 есть 0,67, а фактора 2 - 0,33.
| Продукты Факторы | А | Б |
|---|---|---|
| 1 | 40 % | 90 % |
| 2 | 50 % | 20 % |
Суммарная оценка по продукту $$А$$ равна
$$0.67 \times 40 + 0,33 \times 50 = 26,8 + 16,5 = 43,3$$ %,
а суммарная оценка по продукту $$Б$$ равна
$$0.67 \times 90 + 0,33 \times 20 = 60,3 + 6,6 = 66,9$$ %.
Однако получение суммарных оценок - только этап процесса принятия решений. Нужен еще
Отметим, что принятие решения на основе границы несколько снижает влияние конкретных правил оцифровки. Например, если для продукта $$А$$ оценки по факторам $$А$$ и $$Б$$ поднимутся на 10 % и достигнут соответственно значений 50% и 60 %, то суммарная оценка окажется равной
$$0.67 \times 50 + 0,33 \times 60 = 33,5 + 19,8 = 53,3 $$т.е. общее решение не меняется, продукт А остается среди малоперспективных.
Менеджер - главное лицо в перспективном планировании. Если прогнозирование - научно-исследовательская работа, ее результаты можно сравнить с прожектором, освещающим основные черты грядущего, то планирование - частный вид принятия решений. Для
Однако все эти простые или хитроумные компьютерные приемы - лишь подспорье для менеджера. Именно он несет ответственность за судьбу фирмы, и именно на свое знание дела, на свою интуицию он должен полагаться при принятии решений в стратегическом менеджменте.
Среди оптимизационных задач в теории принятия решений наиболее известны
Производственная задача. Цех может производить стулья и столы. На производство стула идет 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.$$В первой строке выписана
Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси
(рис 4.1) Ограничения по материалу
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем
Аналогичным образом можно изобразить и ограничения по труду (рис.4.2).
(рис 4.2) Ограничения по труду
Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем
Чтобы ответить на этот вопрос, надо "совместить" рис.4.1 и рис.4.2, получив область возможных решений, а затем проследить, какие значения принимает
(рис 4.3) Основная идея линейного программирования
Таким образом, множество возможных значений объемов выпуска стульев и столов ( $$X_1 , X_2 $$ ), или, в других терминах, множество $$А $$, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.4.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис. 4.1 и рис. 4.2, т.е. решение системы уравнений
$$5 X_1 + 20 X_2 = 400 \\ 10 X_1 + 15 X_2 = 450.$$Из первого уравнения: $$5 X_1 = 400 - 20 X_2 , X_1 = 80 - 4 X_2 $$. Подставляем во второе уравнение:
$$10 (80 - 4 X_2) + 15 X_2 = 800 - 40X_2 + 15 X_2 = 800 - 25 X_2 = 450,$$следовательно, $$25 X_2 = 350, X_2 = 14 $$, откуда $$X_1 = 80 - 4 х 14 = 80 -56 =24 $$. Итак, четвертая вершина четырехугольника - это (24, 14).
Надо найти максимум
Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.
Двойственная задача. Каждой
Почему
Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации
Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации
Рассмотрим несколько
Задача об оптимизации смеси (упрощенный вариант). На химическом комбинате для оптимизации технологического процесса надо составить самую дешевую смесь, содержащую необходимое количество определенных веществ (обозначим их Т и Н). Энергетическая ценность смеси (в калориях) должна быть не менее заданной. Пусть для простоты смесь составляется из двух компонентов - К и С. Сколько каждого из них взять для включения в смесь? Исходные данные для расчетов приведены в табл.4.4.
| Содержание в 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 |
Ее графическое решение представлено на рис. 4.4.
(рис 4.4) Графическое решение задачи об оптимизации смеси
На рис. 4.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая $$1,00К + 0,25С = 5,00$$ (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси
Прямая (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) на оси
Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых). Область допустимых значений параметров (К, С) можно назвать "неограниченным многоугольником". Минимум
Из второго уравнения $$К = 5 - 0,25 С$$, из первого $$0,10 (5 - 0,25 С) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1$$, откуда $$С = 0,5/0,225 = 20/9$$ и $$К = 5 - 5/9 = 40/9$$. Итак, $$А = (40/9; 20/9) $$.
Прямая (3) на рис. 4.4 - это прямая, соответствующая
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны $$236/9$$. Интерпретация двойственных переменных: $$W_1$$ - "стоимость" единицы вещества $$Т$$, а $$W_2$$ - "стоимость" единицы вещества Н, измеренные "по их вкладу" в
Планирование номенклатуры и объемов выпуска. Вернемся к
| Кухни | Кофеварки | Самовары | |
|---|---|---|---|
| Штамповка | 20000 | 30000 | 12000 |
| Отделка | 30000 | 10000 | 10000 |
| Сборка | 20000 | 12000 | 8000 |
| Объем выпуска | $$Х_1$$ | $$Х_2$$ | $$Х_3$$ |
| Удельная прибыль (на одно изделие) | 15 | 12 | 14 |
При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.
Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).
Наконец,
Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно сразу отбросить.
Отметим сразу любопытный факт. Как будет установлено, в
Методы решения задач линейного программирования. Методы решения
С ростом мощности компьютеров необходимость применения изощренных методов снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, поскольку весьма мало (доли секунд). Поэтому мы разберем лишь три метода.
Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа $$2Х_1 + 5Х_2 \le 10$$, то, очевидно, $$0 \le Х_1 \le 10/2 = 5 $$ и $$0 \le Х_2 \le 10/2 = 5 $$. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.
Проведем перебор точек параллелепипеда с шагом $$1/10^n $$ последовательно при $$n=2,3,\dots$$, вычисляя значения
Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину $$\Delta$$, каждый раз в точку с более высоким значением
Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение
Рассмотрим задачу
Неотрицательность переменных не будем специально указывать, поскольку в
В соответствии с
У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:
$$Х_1 = Х_2 = Х_3 = 0, Х_4 = Х_5 = Х_6 = 100, F = 0.$$В терминах исходной задачи это значит, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.
Выбираем переменную, которая входит в
Сравниваем частные от деления
Выбираем строку, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.
Умножим первую строку на 200, чтобы получить $$Х_1$$ с единичным коэффициентом:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000.$$Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим
$$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$$, как в первый раз) образуем частные от деления соответствующих
Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 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. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных
В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 4.6.
| Потреби-тель 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 |
В табл.4.6, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i=1,2,3, потребителю j, j=1,2,3,4.. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется $$50+70 =120$$ единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.5 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
Надо спланировать перевозки, т.е. выбрать объемы $$Х_{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 ограничений.
Рассматриваются также различные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Рассмотрим принципиально иной тип оптимизационных постановок, часто использующихся в задачах управления экономическими явлениями и процессами. В
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 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,$$ Х и У - целые числа.
Сформулированная математическая задача отличается от
Если $$Х = 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. К
Укажем два метода решения задач
Метод приближения непрерывными задачами. В соответствии с ним сначала решается
Методы направленного перебора. Из них наиболее известен
Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества $$Х_С$$ на два - $$Х_{1С} и Х_{2С}.$$ При этом пересечение $$Х_{1С}$$ и $$Х_{2С}$$ пусто, а их объединение совпадает с $$Х_С.$$ Затем вычисляют границы $$А(Х_{1С})$$ и $$А(Х_{2С})$$ и выделяют "ветвь" $$Х|_{С +1}$$ - то из множеств $$Х_{1С}$$ и $$Х_{2С},$$ для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа.
Для каждой конкретной задачи
Один из разделов дискретной математики, часто используемый при принятии решений - теория графов. Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.4.5.
(рис 4.5) Примеры графов
На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.4.6.
(рис 4.6) Примеры ориентированных графов
Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Задача коммивояжера.Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.
Многие постановки экономического содержания сводятся к
Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.4.7).
(рис 4.7) Исходные данные к задаче о кратчайшем пути
Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.4.7).
| Начало дуги | Конец дуги | Время в пути |
|---|---|---|
| 1 | 2 | 7 |
| 1 | 3 | 1 |
| 2 | 3 | 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) и указании пути, на котором этот минимум достигается.
Для исходных данных, представленных на рис.4.7 и в табл.4.6, в вершину 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$$Задача о кратчайшем пути для конкретных исходных данных (рис.4.77 и табл.4.7) полностью решена.
Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис.4.8).
(рис 4.8) Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.4.8, можно также задать таблицей (табл.4.8).
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 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 единица из пункта 3. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл.4.9).
| Пункт отправления | Пункт назначения | План перевозок | Пропускная способность |
|---|---|---|---|
| 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. Какой образец мотоцикла запустить в серию? Исходные данные для принятия решения приведены в табл.4.10. Разберите четыре критерия принятия решения: пессимистичный, оптимистичный, средней прибыли, минимальной упущенной выгоды.
| Цена бензина и ее шансы | Мотоцикл "Витязь" | Мотоцикл "Комар" |
|---|---|---|
| Низкая (20 % ) | 900 | 700 |
| Средняя (60%) | 700 | 600 |
| Высокая (20 % ) | 100 | 400 |
2. Изобразите на плоскости ограничения
3. Решите задачу
4. Решите задачу
$$Х и У$$ - целые числа.
5. Решите задачу о ранце:
$$Х_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.
6.
(рис 4.9) Транспортная сеть к задаче о кратчайшем пути
7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл.4.11.
| Город отправления | Город назначения | Затраты на проезд |
|---|---|---|
| А | Б | 2 |
| А | В | 1 |
| А | Д | 5 |
| Б | А | 3 |
| Б | В | 2 |
| Б | Д | 1 |
| В | А | 4 |
| В | Б | 1 |
| В | Д | 2 |
| Д | А | 5 |
| Д | Б | 3 |
| Д | В | 3 |
8. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис.4.10) ограничена (табл.4.12)?
(рис 4.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 |
Начнем с некоторых методов, используемых в стратегическом менеджменте, а затем перейдем к оптимизационным задачам.
Рассмотрим несколько широко используемых практических инструментов принятия решений в стратегическом менеджменте.
Информация и инструменты стратегического планирования. Исходными пунктами
На основе перечисленных данных в соответствии с миссией фирмы выбираются цели на длительную перспективу и анализируются ресурсы, которые для этого необходимы. Инструментами
При анализе "разрывов " сравнивают три возможных сценария развития фирмы:
Разницу между результатами по сценариям Б и А называют оперативным разрывом, а между результатами по сценариям В и Б - стратегическим разрывом. Эта терминология подчеркивает роль нововведений в стратегическом плане фирмы - разработки новых продуктов или выхода на новые рынки, или и того и другого вместе.
Матрица портфеля Бостонской консалтинговой группы. Может оказаться полезным анализ портфеля предприятия (табл.4.1). Надо иметь в виду, что речь идет не о стратегическом планировании для всего предприятия, а для его "стратегических подразделений ". Они выделяются комбинациями "продукт-рынок ", которые:
| Высокий | 1. Звезды | 3. Знак вопроса |
| Низкий | 2. Дойные коровы | 4. Собаки |
| Рост спроса / рыночная доля | Высокая | Низкая |
Внеся товары (с учетом их доли в обороте фирмы) в соответствующие клетки табл.4.1, можно рассчитать долю особо успешных товаров типа 1 (Звезды), которые, возможно, нуждаются в дальнейшем финансировании для увеличения и закрепления успеха. Хотя рост спроса на товары типа 2 (Дойные коровы) низок, но из-за большой доли рынка они могут еще долго приносить хороший доход на мало меняющихся (стагнирующих) рынках. Судьба товаров типа 3 (Знак вопроса) неясна. Оправданы ли большие финансовые затраты на расширение их доли на рынке? Товары типа 4 (Собаки) "зарабатывают " лишь себе на жизнь.
На основе анализа табл.4.1 можно проанализировать несколько возможных стратегий:
При определении целей и стратегий дальнейшего развития стратегические подразделения нуждаются во взаимной координации, однако без подавления их самобытности (другими словами, со стороны руководства фирмы должно осуществляться контролируемое децентрализованное руководство). Руководство фирмы должно направить отдельные подразделения на привлекательные рынки, обнаружить и использовать синергетический эффект от их взаимодействия и рационально распределить ресурсы. Так, руководство фирмы должно способствовать тому, чтобы "дойные коровы " передали часть дохода "звездам ".
В табл. 4.1 сопоставлены такие характеристики выпускаемого товара, как "рост спроса " и "доля рынка". Ясно, что высокий рост соответствует ранней стадии жизненного цикла товара, а низкий - поздней стадии. Обычно высокая доля рынка сигнализирует о продолжительном периоде получения прибыли, а низкая - о коротком. Так, высокая доля рынка может быть из-за слабой конкуренции. Рыночный лидер может иметь преимущество в издержках на одно изделие -
Методы списка и суммарной оценки. Широко используемыми и весьма полезными инструментами
| Продукты Факторы | А | Б | В |
|---|---|---|---|
| Степень |
Хорошо | средне | плохо |
| Число возможных покупателей | Плохо | хорошо | Средне |
| Готовность к |
Средне | хорошо | Хорошо |
| Барьеры для вхождения новых продавцов | Хорошо | плохо | Плохо |
| Обеспеченность сырьем | Плохо | средне | Хорошо |
Обратите внимание, что оценки даются в качественном виде (измерены в порядковой шкале - см. ниже). Любая количественная определенность была бы при подобных оценках лишь иллюзией.
Целесообразно разделить факторы на "обязательные ", "необходимые " и "желательные ", т.е. ввести веса факторов, выраженные в качественном виде. Правило принятия решения может иметь вид: "Форсируй планирование тех стратегий типа "продукт-рынок ", при которых все обязательные факторы и по меньшей мере два необходимых соответствуют оценке "хорошо " ".
Методу проверочного списка, в котором как оценки отдельных факторов, так и веса факторов и способы принятия решений имеют качественный характер, соответствует количественный двойник - метод суммарной оценки.
Конечно, с числами оперировать гораздо легче, чем с качественными оценками. Недаром математики обычно рвутся "оцифровать" качественные факторы и веса. Но при этом, как мы знаем из теории измерений, в окончательные выводы может быть внесен субъективизм, связанный с выбором способа "оцифровки" качественных оценок и весов.
Рассмотрим условный пример по вычислению и использованию единой суммарной оценки. Пусть оценки факторов 1 и 2 для продуктов А и Б даны в табл.4.3 (для простоты изложения мы опускаем способы получения численных значений в табл.6 и не рассматриваем погрешности этих значений).
Для получения суммарной оценки необходимо знать веса факторов. Пусть фактор 1 оценивается экспертами как вдвое более важный, чем фактор 2. Поскольку сумма весов факторов должна составлять 1, то вес фактора 1 есть 0,67, а фактора 2 - 0,33.
| Продукты Факторы | А | Б |
|---|---|---|
| 1 | 40 % | 90 % |
| 2 | 50 % | 20 % |
Суммарная оценка по продукту $$А$$ равна
$$0.67 \times 40 + 0,33 \times 50 = 26,8 + 16,5 = 43,3$$ %,
а суммарная оценка по продукту $$Б$$ равна
$$0.67 \times 90 + 0,33 \times 20 = 60,3 + 6,6 = 66,9$$ %.
Однако получение суммарных оценок - только этап процесса принятия решений. Нужен еще
Отметим, что принятие решения на основе границы несколько снижает влияние конкретных правил оцифровки. Например, если для продукта $$А$$ оценки по факторам $$А$$ и $$Б$$ поднимутся на 10 % и достигнут соответственно значений 50% и 60 %, то суммарная оценка окажется равной
$$0.67 \times 50 + 0,33 \times 60 = 33,5 + 19,8 = 53,3 $$т.е. общее решение не меняется, продукт А остается среди малоперспективных.
Менеджер - главное лицо в перспективном планировании. Если прогнозирование - научно-исследовательская работа, ее результаты можно сравнить с прожектором, освещающим основные черты грядущего, то планирование - частный вид принятия решений. Для
Однако все эти простые или хитроумные компьютерные приемы - лишь подспорье для менеджера. Именно он несет ответственность за судьбу фирмы, и именно на свое знание дела, на свою интуицию он должен полагаться при принятии решений в стратегическом менеджменте.
Среди оптимизационных задач в теории принятия решений наиболее известны
Производственная задача. Цех может производить стулья и столы. На производство стула идет 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.$$В первой строке выписана
Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси
(рис 4.1) Ограничения по материалу
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Этот треугольник получается путем
Аналогичным образом можно изобразить и ограничения по труду (рис.4.2).
(рис 4.2) Ограничения по труду
Таким образом, ограничения по труду, как и ограничения по материалу, изображаются в виде треугольника. Этот треугольник также получается путем
Чтобы ответить на этот вопрос, надо "совместить" рис.4.1 и рис.4.2, получив область возможных решений, а затем проследить, какие значения принимает
(рис 4.3) Основная идея линейного программирования
Таким образом, множество возможных значений объемов выпуска стульев и столов ( $$X_1 , X_2 $$ ), или, в других терминах, множество $$А $$, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.4.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис. 4.1 и рис. 4.2, т.е. решение системы уравнений
$$5 X_1 + 20 X_2 = 400 \\ 10 X_1 + 15 X_2 = 450.$$Из первого уравнения: $$5 X_1 = 400 - 20 X_2 , X_1 = 80 - 4 X_2 $$. Подставляем во второе уравнение:
$$10 (80 - 4 X_2) + 15 X_2 = 800 - 40X_2 + 15 X_2 = 800 - 25 X_2 = 450,$$следовательно, $$25 X_2 = 350, X_2 = 14 $$, откуда $$X_1 = 80 - 4 х 14 = 80 -56 =24 $$. Итак, четвертая вершина четырехугольника - это (24, 14).
Надо найти максимум
Таким образом, оптимальный выпуск таков: 24 стула и 14 столов. При этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 долларам США.
Двойственная задача. Каждой
Почему
Линейное программирование как научно-практическая дисциплина. Из всех задач оптимизации
Впервые такие задачи решались советским математиком Л.В. Канторовичем (1912-1986) в 1930-х годах как задачи производственного менеджмента с целью оптимизации
Рассмотрим несколько
Задача об оптимизации смеси (упрощенный вариант). На химическом комбинате для оптимизации технологического процесса надо составить самую дешевую смесь, содержащую необходимое количество определенных веществ (обозначим их Т и Н). Энергетическая ценность смеси (в калориях) должна быть не менее заданной. Пусть для простоты смесь составляется из двух компонентов - К и С. Сколько каждого из них взять для включения в смесь? Исходные данные для расчетов приведены в табл.4.4.
| Содержание в 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 |
Ее графическое решение представлено на рис. 4.4.
(рис 4.4) Графическое решение задачи об оптимизации смеси
На рис. 4.4 ради облегчения восприятия четыре прямые обозначены номерами (1) - (4). Прямая (1) - это прямая $$1,00К + 0,25С = 5,00$$ (ограничение по веществу Н). Она проходит, как и показано на рисунке, через точки (5,0) на оси
Прямая (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) на оси
Следовательно, область допустимых значений параметров (К, С) является неограниченной сверху. Из всей плоскости она выделяется осями координат (лежит в первом квадранте) и прямыми (1) и (4) (лежит выше этих прямых). Область допустимых значений параметров (К, С) можно назвать "неограниченным многоугольником". Минимум
Из второго уравнения $$К = 5 - 0,25 С$$, из первого $$0,10 (5 - 0,25 С) + 0,25 С = 0,5 - 0,025 С + 0,25 С = 0,5 + 0,225 С = 1$$, откуда $$С = 0,5/0,225 = 20/9$$ и $$К = 5 - 5/9 = 40/9$$. Итак, $$А = (40/9; 20/9) $$.
Прямая (3) на рис. 4.4 - это прямая, соответствующая
Минимальное значение в прямой задаче, как и должно быть, равно максимальному значению в двойственной задаче, т.е. оба числа равны $$236/9$$. Интерпретация двойственных переменных: $$W_1$$ - "стоимость" единицы вещества $$Т$$, а $$W_2$$ - "стоимость" единицы вещества Н, измеренные "по их вкладу" в
Планирование номенклатуры и объемов выпуска. Вернемся к
| Кухни | Кофеварки | Самовары | |
|---|---|---|---|
| Штамповка | 20000 | 30000 | 12000 |
| Отделка | 30000 | 10000 | 10000 |
| Сборка | 20000 | 12000 | 8000 |
| Объем выпуска | $$Х_1$$ | $$Х_2$$ | $$Х_3$$ |
| Удельная прибыль (на одно изделие) | 15 | 12 | 14 |
При этом штамповка и отделка проводятся на одном и том же оборудовании. Оно позволяет штамповать за заданное время или 20000 кухонь, либо 30000 кофеварок, либо и то, и другое, не в меньшем количестве. А вот сборка проводится на отдельных участках.
Здесь:
(0) - обычное в экономике условие неотрицательности переменных,
(1) - ограничение по возможностям штамповки (выраженное для облегчения восприятия в процентах),
(2) - ограничение по возможностям отделки,
(3) - ограничение по сборке для кухонь,
(4) - то же для кофемолок,
(5) - то же для самоваров (как уже говорилось, все три вида изделий собираются на отдельных линиях).
Наконец,
Заметим, что неравенство (3) вытекает из неравенства (1), а неравенство (4) - из (2). Поэтому неравенства (3) и (4) можно сразу отбросить.
Отметим сразу любопытный факт. Как будет установлено, в
Методы решения задач линейного программирования. Методы решения
С ростом мощности компьютеров необходимость применения изощренных методов снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, поскольку весьма мало (доли секунд). Поэтому мы разберем лишь три метода.
Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа $$2Х_1 + 5Х_2 \le 10$$, то, очевидно, $$0 \le Х_1 \le 10/2 = 5 $$ и $$0 \le Х_2 \le 10/2 = 5 $$. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.
Проведем перебор точек параллелепипеда с шагом $$1/10^n $$ последовательно при $$n=2,3,\dots$$, вычисляя значения
Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину $$\Delta$$, каждый раз в точку с более высоким значением
Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение
Рассмотрим задачу
Неотрицательность переменных не будем специально указывать, поскольку в
В соответствии с
У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:
$$Х_1 = Х_2 = Х_3 = 0, Х_4 = Х_5 = Х_6 = 100, F = 0.$$В терминах исходной задачи это значит, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.
Выбираем переменную, которая входит в
Сравниваем частные от деления
Выбираем строку, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.
Умножим первую строку на 200, чтобы получить $$Х_1$$ с единичным коэффициентом:
$$Х_1 + 2/3 Х_2 + 2/1,2 Х_3 + 200 Х_4 = 20000.$$Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим
$$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$$, как в первый раз) образуем частные от деления соответствующих
Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 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. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.
Транспортная задача. Различные технико-экономические и экономические задачи производственного менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных
В качестве очередного примера рассмотрим т.н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать "прикрепление" потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.
Например, может идти речь о перевозке песка - сырья для производства кирпичей. В Москву песок обычно доставляется самым дешевым транспортом - водным. Поэтому в качестве складов можно рассматривать порты, а в качестве запасов - их суточную пропускную способность. Потребителями являются кирпичные заводы, а их потребности определяются суточным производством (в соответствии с имеющимися заказами). Для доставки необходимо загрузить автотранспорт, проехать по определенному маршруту и разгрузить его. Стоимость этих операций рассчитывается по известным правилам, на которых не имеет смысла останавливаться.
Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 4.6.
| Потреби-тель 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 |
В табл.4.6, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i=1,2,3, потребителю j, j=1,2,3,4.. Например, самая дешевая доставка - со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется $$50+70 =120$$ единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.5 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение - при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.
Надо спланировать перевозки, т.е. выбрать объемы $$Х_{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 ограничений.
Рассматриваются также различные варианты транспортной задачи. Например, если доставка производится вагонами, то объемы поставок должны быть кратны вместимости вагона.
Количество переменных и ограничений в транспортной задаче таково, что для ее решения не обойтись без компьютера и соответствующего программного продукта.
Рассмотрим принципиально иной тип оптимизационных постановок, часто использующихся в задачах управления экономическими явлениями и процессами. В
Задачи оптимизации, в которых переменные принимают целочисленные значения, относятся к
Задача о выборе оборудования. На приобретение оборудования для нового участка цеха выделено 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,$$ Х и У - целые числа.
Сформулированная математическая задача отличается от
Если $$Х = 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. К
Укажем два метода решения задач
Метод приближения непрерывными задачами. В соответствии с ним сначала решается
Методы направленного перебора. Из них наиболее известен
Каждый шаг метода ветвей и границ состоит в делении выбранного на предыдущем шаге множества $$Х_С$$ на два - $$Х_{1С} и Х_{2С}.$$ При этом пересечение $$Х_{1С}$$ и $$Х_{2С}$$ пусто, а их объединение совпадает с $$Х_С.$$ Затем вычисляют границы $$А(Х_{1С})$$ и $$А(Х_{2С})$$ и выделяют "ветвь" $$Х|_{С +1}$$ - то из множеств $$Х_{1С}$$ и $$Х_{2С},$$ для которого граница меньше. Алгоритм прекращает работу, когда диаметр вновь выделенной ветви оказывается меньше заранее заданного малого числа.
Для каждой конкретной задачи
Один из разделов дискретной математики, часто используемый при принятии решений - теория графов. Граф - это совокупность точек, называемых вершинами графа, некоторые из которых соединены дугами. Примеры графов приведены на рис.4.5.
(рис 4.5) Примеры графов
На только что введенное понятие графа "навешиваются" новые свойства. Исходному объекту приписывают новые качества. Например, вводится и используется понятие ориентированного графа. В таком графе дуги имеют стрелки, направленные от одной вершины к другой. Примеры ориентированных графов даны на рис.4.6.
(рис 4.6) Примеры ориентированных графов
Ориентированный граф был бы полезен, например, для иллюстрации организации перевозок в транспортной задаче. В экономике дугам ориентированного или обычного графа часто приписывают числа, например, стоимость проезда или перевозки груза из пункта А (начальная вершина дуги) в пункт Б (конечная вершина дуги).
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Задача коммивояжера.Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).
Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.
Многие постановки экономического содержания сводятся к
Задача о кратчайшем пути. Как кратчайшим путем попасть из одной вершины графа в другую? В терминах производственного менеджмента: как кратчайшим путем (и, следовательно, с наименьшим расходом топлива и времени, наиболее дешево) попасть из пункта А в пункт Б? Для решения этой задачи каждой дуге ориентированного графа должно быть сопоставлено число - время движения по этой дуге от начальной вершины до конечной. Рассмотрим пример (рис.4.7).
(рис 4.7) Исходные данные к задаче о кратчайшем пути
Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.4.7).
| Начало дуги | Конец дуги | Время в пути |
|---|---|---|
| 1 | 2 | 7 |
| 1 | 3 | 1 |
| 2 | 3 | 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) и указании пути, на котором этот минимум достигается.
Для исходных данных, представленных на рис.4.7 и в табл.4.6, в вершину 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$$Задача о кратчайшем пути для конкретных исходных данных (рис.4.77 и табл.4.7) полностью решена.
Оптимизационные задачи на графах, возникающие при подготовке управленческих решений в производственном менеджменте, весьма многообразны. Рассмотрим в качестве примера еще одну задачу, связанную с перевозками.
Задача о максимальном потоке. Как (т.е. по каким маршрутам) послать максимально возможное количество грузов из начального пункта в конечный пункт, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная способность этой дуги. Рассмотрим пример (рис.4.8).
(рис 4.8) Исходные данные к задаче о максимальном потоке
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.4.8, можно также задать таблицей (табл.4.8).
| Пункт отправления | Пункт назначения | Пропускная способность |
|---|---|---|
| 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 единица из пункта 3. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл.4.9).
| Пункт отправления | Пункт назначения | План перевозок | Пропускная способность |
|---|---|---|---|
| 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. Какой образец мотоцикла запустить в серию? Исходные данные для принятия решения приведены в табл.4.10. Разберите четыре критерия принятия решения: пессимистичный, оптимистичный, средней прибыли, минимальной упущенной выгоды.
| Цена бензина и ее шансы | Мотоцикл "Витязь" | Мотоцикл "Комар" |
|---|---|---|
| Низкая (20 % ) | 900 | 700 |
| Средняя (60%) | 700 | 600 |
| Высокая (20 % ) | 100 | 400 |
2. Изобразите на плоскости ограничения
3. Решите задачу
4. Решите задачу
$$Х и У$$ - целые числа.
5. Решите задачу о ранце:
$$Х_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.
6.
(рис 4.9) Транспортная сеть к задаче о кратчайшем пути
7. Решите задачу коммивояжера для четырех городов (маршрут должен быть замкнутым и не содержать повторных посещений). Затраты на проезд приведены в табл.4.11.
| Город отправления | Город назначения | Затраты на проезд |
|---|---|---|
| А | Б | 2 |
| А | В | 1 |
| А | Д | 5 |
| Б | А | 3 |
| Б | В | 2 |
| Б | Д | 1 |
| В | А | 4 |
| В | Б | 1 |
| В | Д | 2 |
| Д | А | 5 |
| Д | Б | 3 |
| Д | В | 3 |
8. Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (рис.4.10) ограничена (табл.4.12)?
(рис 4.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 |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.