Книги по разным темам Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 14 |

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

3.4. Типовые управленческие задачи, решаемые методом математического программирования Метод математического программирования нашел достаточно широкое применение, в том числе в экономике и менеджменте. Ниже приводится примеры постановки и решения некоторых практических задач.

Задача распределения ресурсов В стандартном варианте задача распределения ресурсов [15] совпадает с постановкой задачи линейного программирования (3.1Ц3.2). Пусть имеется m видов ресурсов, причем каждый i-й ресурс имеется в количестве bi (1 i m). Имеющиеся ресурсы используются для выпуска n видов продукции, причем для выпуска единицы j-го вида продукции необходимо aij единиц i-го вида ресурса. Кроме этого, известен вклад единицы продукции ci в целевую функцию. Требуется определить сколько какого вида продукции следует произвести, чтобы обеспечить максимум критерия оптимальности (3.1). Так, например, если m = 9, n = 4, количество имеющихся ресурсов описывается набором значений b = {30,52; 51,11; 31,23; 26,28; 39,40; 57,47; 53,61; 44,30; 84,54}; матрица коэффициентов aij имеет вид табл. 3.2. в которой столбцы имеют смысл вида соответствующей продукции, а строки - вида ресурса. Коэффициенты значимости каждого вида продукции ci имеют значения {9,20; 7,15;

X = 6,01; 7,61}; решением задачи является набор переменных {1,13; 0,00;

0,00; 3,10}, обеспечивающий оптимальное значение целевой функции округленно равное 33,97 при общем суммарном расходе ресурсов равном 185,59. Здесь и далее в этом подразделе для непосредственных вычислений использованы средства надстройки Поиск решения табличного процессора Excel, методы работы с которой подробно описаны ниже.

Таблица 3.Расход ресурса на производство единицы продукции 1 1,10 6,09 2,6,2 7,08 7,02 5,8,3 1,45 7,49 9,6,4 9,81 9,60 4,9,5 1,44 3,38 8,3,6 7,42 1,92 2,3,7 9,83 2,22 5,8,8 6,78 5,43 1,5,9 6,35 5,14 1,3,Существует и другая постановка задачи - при заданном результате С минимизировать используемые ресурсы, выраженные в одинаковых единицах измерения m n x min, E = aij j i=1 j= n g = x C.

i c j j j= Результатом решения этой задачи при тех же исходных данных в допущении C=33,0 является набор переменных {1,01; 0,00; 0,00; 3,11}, X = обеспечивающий расход ресурсов равный 180,14. Если задать C = 33,97, результат решения второй задачи совпадает с первым.

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

Строки ограничений рассматриваются как наличие соответствующего ресурса, коэффициенты aij имеют смысл его расхода на выпуск единицы продукции, а сами переменные xj - количество продукции j-го вида.

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

Задача о назначениях Задача о назначениях обычно рассматривается как задача выбора наилучшей комбинации распределения ресурсов. Пусть имеется n работ и n кандидатов для выполнения этих работ [15]. Назначению i-го кандидата на j-ю работу соответствует определенная прибыль cij. Каждого кандидата можно назначить только на одну должность и только один раз, а каждая работа может быть выполнена только один раз. Из сказанного следуют два ограничения nn = 1, = 1.

(3.9) xij xij i=1 j=Переменные xij принимают значение 1 в том случае, когда кандидат i назначается на работу j и равны нулю во всех остальных случаях, что переводит задачу в категорию дискретных задач математического программирования. Целевая функция задачи в этом случае может быть записана как n n E = xij max, (3.10) cij j=1 i=а выражения (3.9) формулируются в виде ограничений. Так, например, если n = 4, матрица весовых коэффициентов cij. имеет вид табл. 3.3, в которой столбцы соответствуют кандидатам на должности, а строки - самим должностям. Результат решения X представлен в табл. 3.4, а показатель эффективности имеет значение 2,93. Очевидно, что все кандидаты получили предложение занять должность.

Таблица 3.Таблица 3.Значения прибыли Оптимальный вариант от назначения кандидата назначения кандидатов на соответствующую работу на должности (решение) 1 2 3 4 1 2 3 1 0,00 0,72 0,73 0,78 1 0 0 0 2 0,55 0,58 0,86 0,96 2 1 0 0 3 0,02 0,90 0,68 0,68 3 0 0 1 4 0,00 0,92 0,48 0,05 4 0 1 0 Задача о назначениях в общем случае может рассматриваться в открытом виде, когда суммы (3.9) имеют различное число слагаемых, т.е. m > n. Такая постановка может иметь место тогда, когда количество кандидатов на занимаемые должности больше числа вакансий.

Выражения ограничений (3.9) в этом случае преобразуются к виду mn 1, = 1, xij = 0,1.

