Менеджмент 3-е издание - Глухов В.В.. Учебник для вузов. 3е изд. Спб. Питер, 2008. 608 с. ил. Серия Учебник для вузов
 Скачать 3.25 Mb.
|
|
Пример. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов, чтобы доход был мак симальным. Причем выпуск спинок дивана может принимать любое значение, подлокотники изготавливаются парами, т. е. они должны быть кратны двум, а ножки стульев — четырем (табл. 8.9). Таблица 8.9 Изделия Показатели спинка дивана подлокотники кресла ножка стула Наличие ресурса Цена, ден.ед./ед. 20 6 8 – Древесина 10 5 3 206 Трудозатраты 2 7 4 100 Спрос 10 8 12 – х 1 х 2 х 3 b i Решение. Математическая модель задачи запишется в виде: mах L = 20 х 1 + 6 х 2 + 8 х 3 ; 10 х 1 + 5 х 2 + 4 х 3 ≤ 206; 2 х 1 + 7 х 2 + 4 х 3 ≤ 100; 0 ≤ х 1 ≤ 10; 0 ≤ х 2 ≤ 8; 0 ≤ х 3 ≤ 12; х 2 = 2 δ 21 + 4 δ 22 + 6 δ 23 + 8 δ 24 ; х 3 = 4 δ 31 + 8 δ 32 + 12 δ 33 ; δ 21 + δ 22 + δ 23 + δ 24 = 1; δ 31 + δ 32 + δ 33 = 1, где δ 2k , δ 3k — варианты количеств подлокотников и ножек (k = 1… k i ). Глава 8. Методы решения управленческих задач 158 158 158 158 158 Введение булевых переменных дает возможность обеспечить выпуск изделий в кратном заданном количестве. Так, для подлокотников х 2 может принимать сле дующие значения: если в результате решения будет получено δ 21 = 1, а остальные δ 22 = δ 23 = δ 24 = 0, то х 2 = 2; если δ 22 = 1, а остальные δ 21 = δ 23 = δ 24 = 0, то х 2 = 4 и т. д. Для решения задачи с учетом дополнительных условий мы ввели еще семь пе ременных и четыре ограничения. Если бы требовалось определить выпуск спи нок, подлокотников и ножек для одного изделия (комплекта), то можно было бы записать х 2 = 2х 1 , х 3 = 4х 1 и не вводить дополнительные ограничения и булевы переменные. В результате решения задачи получены следующие значения: 0 0 0 1 2 3 0 0 0 0 0 0 0 22 33 21 23 24 31 32 max 320; 10; 4; 12; 1; 0. L x x x δ δ δ δ δ δ δ = = = = = = = = = = = При этом не полностью использованы ресурсы: резерв первого равен 50, второ го — 4 ед. В общем виде задачу распределения ресурсов с учетом требования дискретно сти значений переменных можно записать: 1 1 1 1 max(min) ; ( 1... ); ( 1... ); 1, j j n j j j n ij j i j k j kj kj k k kj k L c x a x b i m x d j n δ δ = = = = = ≤ = = = = ∑ ∑ ∑ ∑ где d 1j , d 2j , ..., d kj , ... — дискретные значения, которые может принимать переменная х j Эта система отличается от обычной задачи распределения ресурсов появлением булевых переменных и увеличением числа ограничений: 1 1 j max(min) ; ( 1... ); D ( 1... ). n j j j n ij j i j j j L c x a x b i m d x j n = = = ≤ = ≤ ≤ = ∑ ∑ 8.9. 8.9. 8.9. 8.9. 8.9. Параметрическое программирование Параметрическое программирование Параметрическое программирование Параметрическое программирование Параметрическое программирование Задача параметрического программирования имеет следующий вид: , " 1 ( ) n j j j j F c c t x = = + ∑ (1) 159 159 159 159 159 8.9. Параметрическое программирование при условиях 1 ( 1... ); n ij j i j a x b i m = = = ∑ (2) 0 ( 1... ), j x j n ≥ = (3) где c ′ j , c ′′ j , a ij , b i — заданные постоянные числа. Может быть поставлена и обобщенная параметрическая задача, в которой от параметра t линейно зависят коэффициенты при неизвестных в целевой функ ции (цены изделий от спроса на них), в системе уравнений (нормы расхода ресур сов от применяемых технологий), свободные члены системы уравнений (наличие ресурсов от предложений поставщиков): 1 max ( ' '' ) ; n j j j j F c c t x = = + ∑ (4) 1 ( ' '' ) ' '' ( 1... ); n ij ij j i i j a a t x b b t i m = + = + = ∑ (5) 0 ( 1... ); j x j n ≥ = (6) , t α β ≤ ≤ (7) где a, β — промежуток изменения значений параметра t (–∞, +∞). Решение задач (1)–(3), (4)–(7) можно найти методами линейного программи рования. Предположим, что в задаче (1)–(3) множество неотрицательных решений си стемы линейных уравнений (2) (многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t ∈[a, β] такой точки многогранника решений, в которой функция (1) принимает maх. Чтобы найти эту точку, будем считать t = t 0 и находим решение полученной задачи линейного программирования ЛП (1)–(3), т. е. определим вер шину многогранника решений, в которой функция (1) имеет maх, либо устанав ливаем, что при данном значении t 0 задача неразрешима. После нахождения точки, в которой при t = t 0 функция (1) принимает maх, ищут множество значений t, для которых координаты этой точки определяют оптимальный план задачи (1)–(3). Найденные параметры t исключают из рас смотрения и берут некоторое новое значение t из промежутка [a, β]. Для выбранного значения параметра t из промежутка [a, β] либо находят опти мальный план, либо устанавливают неразрешимость задачи. Пример. Пусть предприятие изготавливает два вида продукции А, В, для кото рых использует три вида ресурсов. Известны нормы расхода и запасы каждого вида (табл. 8.10). Из анализа спроса установлено, что цена единицы продукции для изделия А может изменяться от 2 до $12, а для изделия В — от 13 до $3, причем эти измене ния определяются соотношениями c 1 = 2 + t, c 2 = 13 – t, где 0 ≤ t ≤ 10. Требуется для Глава 8. Методы решения управленческих задач 160 160 160 160 160 каждого из возможных значений цены каждого вида изделий найти такой план их производства, при котором обеспечивается максимальная выручка. Решение. Математически задача формулируется в виде: 1 2 1 2 1 2 1 2 1 2 max[(2 ) (13 ) ]; 4 16; 2 2 22; 6 3 36; , 0; 0 10. t x t x x x x x x x x x t + + − ⎧ ⎪ + ≤ ⎪⎪ + ≤ ⎨ ⎪ + ≤ ⎪ ⎪ ≥ ≤ ≤ ⎩ Для решения задачи (8)–(10) строим многоугольник решений, определенный системой линейных неравенств (9) и условием неотрицательности переменных (рис. 8.5). После этого, полагая t = 0, строим целевую функцию 2х 1 + 13х 2 = 26 (число 26 — произвольно) и вектор c = (2; 13). Передвигая эту прямую в направлении век тора , c можно установить последнюю ее точку с многоугольником решений OABCD, т. е. точку А(0; 11). Таблица 8.10 Удельный расход ресурсов на изделие Ресурсы А В Наличие ресурсов 1 4 1 16 2 2 2 22 3 6 3 36 Цена изделия 2 + t 13 – t – (8) (9) (10) Рис. 8.5 161 161 161 161 161 8.9. Параметрическое программирование Следовательно, задача, полученная из задачи (8)–(10) при t = 0, имеет опти мальный план * 0 x = (0; 11). Это означает, что если цена изделия А равна 2 + 0 = $2, а цена изделия В 13 – 0 = $13, то в оптимальном плане производство изделий А не предусматривается, а изделий В требуется изготовить в количестве 11 ед. и мак симальная выручка составит maх F = $143. Положим теперь t = 2 и построим прямую целевой функции (2 + 2) х 1 + (13 – 2) х 2 = = 4 х 1 + 11 х 2 = 44 (число 44 — произвольно) и вектор 1 c (4; 11). Передвигая эту прямую в направлении вектора 1 , c устанавливаем последнюю точку многоуголь ника решений — ту же точку А(0; 11). Следовательно, при t = 2 задача, полученная из задачи (8)–(10), имеет тот же оптимальный план * 0 x = (0; 11), означающий, что при цене изделия А $4, а изделия В — $11 требуется изготовить только 11 ед. изделия В, которые обеспечат макси мум выручки maх F = 11 × 11 = $121. Данный план производства будет оставаться оптимальным для всякого значе ния t, пока прямая целевой функции (2 + t)х 1 + (13 – t)х 2 = L не станет параллель ной прямой 2х 1 + 2х 2 = 22. Это произойдет, когда 2 13 , 2 2 t t + − = т. е. при t = 5,5 координаты любой точки отрезка АВ дают оптимальный план задачи (8)–(10). Таким образом, для всякого 0 ≤ t ≤ 5,5 задача (8)–(10) имеет оптимальный план * 0 x = (0; 11), при котором значение целевой функции maх F = (2 + t)х 1 + (13 – t)х 2 = (2 + t) × 0 + (13 – t) × 11 = 143 – 11t. При значениях параметра t, больших 5,5, например t = 6, прямая целевой функ ции: 8х 1 + 7х 2 = 56 (56 — произвольно), которой соответствует вектор 2 c (8; 7); в направлении движения по этому вектору последняя точка В(1; 10), т. е. при цене А 2 + 6 = $8, при цене В 13 – 6 = $7 0 0 1 2 1; 10; x x = = maх F = $78. План * 1 x = (1; 10) будет оптимальным для задачи (8)–(10) для всякого t > 5,5, пока прямая целевой функции ЦФ не станет параллельной прямой 6х 1 + 3х 2 = 36. Это произойдет, когда 2 13 , 6 3 t t + − = т. е. при t = 8, при котором координаты любой точки отрезка ВС дают оптималь ный план задачи (8)–(10). Таким образом, для всякого 5,5 ≤ t ≤ 8 задача (8)–(10) имеет оптимальный план * 1 x = (1; 10), при котором значение целевой функции maх F = (2 + t) × 1 + (13 – t) × 10 = 132 – 9t. Аналогично рассуждая, получим, что для всякого 8 ≤ t ≤ 10 оптимальным пла ном задачи (8)–(10) будет * 2 x = (2; 8), т. е. если цена изделия А заключена между (или равна) 10 и $12, а изделия В — между 3 и $5, то 0 0 1 2 2 ед., 8 ед., x x = = которые обеспечат максимальную выручку maх F = 108 – 6t. Глава 8. Методы решения управленческих задач 162 162 162 162 162 Окончательно: * 0 * 1 * 2 (0;11); [0;5,5] max 143 11 . (1;10); [5,5; 8] max 132 9 . (2; 8); [8;10] max 108 6 . x F t x t F t x F t ⎧ ⎧ = ⎪ = ⎪ ⎨ = − ⎪ ⎪ ⎩ ⎪ ⎧ = ⎪ ⎪ = = ⎨ ⎨ = − ⎪⎩ ⎪ ⎪ ⎧ = ⎪ ⎪ = ⎨ ⎪ = − ⎪⎩ ⎩ 8.10. 8.10. 8.10. 8.10. 8.10. Дробно линейное программирование Дробно линейное программирование Дробно линейное программирование Дробно линейное программирование Дробно линейное программирование Общая задача дробно линейного программирования формулируется в виде: 1 1 2 1 1 max ; ( 1... ); 0 ( 1... ), n j j j n j j j n ij j i j j c x L L L d x a x b i m x j n = = = ⎧ ⎪ ⎪ = = ⎪ ⎪ ⎪ ⎨ ⎪ ≤ = ⎪ ⎪ ⎪ ⎪ ≥ = ⎩ ∑ ∑ ∑ где c j , d j , b i , a ij — некоторые постоянные числа; 1 0. n j j j d x = > ∑ Для n = 2: 1 1 2 2 1 1 2 2 1 1 2 2 1 2 max ; ( 1... ); , 0, i i i c x c x L d x d x a x a x b j n x x + ⎧ = ⎪ + ⎪ ⎨ + ≤ = ⎪ ⎪ ≥ ⎩ где d 1 х 1 + d 2 х 2 > 0. Задача решается в следующей последовательности: 1. В ограничивающих уравнениях заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые. 2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи. 3. Находят область (многоугольник) допустимых решений задачи. 4. Строят прямую 1 1 2 2 1 1 2 2 , c x c x L d x d x + = + уравнение которой получается, если поло жить значение целевой функции равным некоторому постоянному числу. (1) (2) (3) 163 163 163 163 163 8.10. Дробно линейное программирование 5. Определяют точку максимума или устанавливают неразрешимость задачи. 6. Находят значение целевой функции в точке максимума. Пример. Пусть для производства двух видов изделий А и В используются три типа технологического оборудования. Известны затраты времени и других ресур сов на производство единицы изделия каждого вида (табл. 8.11). Таблица 8.11 Нормы времени Ограничения по фонду времени оборудования Тип оборудования А В верхний нижний I 2 8 26 – II 1 1 – 4 III 12 3 39 – Затраты на производство 2 3 – – Требуется определить, сколько изделий каждого вида необходимо изготовить, чтобы себестоимость одного изделия была минимальной. Решение. 1 2 1 2 1 2 1 2 1 2 1 2 2 3 min ; 2 8 26; 4; 12 3 39; , 0. x x L x x x x x x x x x x + ⎧ = ⎪ + ⎪ ⎪ + ≤ ⎪ ⎨ + ≥ ⎪ ⎪ + ≤ ⎪ ≥ ⎪⎩ Решение задачи определяется из области допустимых вариантов (рис. 8.6). Область допустимых вариантов решения представляется треугольником BCD. Значит, целевая функция принимает значение в одной из точек: B, C или D. Чтобы определить, в какой именно из этих точек, положим значение функции L равным некоторому числу, например 11/4: Рис. 8.6 (4) (5) (6) (7) Глава 8. Методы решения управленческих задач 164 164 164 164 164 1 2 1 2 2 3 11 или 4 x x x x + = + –3 х 1 + х 2 = 0. (8) Это уравнение определяет прямую, проходящую через начало координат. Ко ординаты точек этой прямой, принадлежащие и многоугольнику решений, явля ются планами задачи, при которых значение целевой функции равно 11/4. В дан ном случае к указанным точкам относится только одна точка B(1; 3). Теперь положим, что 1 2 1 2 2 3 5 или 2 x x x x + = + –х 1 + х 2 = 0. (9) Это уравнение определяет прямую, проходящую через начало координат. Ее можно рассматривать как прямую, полученную в результате вращения прямой (8) по часовой стрелке вокруг начала координат. Следовательно, если положить значение целевой функции равным некоторому числу L 0 1 2 0 1 2 2 3 , x x L x x + = + (10) а прямую (10), проходящую через начало координат, вращать в направлении ча совой стрелки вокруг начала координат, то получим прямые 1 2 1 2 2 3 , x x L x x + = + где L < L 0 Последней общей точкой вращаемой прямой с областью допустимых вариан тов решения будет точка D(3; 1), в которой достигается минимум целевой функ ции. Таким образом, оптимальный план заключается в производстве трех изде лий А и одного изделия В, обеспечивающем минимальную себестоимость одного изделия, равного 2 3 3 1 9 min 3 1 4 L × + × = = + Задача дробно линейного программирования при n > 2 может быть решена сведе нием ее к задаче линейного программирования. Для этого следует обозначить через 1 0 1 n j j j y d x − = ⎛ ⎞ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ∑ и ввести новые переменные y j = y 0 х j , ( j = 1… n). Тогда исходная задача (1)–(3) сведется к следующей: * 1 0 1 1 0 max ; y =0 ( 1... ); 1; 0 ( 1... ), y 0. n j j j n ij j i j n j j j j L c y a y b i m d y y j n = = = ⎧ = ⎪ ⎪ ⎪ ⎪ − = ⎪ ⎨ ⎪ ⎪ = ⎪ ⎪ ≥ = ≥ ⎪⎩ ∑ ∑ ∑ (11) (12) (13) (14) |