Менеджмент 3-е издание - Глухов В.В.. Учебник для вузов. 3е изд. Спб. Питер, 2008. 608 с. ил. Серия Учебник для вузов
 Скачать 3.25 Mb.
|
|
Совместимость ограничивающих условий В общую постановку задачи оптимизации входят неравенства вида 1 ( 1... ), n ij j i j a x b i m = ≤ = ∑ где n — число неизвестных; m — число неравенств. Если в каждое неравенство добавить неотрицательное неизвестное y ≥ 0 (i = = 1... m), то от системы неравенств можно перейти к системе уравнений 1 ( 1... ). n ij j i i j a x y b i m = + = = ∑ В этой системе общее число неизвестных N = n + m, где n — число основных неизвестных x j ; m — число дополнительных неизвестных y i , которое равно числу уравнений. Возможны три варианта соотношения величин N и m. 1. Число неизвестных меньше, чем число уравнений: N < m. Например, N = 1, m = 2. Очевидно, эта система решения не имеет, т. е. нет таких значений x 1 , которые бы удовлетворяли обоим уравнениям. В этом случае говорят, что система усло вий несовместна. Значит, если число неизвестных N меньше числа уравнений m, то система решения не имеет и является несовместной. 2. Число неизвестных равно числу уравнений: N = m. Например, нетрудно вычислить, что решением этой системы будут значения x 1 = 2, x 2 = 1. Таким образом, линейная система, в которой число неизвестных N равно числу уравнений m, имеет одно решение. 3. Число неизвестных больше числа уравнений: N > m. Например, 2x 1 + x 2 = 2. Очевидно, что все значения x 1 и x 2 , лежащие на прямой этого уравнения, являются его решением. Если в системе число неизвестных N больше числа уравнений m, то такая система имеет бесчисленное множество ре шений. 7.6. 7.6. 7.6. 7.6. 7.6. Формирование производственной программы Формирование производственной программы Формирование производственной программы Формирование производственной программы Формирование производственной программы Рассмотрим производственный участок, выпускающий два типа деталей. Исход ная заготовка при изготовлении деталей первого типа проходит две операции (то карную и сверлильную) при трудоемкости 20 и 30 ч/шт. соответственно. При из готовлении детали второго типа необходимы три операции (токарная, сверлильная, шлифовальная) при трудоемкости 40, 30, 20 ч/шт. соответственно. Прибыль от продажи деталей равна 1,5 руб./шт. для деталей первого типа и 1 руб./шт. для деталей второго типа. На плановый период ресурс рабочего времени по операциям в часах составля ет: токарная — 1000, сверлильная — 900, шлифовальная — 400 ч. Необходимо по добрать производственную программу выпуска деталей, обеспечивающую мак симальную прибыль. Глава 7. Простейшие типовые математические модели 132 132 132 132 132 Обозначим количество деталей первого типа, принимаемых для выпуска, че рез y, второго типа — х. Математическая постановка задачи определения у и х имеет вид 40 х + 20 у = 1000; 30 х + 30 у = 900; 20 х = 400; х > 0, y > 0; J = 1,5 y + 1 x → max. 7.7. 7.7. 7.7. 7.7. 7.7. Задача о назначениях Задача о назначениях Задача о назначениях Задача о назначениях Задача о назначениях Пусть имеются n работ и n кандидатов для их выполнения. Назначению i го кан дидата (i = 1... n) на j ю работу ( j = 1... n) соответствуют определенная эффектив ность (прибыль, производительность) или затраты какого либо ресурса с ij . Тре буется назначить на выполнение всех видов работ таких кандидатов, которые обеспечат наибольшую эффективность, т. е. минимум суммарных затрат или мак симум прибыли (производительности). Каждого кандидата можно назначить только на одну должность, и каждая работа может быть выполнена только одним кандидатом. Математическая постановка задачи имеет вид: 1 1 1 1 min min ; 1; 1, n n n n ij ij ij ij j j i j J c x x x = = = = = = = ∑ ∑ ∑ ∑ где x ij — искомая переменная: х ij = 1, если i й кандидат распределяется на j ю ра боту; 0 — в противном случае. В такой постановке данная задача относится к классу комбинаторных. 7.8. 7.8. 7.8. 7.8. 7.8. Транспортная задача Транспортная задача Транспортная задача Транспортная задача Транспортная задача Транспортная задача — это задача о выборе плана перевозок однородного про дукта из пунктов производства в пункты потребления. Пусть имеется m пунктов отправления и n пунктов назначения. Ресурсы продукта в пунктах отправления обозначим через a(i), потребность в продукте в пункте потребления — b( j). Расходы на доставку единицы продукта от поставщика i к потребителю j равняются c(i, j). Балансовое условие производства и потребления имеет вид: a(1) + a(2) + … + a(n) = b(1) + b(2) + … + b(m). Требуется определить x(i, j) — количество продукта, доставляемое от пункта производства i к пункту потребления j. Обязательными условиями являются: • необходимость вывоза всего произведенного продукта: x(i, 1) + x(i, 2) + … + x (i, m) = a(i) для всех значений i; • необходимость удовлетворения всех потребителей: x(1, j) + x(2, j) + … + x (n, j) = b( j) для всех значений j. 133 133 133 133 133 7.10. Задача о ранце Оптимальный план доставки продукта должен обеспечить минимум общей суммы затрат на доставку: ( , ) ( , ). i j c i j x i j ∑∑ Решаются транспортные задачи методами линейного программирования. 7.9. 7.9. 7.9. 7.9. 7.9. Задача составления смесей Задача составления смесей Задача составления смесей Задача составления смесей Задача составления смесей Задачи составления рациона корма, состава шихты при выплавке стали, состава цементной смеси относятся к группе задач составления смесей. В такой задаче задается набор исходных материалов, характеризующихся содержанием контро лируемых компонентов а(i, j) — содержание i го компонента в j м виде исходного материала. Требуется определить x(j) — количество j го материала, принимаемого для подготовки комплексной смеси. Совокупность ограничений включает условия вида: x(j) < X(j); x(1) + x(2) + … + x(n) < Y; a(i, 1) x(1) + a(i, 2) x(2) + … + a(i, n) x(n) > A(i). Здесь X(j) — допустимое для использования количество j го материала, Y — общее ограничение на массу исходного материала, A(i) — минимально необходи мое содержание i го компонента в конечном продукте. Оценкой вариантов решения задачи является сумма затрат на состав материа лов в формируемой смеси: J = c(1) x(1) + c(2) x(2) + … + c(n) x(n), где c(j) — расходы на единицу j го материала. 7.10. 7.10. 7.10. 7.10. 7.10. Задача о ранце Задача о ранце Задача о ранце Задача о ранце Задача о ранце Пусть имеется некоторый объем V, который необходимо заполнить различными предметами. Предметов имеется несколько видов, отличающихся объемом v(i) и ценностью c(i). Требуется определить вариант заполнения предметами объема V, чтобы их суммарная ценность оказалась наибольшей. Неизвестные переменные задачи — это x(i) — число предметов i го вида, выбранных для размещения в ранце. Огра ничения задачи имеют вид: x(1) v(1) + x(2) v(2) + … + x(n) v(n) < V; x(i) > 0. Оценка вариантов решения задачи — это сумма J = x(1) c(1) + x(2) c(2) + … + x(n)c(n), которая должна иметь максимальное значение. Глава 7. Простейшие типовые математические модели 134 134 134 134 134 7.11. 7.11. 7.11. 7.11. 7.11. Задача коммивояжера Задача коммивояжера Задача коммивояжера Задача коммивояжера Задача коммивояжера Обычно эта задача формулируется следующим образом. Коммивояжер должен побывать в ряде городов. Известны расстояния между каждой парой городов (вре мя или стоимость проезда). Необходимо выбрать кратчайший маршрут, проходя щий один раз через каждый город. Если расстояние между городами не зависит от направления движения, то задача называется симметричной. Если стоимость проезда меняется при изменении направления движения, задача называется не симметричной. Для задачи коммивояжера при необходимости посещения только двух городов выбора нет. При посещении трех городов и заданном начальном пункте возмож ны 2 маршрута. Если городов четыре, то имеется 6 маршрутов, а при одиннадцати городах — более 3,5 млн допустимых маршрутов. В общем случае при n городах имеется (n –1)! маршрутов. К подобному типу задач сводится множество реальных ситуаций. Например, выбор очередности обработки разнородных изделий, маршрута автотранспорта, задачи выбора маршрута в сетях систем связи. Пример. Пусть имеется 5 пунктов, соединенных между собой дорогами так, что из любого пункта можно проехать в любой другой пункт. Известно время пе ревозки из пункта i в пункт j (табл. 7.1). Таблица 7.1 Время переезда, ед. № маршрута в пункт j № маршрута из пункта i 1 2 3 4 5 1 0 10 25 25 10 2 1 0 10 15 2 3 8 9 0 20 10 4 14 10 24 0 15 5 10 8 25 27 0 Требуется найти маршрут с наименьшей продолжительностью, начинающий ся в данном пункте, проходящий через все пункты и заканчивающийся в пункте выезда. Решение. Введем обозначения: i и j — номера пунктов выезда и въезда; t ij — время переезда из пункта i в пункт j. В общем случае t ij может быть не равно вре мени переезда в обратном направлении — t ij ≠ t ji (например, когда один пункт на вершине горы, а другой — у ее подножия). Введем булевы переменные: 1, если из пункта торговец переедет в пункт ; 0, если не поедет. ij i j δ ⎧ = ⎨ ⎩ Составим модель (рис. 7.1). Из пункта 1 можно выехать в любой из пунктов: 2, или 5, или 3, или 4, или остаться в пункте 1. Но при этом можно выехать только в одном единственном направлении. Это условие можно записать так: δ 11 + δ 12 + δ 13 + δ 14 + δ 15 = 1, 135 135 135 135 135 7.11. Задача коммивояжера или 5 1 1 1, j j δ = = ∑ или для произвольного (любого) i го пункта 5 1 1( 1... 5). ij j i δ = = = ∑ Эти зависимости обеспечивают выполнение условия, согласно которому из каждого пункта выезд производится только один раз и только в одном направ лении. Условие въезда в пункт 1 аналогично условию выезда из пункта 1. Требо вание минимальной продолжительности маршрута запишется в виде целевой функции: min L = t 11 δ 11 + t 12 δ 12 + t 13 δ 13 + t 14 δ 14 + t 15 δ 15 + t 21 δ 21 + t 22 δ 22 + ... + t 55 δ 55 , где t ij берутся из исходной таблицы, а δ ij — искомые переменные. Математическую постановку задачи можно сформулировать в виде: 5 5 1 1 5 1 5 1 min ; 1 ( 1... 5); 1 ( 1... 5); [0;1] , ( , 1... 5). ij ij i j ij j ij i ij L t i j i j δ δ δ δ = = = = ⎧ = ⎪ ⎪ ⎪ ⎪ = = ⎪ ⎨ ⎪ ⎪ = = ⎪ ⎪ = = ⎪⎩ ∑∑ ∑ ∑ В результате решения системы получим следующие значения (рис. 7.2): δ 15 0 = δ 52 0 = δ 23 0 = δ 34 0 = δ 41 0 = 1, остальные δ ij 0 = 0; min L = 10 + 8 + 10 +20 + 14 = 62. Рис. 7.1 1 2 3 4 5 10 8 20 14 10 (7.7) (7.8) (7.10) (7.9) Глава 7. Простейшие типовые математические модели 136 136 136 136 136 Переходя от частной постановки к общей, задачу коммивояжера можно сфор мулировать так: 1 1 5 1 5 1 min ; 1 ( 1... ); 1 ( 1... ); [0;1] ( , 1... ). n n ij ij i j ij j ij i ij L t i n j n i j n δ δ δ δ = = = = ⎧ = ⎪ ⎪ ⎪ ⎪ = = ⎪ ⎨ ⎪ ⎪ = = ⎪ ⎪ = = ⎪⎩ ∑∑ ∑ ∑ 7.12. 7.12. 7.12. 7.12. 7.12. Распределение капитальных вложений Распределение капитальных вложений Распределение капитальных вложений Распределение капитальных вложений Распределение капитальных вложений Пусть известны возможные значения эффективности (например, прирост при были, выпуск продукции и др.) на каждом из четырех предприятий отрасли в ре зультате расширения действующих мощностей (табл. 7.2). Требуется составить план распределения ограниченных капиталовложений по этим предприятиям (К = 200 ден. ед.), максимизирующий общий прирост выпус ка при заданной номенклатуре и структуре отраслевого плана производства про дукции. Рис. 7.2 1 2 3 4 5 10 8 20 14 10 (7.11) (7.12) (7.14) (7.13) Таблица 7.2 Возможные значения эффективности предприятий в результате расширения действующих мощностей Капиталовложения (x), ед. Прирост выпуска продукции i-го предприятия g i (x), ед./год 1 2 3 4 0 50 100 150 200 0 25 60 100 140 0 30 70 90 122 0 36 64 95 130 0 28 56 110 142 137 137 137 137 137 7.12. Распределение капитальных вложений Решение. Данная задача может быть решена методом динамического програм мирования. Обозначим: g i (x) — прирост выпуска продукции на i м предприятии при x единиц капиталовложений на реконструкцию или расширение активной части его основных фондов; F(К) — максимально возможный прирост выпуска продукции при распределении суммы К между четырьмя предприятиями. Тогда, согласно основному функциональному уравнению Беллмана: 4 4 3 0 ( ) max [ ( ) ( )]; x К F К g x F К x ≤ ≤ = + − (7.15) 1 1 1 0 ( ) max [ ( )] ( ), x К F x g x g x ≤ ≤ = = (7.16) т. е. максимальный прирост выпуска продукции на первом предприятии при рас пределении для него (и только для него) единиц капиталовложений x (0 ≤ x ≤ К) будет соответствовать значениям графы 2 исходных данных. Реализация задачи будет заключаться в последовательном решении уравнений Беллмана, описывающих максимальный прирост выпуска при распределении К = 200 между двумя предприятиями, затем тремя и четырьмя. В процессе вычис лений x меняется от 0 до К с шагом Δ = 50: 2 2 1 2 1 2 1 0 50 (50) max [ ( ) (50 )] max[ (0) (50); (50) (0)] max[0 25; 30 0] 30; x F g x F x g g g g ≤ ≤ = + − = + + = = + + = 2 2 1 2 1 2 1 0 100 2 1 (100) max [ ( ) (100 )] max[ (0) (100); (50) (50); (100) (0)] max[0 60; 30 25;70 0] 70; x F g x F x g g g g g g ≤ ≤ = + − = + + + = + + + = 2 2 1 2 1 2 1 0 150 2 1 2 1 (150) max [ ( ) (150 )] max[ (0) (150); (50) (100); (100) (50); (150) (0)] max[0 100; 30 60;70 25; 90 0] 100 x F g x F x g g g g g g g g ≤ ≤ = + − = + + + + = + + + + = и т. д. (табл. 7.3). Из анализа результатов расчетов следует, что наибольший достижимый при рост продукции составит F 4 (200) = g 4 (150) + F 3 (50) = 110 + 36 = 146, т. е. четвертому предприятию должно быть выделено 150, а первым трем — 50 ед. средств. Таблица 7.3 x F 1 (x) F 2 (x) F 3 (x) F 4 (x) 0 50 100 150 200 0 25 60 100 140 0 30 70 100 140 0 36 70 106 140 0 36 70 110 146 Глава 7. Простейшие типовые математические модели 138 138 138 138 138 3 3 2 0 50 (50) max [ (50) (0)] [36 0] 36, x F g F ≤ ≤ = + = + = т. е. все оставшиеся 50 ед. выделяются третьему заводу. Итак, решение задачи: 0 0 0 0 1 2 3 4 0; 50; 150 ден. ед. x x x x = = = = 7.13. 7.13. 7.13. 7.13. 7.13. Игровая модель обмена товарами (модель Эджворта) Игровая модель обмена товарами (модель Эджворта) Игровая модель обмена товарами (модель Эджворта) Игровая модель обмена товарами (модель Эджворта) Игровая модель обмена товарами (модель Эджворта) Рассмотрим «игру» двух лиц, обладающих некоторой суммой, не равной нулю. «Игрок» А имеет а единиц одного товара, «игрок» В — b единиц второго товара. При обмене товарами каждый из «игроков» стремится извлечь пользу. Для участника А итог обмена обозначим через (x, y), для участника В итог дея тельности будет (а – x, b – y). Для определяемых величин x и y учитываются ог раничивающие условия. Значение x находится в пределах от 0 до а, значение y — в пределах от 0 до b. В координатах x, y для прямоугольника допустимых значений искомых неиз вестных строятся линии равной выгодности. Для участника А — это совокупность параллельных выпуклых функций, для участника В — это совокупность парал лельных вогнутых функций. Точки возможных условий контракта — это точки касания функций полезности результата для участников. ГГГГГлава лава лава лава лава 8 8 8 8 8 МЕТОДЫ РЕШЕНИЯ УПРАВЛЕНЧЕСКИХ ЗАДАЧ МЕТОДЫ РЕШЕНИЯ УПРАВЛЕНЧЕСКИХ ЗАДАЧ МЕТОДЫ РЕШЕНИЯ УПРАВЛЕНЧЕСКИХ ЗАДАЧ МЕТОДЫ РЕШЕНИЯ УПРАВЛЕНЧЕСКИХ ЗАДАЧ МЕТОДЫ РЕШЕНИЯ УПРАВЛЕНЧЕСКИХ ЗАДАЧ 8.1. 8.1. 8.1. 8.1. 8.1. Регрессионный анализ Регрессионный анализ Регрессионный анализ Регрессионный анализ Регрессионный анализ Событие — всякий факт, который может произойти или не произойти в результа те опыта как результат предпринятого действия (действий). Признаком отнесен ности факта к разряду событий является ответ «да» либо «нет» на вопрос: «Про изошло ли событие?» Событиями можно назвать как падение монеты гербом вверх при бросании («орел» или «решка»?), так и своевременную поставку сырья и др. События могут быть достоверными, возможными и невозможными. Достоверное событие — событие, которое непременно должно произойти, на пример выпадение любого количества очков на игральной кости, расход ресурсов при выпуске продукции. Возможное — событие, которое может произойти или не произойти: падение монеты гербом вверх, выполнение плана на 100% и др. Невозможное — событие, которое не может произойти: появление (у игрока) двух тузов при вытаскивании одной карты, выпуск сверхплановой продукции без использования дополнительных ресурсов и др. Для выражения возможности события используют численную меру. Числен ную меру возможности события называют вероятностью. Вероятность события A, т. е. P(A), можно вычислить: Глава 8. Методы решения управленческих задач 140 140 140 140 140 ( ) , m P A n = где m — число случаев, когда событие A может произойти; n — общее число случаев. 0, то событие невозможно; Очевидно, что если ( ) 1 — достоверное событие; 0 и <1 — событие возможное. P A ⎧ ⎪ = ⎨ ⎪> ⎩ Вероятность P(A) характеризует возможность появления события А в буду щем. Для оценки того, как часто события уже происходили, используют понятие частоты. Частоту события А обозначают * * ( ) , m P A n = где m * показывает, сколько раз событие произошло; n — общее число произведен ных испытаний. Несовместными называют события, исключающие друг друга. Так, падение монеты вверх гербом и цифрами — это два несовместных события. Очевидно, что сумма вероятностей всех несовместных событий равна 1. Случайные события можно характеризовать числами. Такие числа называют случайными величинами. Случайная величина может принять то или иное значе ние, заранее не известное. Например, случайными величинами являются объем поставленных материалов, трудоемкость операции или работы. Леонид Витальевич Канторович — лауреат Нобелевской премии. Родился в 1912 г. в Санкт Петербурге в семье врача. В 18 лет закончил математиче ский факультет Ленинградского университета и уже через четыре года получил звание профессора. В 1935 г. ему была присуждена ученая степень доктора физико математических наук. Л. В. Канторович является основателем рос сийской школы функционального анализа, вычислительной математики, язы ков программирования. Крупнейшим его открытием стало введение в мате матическую и экономическую науки понятия «линейное программирование» (1939). Это универсальная математическая модель решения многих экономи ческих задач. Им были введены «двойственные оценки» ресурсов, показы вающие ценность этих ресурсов для общества. Двойственные оценки полу чили разнообразное толкование в зависимости от рассматриваемого круга задач. Одной из разработок Л. В. Канторовича была теория дифференциаль ной ренты. Рентные оценки позволяют измерить стоимость пользования при родными ресурсами (землей, водой, воздухом и т. п.). За короткий период Л. В. Канторовичу удалось построить разветвленную теорию на базе линейного программирования, а также создать основы мате матической теории. Им были разработаны транспортная задача, задача рас кроя материалов. В 1965 г. Л. В. Канторович совместно с В. С Немчиновым и В. В. Новожиловым получил Ленинскую премию за разработку оптимизаци онного подхода к плановому управлению экономикой. В 1975 г. Л. В. Канторович за разработку теории оптимального использова ния ресурсов был удостоен Нобелевской премии. 141 141 141 141 141 8.1. Регрессионный анализ Конкретное измеренное значение случайной величины называют ее реализа цией. Различные реализации случайной величины относят к несовместным со бытиям. Действительно, если трудоемкость изготовления детали составила 100 человеко часов, то она не может быть равна 105 или иметь любое другое значение. Случайная величина не может быть описана одним конкретным числом. Ее можно описать либо количественными характеристиками, либо законом распре деления. Наиболее распространенными характеристиками случайной величины являются: математическое ожидание, дисперсия, среднее квадратическое откло нение, коэффициент вариабельности. Математическое ожидание характеризует среднее значение случайной вели чины и обозначается M x , или M[x], или : x 1 1 ( ) , n i i M x x n = = ∑ где n — число реализаций; x i — значение случайной величины в i й реализации. Дисперсия D[x] (или D x ) характеризует разброс значений случайной величины: 2 1 ( ) [ ] n i i x x D x n = − = ∑ Так как размерность дисперсии равна квадрату размерности самой случайной величины, использовать дисперсию для относительной оценки разброса случай ной величины нельзя. Поэтому разброс оценивают средним квадратическим отклонением: 2 2 1 ( ) [ ] или [ ] n i x x i x x D x D x n σ σ = − = = = ∑ Удобной характеристикой случайной величины является коэффициент вариа бельности, который показывает относительное значение разброса случайной ве личины. |