{ } xij xij i=1 j=Решение открытой задачи о назначениях позволяет формализовать процедуру отбора кандидатов на имеющиеся вакантные места. В этом случае матрица весовых коэффициентов cij имеет вид табл. 3.5, резульX тат решения представлен в табл. 3.6 из которой следует, что кандидат 1 должности не получает, а показатель эффективности имеет значение 2,93.

Таблица 3.5 Таблица 3.Значения прибыли Оптимальный вариант от назначения кандидата назначения кандидатов на соответствующую работу на должности (решение) в открытой задаче в открытой задаче : 1 2 3 4 1 2 3 4 1 0 0 1 0 1 0,00 0,72 0,73 0,78 0,2 0 0 0 1 2 0,55 0,58 0,86 0,96 0,3 0 1 0 0 3 0,02 0,90 0,68 0,68 0,4 0 0 0 0 4 0,00 0,92 0,48 0,05 0,Примерами практических задач о назначениях могут быть задачи размещения туристов в гостинице, распределения отпусков сотрудников, составления графика дежурств.

Транспортная задача Транспортной задачей обычно называют задачу о выборе плана перевозок из m пунктов отправления в n пунктов назначения [15]. В качестве условия задачи задается набор коэффициентов cij, определяющий стоимость доставки продукции из пункта i в пункт j. Ресурсы продукта в пунктах отправления обозначим ai, а потребность продуктов в пунктах назначения bj. Обычно предполагается, что должна быть выполнена вся программа перевозок, которая задается в виде ограничений m n =.

ai bj i=1 j=Целевая функция задачи имеет вид m n E = xij min, cij i=1 j=где xij - расчетная программа перевозки из пункта i в пункт j. Так, например, если m = 4, n = 5, количество имеющихся ресурсов в пунктах отправления описывается набором значений a ={3,43; 6,56; 1,31; 6,43};

потребность в ресурсах в пунктах назначения описывается набором значений b ={1,72; 4,92; 3,38; 1,89; 5,83}; матрица коэффициентов cij имеет вид табл. 3.7, в которой столбцы соответствуют номерам пунктов отправления, а строки - номерам пунктов назначения. Тогда решением задачи X является набор переменных табл. 3.8, обеспечивающий значение целевой функции округленно равное 71,08, смысл которого сводится к оптимальному объему перевозки из соответствующего пункта отправления в соответствующий пункт назначения.

Таблица 3.Таблица 3.Оптимальный план перевозок Стоимость перевозки (решение) 1 2 3 4 1 2 3 1 2,31 5,85 7,87 6,75 1 0,00 0,41 1,31 0,2 1,78 7,14 8,39 1,65 2 3,43 1,49 0,00 0,3 8,87 7,14 4,57 4,52 3 0,00 0,00 0,00 3,4 6,24 6,63 2,91 4,30 4 0,00 0,00 0,00 1,5 6,70 3,12 7,96 1,21 5 0,00 4,66 0,00 1,Задача составления смесей При формулировке задачи [15] составляется набор исходных материалов, характеризующий содержание контролируемых компонент, где aij - содержание i-го компонента в j-м виде исходного материала. Необходимо определить набор xj при условиях nn b1, x bi,1 i m, x j aij j (3.11) j=1 j=где b1 - общее ограничение массы смеси, bi - минимально необходимое содержание i-го компонента в конечном продукте, обеспечивая n E = x min, c j j j=где cj - расходы на единицу j-го материала. В качестве варианта может рассматриваться задача приготовления заданного объема смеси (в этом случае первое неравенство в (3.11) записывается как строгое равенство). Так, например, если m = 3, n = 6, ограничения описываются набором значений b ={3,78; 2,64; 1,28}; расходы на единицу материала составляют соответственно cj ={7,35; 3,73; 1,87; 6,92; 5,53; 5,83}; матрица коэффициентов aij имеет вид табл. 3.9, в которой столбцы соответствуют номерам исходных материалов, а строки - номерам ограничений.

X = Тогда решением задачи является набор переменных {0,00; 0,00; 2,61;

0,00; 1,17; 0,00}, обеспечивающий значение целевой функции округленно равное 11,36, смысл которого сводится к величине расходов на составление смеси.

Таблица 3.Содержание компонентов в исходных материалах 1 1,00 1,00 1,00 1,00 1,00 1,2 0,38 0,32 0,73 0,76 0,63 0,3 0,89 0,07 0,08 0,76 0,91 0,Примерами практических задач составления смесей могут служить задачи расчета специальных диет, наборов, меню и т.п.

Задача о ранце Как следует из названия, исходно задача рассматривалась как метод выбора набора из имеющегося множества предметов, который может разместиться в некотором заранее заданном объеме (ранце). Пусть имеется некий объем V, который необходимо заполнить различными предметами n типов объемом vj и ценностью cj так, чтобы их суммарная ценность оказалась наибольшей [15]. Тогда в качестве ограничения можно рассматривать выражение n x V, v j j j=а целевая функция n E = x max.

