Менеджмент 3-е издание - Глухов В.В.. Учебник для вузов. 3е изд. Спб. Питер, 2008. 608 с. ил. Серия Учебник для вузов
 Скачать 3.25 Mb.
|
|
Пример. Определить решение следующей оптимизационной задачи: 1 2 1 2 1 2 3 1 2 4 1 2 5 1 5 2 max ; 2 11; 8; 3 9; ..., 0. x x L x x x x x x x x x x x x x + ⎧ = ⎪ + ⎪ ⎪ + − = ⎪ ⎨ − + = ⎪ ⎪− + + = ⎪ ≥ ⎪⎩ Здесь х 3 , х 4 , х 5 — фиктивные переменные, преобразующие неравенства в равен ства. Решение. Обозначим y 0 = (х 1 + х 2 ) –1 и вводим новые переменные у 0 = (х 1 + х 2 ) –1 Получим задачу линейного программирования: * 1 2 1 2 3 0 1 2 4 0 1 2 5 0 1 2 1 5 0 max 2 ; 2 11 0; 8 0; 3 9 0; 1; ..., 0, 0. L y y y y y y y y y y y y y y y y y y y ⎧ = + ⎪ + − − = ⎪ ⎪ − + − = ⎪ ⎨ − + + − = ⎪ ⎪ + = ⎪ ⎪ ≥ ≥ ⎩ Ее оптимальный план: 0 0 1 2 0 0 3 4 0 0 5 0 0,9; 0,1; 0; 1,5; 0,1. y y y y y y = = = = = = Так как y j = y 0 х j , то оптимальный план исходной задачи: 0 0 0 0 , j j y x y = т. е. х 0 = (9; 1; 0; 0; 15), 2 9 1 max 1,9. 9 1 L × + = = + 8.11. 8.11. 8.11. 8.11. 8.11. Блочное программирование Блочное программирование Блочное программирование Блочное программирование Блочное программирование В решении экономических задач часто появляются математические модели, в ко торых отдельные ограничивающие условия содержат все переменные (ограниче ния, образующие блок связку), а другие — только часть переменных (ограни чения, образующие блоки). Математическая формулировка может содержать значительное число блоков (рис. 8.7). Глава 8. Методы решения управленческих задач 166 166 166 166 166 1 2 1 1 1 1 0 1 0 1 1 1 2 1 1 max ; ( 1... ); ( 1, ); ( 1, ); ( 1, ); p n j j n n j j j n ij j i j n ij j i j n ij j i j n ij j i p p j n L c x c x c x c x a x b i m a x b i m m a x b i m m a x b i m m = = = = + − = = + + + + = ≤ = ≤ = + ≤ = + ≤ = + ∑ ∑ ∑ ∑ 1 1 ( 1... ). n j j j d x D j n − + ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ≤ ≤ = ⎩ ∑ Такой задаче соответствует особая структура исходных данных (табл. 8.12). Таблица 8.12 Рис. 8.7 Переменные Ограничение n 1 n 2 n 3 ... n p Свободный член m 0 A 01 A 02 A 03 ... A 0p b 0 m 1 A 1 b 1 m 2 A 2 b 2 m 3 A 3 b 3 m p ... A p b p 167 167 167 167 167 8.12. Теория графов Применительно к матрице блочной структуры математическую постановку за дачи можно переписать иначе, вводя двухиндексное обозначение переменной х pj , указывающей на принадлежность переменной х j к p му локальному блоку: = = = = = = ≤ = ≤ = = ≤ ≤ = = ∑ ∑ ∑ ∑ ∑ 1 1 0 1 1 1 max(min) ; ( 1... ); ( 1... , 1... ); ( 1... ; 1... ), p p P n pj pj p j n P ij pj i p j n ij pj i p j pj pj pj p L c x a x b i m a x b i m p P d x D j n p P где P — общее число локальных блоков; n p — число переменных, входящих в p й локальный блок; m p — число ограничений в p м локальном блоке. Постановка задач данного класса относится к производственным комплексам, холдингам, финансово промышленным группам, корпорациям и т. п. В свою оче редь, они имеют в своем составе нескольких других предприятий, отличающихся индивидуальными локальными характеристиками (ресурсы, показатели), но в то же время объединенных совокупностью ограничений (общих для всей системы) и единой целевой функцией. Особенность таких задач — большая размерность. Современные программные средства в большинстве используют специальные методы решения с разложением (декомпозицией) задачи на Р подзадач, напри мер метод декомпозиции Данцига—Вульфа. По этому методу каждый блок матри цы формируется и отлаживается автономно как отдельная подзадача с последу ющим объединением блоков общими ограничениями на этапе окончательного составления задачи. Такие задачи экономически интерпретируются как задачи многоуровневой иерархической структуры. 8.12. 8.12. 8.12. 8.12. 8.12. Теория графов Теория графов Теория графов Теория графов Теория графов Наглядность геометрии широко используют при анализе больших технических и организационных систем. Граф — универсальное средство наглядного представления достаточно разно образных задач в виде совокупности вершин и ребер. Варианты сочетаний раз личных ребер и вершин представляют многообразие возможных графов и спосо бов их применения. Сетями представляют различные задачи, в которых исследуют перемещение или выполнение работ во времени. Характеристиками сети являются ее структу ра и параметры дуг. Структура (топология) сети демонстрирует взаимосвязь различных вершин и направление связывающих их дуг. Каждую вершину сети нумеруют порядковым номером. Начальную вершину в описании движения потоков называют источником, конечную — стоком. Глава 8. Методы решения управленческих задач 168 168 168 168 168 Дугу сети обозначают двойной индексацией 1–2; 3–4 (рис. 8.8) и т. д. (по номе рам вершин, на которые дуга опирается). В общем случае дугу обозначают «i–j», где i — номер вершины, из которой исходит дуга; j — номер вершины, в которую входит дуга. Каждая дуга имеет свои характеристики (рис. 8.9); t ij — продолжи тельность движения по дуге i–j; c ij — стоимость перемещения; d ij — пропускная способность дуги и т. д. Зная топологию сети и ее параметры, можно решать разнообразные задачи опти мизации. Рис. 8.8. Двойная индексация дуги сети Рис. 8.9. Характеристики дуги сети 169 169 169 169 169 8.12. Теория графов Сетевой график (сеть) состоит из дуг и узлов (вершин). Дуге соответствует выполняемая работа (обозначается стрелкой); вершине — событие, т. е. состоя ние перед работой (обозначается кружком). Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает последовательность работ и продолжительность вы полнения каждой работы (табл. 8.13). Таблица 8.13 Исходные данные для составления сетевого графика Работа Содержание Следует после работ Продолжи- тельность Обозначение a 1 Закупка и доставка оборудования – 1 1–2 a 2 Разработка технологии – 2 1–3 a 3 Монтаж и наладка оборудования a 1 4 2–3 a 4 Обучение рабочих-операторов a 1 3 2–4 a 5 Пуск линии в эксплуатацию a 2 , a 4 6 3–4 Два события отметим особо: начальное — состояние, с которого начинается весь комплекс работ; конечное — состояние, которым завершается комплекс работ. По исходным данным строится сетевой график (рис. 8.10). Последовательность работ, в которой конец предыдущей работы совпадает по времени с началом последующей, называется путем. Путь, имеющий наиболь шую продолжительность, называют критическим. Увеличение продолжительно сти работ критического пути приводит к более позднему наступлению конечного события. Работы, не лежащие на критическом пути, могут быть начаты или оконче ны позже или иметь бoльшую продолжительность без изменения срока окончания всех работ. Величину, на которую можно увеличить продолжительность выполнения та кой работы без увеличения времени наступления конечного события, называют резервом. Если руководитель следит за выполнением всех работ в срок, то он должен чет ко знать и особо контролировать работы критического пути. Перейдем к формализации. В нашем примере время наступления каждого со бытия может быть найдено по зависимостям Т 1 = 0; Т 2 = Т 1 + t 12 = 0 + 1 = 1. Рис. 8.10. Сетевой график Глава 8. Методы решения управленческих задач 170 170 170 170 170 Так как третье событие может наступить после выполнения работ 2–3 и 1–3, запишем: 3 1 13 3 3 2 23 3 0 2 2, т. е. 2 , 1 4 5, т. е. 5 T T t T T T t T ≥ + = + = ≥ ⎫ ⎬ ≥ + = + = ≥ ⎭ значит, Т 3 = 5. Аналогично найдем время наступления последнего события: 4 2 24 4 4 3 34 4 1 3 4, т. е. 4 , 5 6 11, т. е. 11 T T t T T T t T ≥ + = + = ≥ ⎫ ⎬ ≥ + = + = ≥ ⎭ значит, Т 4 = 11. Окончательно время наступления событий будет равно: Т 1 = 0; Т 2 = 1; Т 3 = 5; Т 4 = 11. Резерв работы 1–3 будем обозначать Δ 13 = 5 – 2 = 3. Значит, работа 1–3 может быть начата не в начальный момент времени, а спустя 3 ед. времени или продол жаться на 3 ед. больше, чем первоначально предполагалось, т. е. может длиться 2 + 3 = 5 ед. без увеличения момента наступления конечного события 4 (рис. 8.11). Рис. 8.11. Временной резерв работы 1–3 Аналогично Δ 24 = Т 4 – (Т 2 + t 24 ) = 11 – (1 + 3) = 7, т. е. продолжительность рабо ты 2 – 4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, т. е. Δ 12 = Δ 23 = Δ 34 = 0. Для третьего события можно записать Т 3 = Т 1 + t 13 + Δ 13 Отсюда (Т 3 – Т 1 ) – Δ 13 = t 13 . Выражение (Т 3 – Т 1 ) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательны ми событиями. И этот интервал за вычетом резерва Δ 13 равен продолжительности работы 1–3. В этой зависимости нам задана продолжительность работы t 13 = 2 (пра вая часть уравнения), остальные величины — искомые переменные. Если их обо значить Т 3 = x 3 ; Δ 13 = x 13 ; Т 1 = x 1 ; t 13 = b 13 , то можно записать (x 3 – x 1 ) – x 13 = b 13 и получить линейное уравнение с тремя неизвестными. Если записать аналогичные зависимости для всех событий и работ, входящих в нашу сеть, то получим систему: 171 171 171 171 171 8.12. Теория графов 2 1 12 12 3 1 13 13 3 2 23 23 4 2 24 24 4 3 34 34 ( ) ; ( ) ; ( ) ; ( ) ; ( ) T T t T T t T T t T T t T T t − − Δ = ⎧ ⎪ − − Δ = ⎪⎪ − − Δ = ⎨ ⎪ − − Δ = ⎪ ⎪ − − Δ = ⎩ Эта система описывает топологию (структуру) нашей сети. Если вместо t ij подставить их известные (заданные) значения, получим: 2 1 12 3 1 13 3 2 23 4 2 24 4 3 34 ( ) 1; ( ) 2; ( ) 4; ( ) 3; ( ) 6. T T T T T T T T T T − − Δ = ⎧ ⎪ − − Δ = ⎪⎪ − − Δ = ⎨ ⎪ − − Δ = ⎪ ⎪ − − Δ = ⎩ Описание структуры сети содержит пять линейных уравнений с девятью неиз вестными. Они имеют бесчисленное множество решений. Чтобы решить эту си стему уравнений, надо добавить граничные условия и целевую функцию. При этом возможны две постановки задач оптимизации. Первая постановка: задаемся временем начала работ, т. е. значением Т 1 , напри мер Т 1 = 0, и стремимся закончить комплекс работ как можно раньше: 1 4 1 min; 0. L T T = → ⎧ ⎨ = ⎩ Вторая постановка: задан срок завершения всех работ, например Т 4 = 15, и мы заинтересованы в как можно более позднем начале работы, но с соблюдением на меченного срока: 2 1 4 max; 15. L T T = → ⎧ ⎨ = ⎩ В общем виде топология сети запишется: (Т j – T i ) – Δ ij = t ij (для всех i, j). (*) Если обозначить S — число событий, R — число работ, то, как видно из (*), си стема, описывающая сеть, будет включать n переменных, где n = S + R, так как каждому i му событию соответствует неизвестная T i , а каждой i, j й работе — не известная Δ ij . А число ограничений m = R, т. е. каждой работе соответствует огра ничение. Поэтому в начальных сетях одна строка ( * ) превращается в систему линейных уравнений, содержащую сотни, а может быть и тысячи неизвестных и ограничений. Тогда общие постановки запишутся: 1 1 1 пл min; ; n L T T T = → ⎧ ⎨ ≥ ⎩ 2 1 пл max; , n n L T T T = → ⎧ ⎨ ≥ ⎩ где T 1 пл , T n пл — заданные плановые сроки начала и окончания работ сети. Глава 8. Методы решения управленческих задач 172 172 172 172 172 Например, для графика из 11 событий и 20 работ (рис. 8.12) первая постановка при Т 1 = 0 будет иметь вид: 1 11 1 min; ( ) ( 1... 10; 2... 11); 0. j i ij ij L T T T t i j T ⎧ = → ⎪ − − Δ = = = ⎨ ⎪ = ⎩ Рис. 8.12. График 11 событий и 20 работ 8.13. 8.13. 8.13. 8.13. 8.13. Динамическое программирование Динамическое программирование Динамическое программирование Динамическое программирование Динамическое программирование Пусть имеется ресурс К, который требуется вложить в m объектов в течение n этапов. В результате вложения в i й объект (I = 1... m) на j м этапе (j = 1… n) ресур са в размере x ij образуется доход, определяемый функцией дохода g ij (x ij ). Часть ресурса x ij при этом остается неизрасходованной. Эта часть определяется функ цией остатка j ij (x ij ). Известна величина ресурса К j , распределяемая на каждом j м этапе. Требуется определить значения x ij вложения ресурсов на каждом этапе в каж дый объект, чтобы на всех объектах и на всех этапах доход был максимальным. Схема поэтапного распределения ресурсов приведена на рис. 8.13. Данная задача математически формулируется в виде: 1 1 max ( ); m n ij ij i j F g x = = = ∑∑ 1 ( 1... ); m ij j i x K j n = = = ∑ 1 1 ( ) ( 1... ); m ij ij j i x K j n ϕ + = = = ∑ 0 ( 1... ; 1... ). ij x i m j n ≥ = = 173 173 173 173 173 8.13. Динамическое программирование Принцип оптимальности Беллмана: на каждом этапе необходимо так распре делять ресурс, чтобы от начала данного этапа и до конца процесса распределения доход был максимальным. Динамическое программирование дает возможность принять ряд последова тельных решений (многошаговый процесс), обеспечивающих оптимальность развития процесса в целом. Предположим, что есть некоторые ресурсы x, которые распределяются на два предприятия: на первое — y, на второе — x – y. Пусть в течение определенного периода (например, года) количество y приносит доход (прибыль) g(y), а количе ство x – y — доход h(x – y). Общий доход от вложенных ресурсов составит R 1 (x, y) = g(y) + h(x – y). Обозначим через F 1 (x) наибольший доход, который могут принести ресурсы x при оптимальном распределении их между предприятиями. Тогда 1 0 ( ) max[ ( ) ( )]. y x F x g y h x y ≤ ≤ = + − (1) Теперь рассмотрим двухшаговый процесс, состоящий из двух периодов (эта пов). Так как доход получается вследствие выпуска и реализации продукции, что связано с определенными издержками (затратами ресурсов), то к началу второго периода первоначальная сумма у уменьшится до величины ay (0 ≤ a ≤ 1), а сумма x – y — до величины b(x – y); (0 ≤ b ≤ 1). Наибольший доход, который можно получить от суммарного остатка a . y + b (x – y) в течение второго этапа, равен F 1 [a . y + b(x – y)]. Обозначим через F 2 (x) наибольший доход, который может быть получен от суммы x за оба периода. Этот доход равен максимальному значению суммы доходов |