c j j j=Так, например, если n = 6, объемы предметов определяются значениями vj ={23,49; 43,15; 7,47; 13,46; 41,96; 37,14; 47,86}, ценность предметов значениями cj ={3,45; 2,16; 0,34; 3,30; 5,62; 9,08}, а V = 50, решение задачи будет иметь вид X = {0,00; 0,00; 1,00; 3,00; 0,00; 0,00} при достигнутом значении ограничения 47,86 и целевой функции 10,25.

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

Задача банковского взаимозачета Задача банковского взаимозачета возникает в том случае, когда из имеющегося набора n платежных поручений стоимостью cj, (1 j n) следует отобрать тот набор платежных поручений, который максимально приблизил бы их к сумме взаимозачета V при наличии ограничения n x V.

с j j j=Переменные в этом случае принимают только дискретные значения xj{0,1}, а целевая функция имеет вид n x max.

с j j j=Задача представляет особый интерес, когда n достаточно велико.

Так, например, при n = 25 и значениях cj ={12,07; 15,98; 10,19; 80,79;

46,19; 57,84; 31,08; 41,45; 6,13; 16,46; 47,13; 95,83; 0,46; 65,96; 86,51; 58,11;

40,55; 60,41; 72,52; 51,59; 26,88; 37,24; 26,11; 63,63; 96,62} результат решеX = ния {0; 0; 0; 1; 1; 1; 0; 1; 0; 0; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 0; 0; 0; 1; 1} обеспечивает значение суммы взаимозачета 965,59 при заданной величине V = 1000.

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

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

Задача имеет много аналогий с транспортной задачей и отличается от нее в первую очередь тем, что искомые переменные принимают только два возможных значения - 1, если перевозка производится и 0, если нет.

Отметим, что каждый пункт маршрута, кроме исходного, должен быть xij 0,посещен только один раз. Введем n2 переменных { }, удовлетворяющих ограничениям nn = 1, 1 j n, = 1, 1 i n.

xij xij i=1 j=Целевая функция задачи имеет вид n n E = xij min.

cij j=1 i=Рассмотрим теперь некоторые дополнительные ограничения. Очевидно, что перевозка внутри одного пункта не требуется. Формально это означает, что x 0, 1 j n.

jj В табл. 3.10 представлена стоимость перевозки между различными пунктами cij, а в табл. 3.11 - рассчитанный оптимальный маршрут перевозок, обеспечивающий значение целевой функции 12,38.

X Рассчитанный оптимальный маршрут поездок начинается в пункте 1. Затем следует поездка в пункт 2, возвращение в пункт 1, поездка в пункт 6, поездка в пункт 5, поездка в пункт 3. Маршрут завершается в пункте 4. Обычно в задаче коммивояжера рассматривается дополнительное условие: маршрут должен начинаться и заканчиваться в пункте 1. Формально это условие может быть записано как 0,1 i < n, xi1 = 1, j = n.

В табл. 3.12 представлен оптимальный маршрут перевозок X, начинающихся и заканчивающихся в пункте 1 при тех же исходных данных табл. 3.10. Значение целевой функции в этом случае увеличилось и составляет 15,25.

Таблица 3.Стоимость перевозки между пунктами 1 0,00 7,15 7,59 5,55 9,96 8,2 3,22 0,00 7,74 9,58 6,01 1,3 5,06 9,32 0,00 0,41 9,91 0,4 8,55 5,86 1,77 0,00 0,04 9,5 7,77 0,64 0,99 7,01 0,00 8,6 5,34 4,55 7,22 0,89 2,13 0,Таблица 3.Оптимальный маршрут перевозок Таблица 3.Оптимальный маршрут перевозок, начинающихся и заканчивающихся в пункте Список типовых задач разработки управленческого решения, для которых может использоваться метод линейного и математического программирования, является далеко не исчерпывающим и может пополняться в процессе реальной работы. Тем не менее, представляется весьма важным для практикующего менеджера наличие в его арсенале соответствующего инструментария и навыков решения.

3.5. Динамические задачи разработки управленческого решения Задача разработки управленческого решения переходит в категорию динамических в том случае, когда входящие в ее состав аргументы оказываются функциями времени. Следует отметить, что время как таковое само по себе является разновидностью ресурса, специфической особенностью которого является то обстоятельство, что расходом этого ресурса невозможно управлять. Учет времени как ресурса оказывается принципиальным для целого класса задач, в основе которых лежит требование минимизации времени, затрачиваемого на выполнение работы. К числу таких задач следует отнести в первую очередь задачи управления проектами [16, 17], а также задачи, описываемые методами теории массового обслуживания [18].

Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 14 |    Книги по разным темам