Математическое моделирование социально-экономических процессов

В.П. Василенков, И.Б. Болотин МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Федеральное агентство по образованию Смоленский государственный университет В.П. Василенков, И.Б. Болотин МАТЕМАТ ИЧЕСКО Е М ОД ЕЛ И Р О ВА Н И Е С О Ц И А Л Ь Н О- Э КО Н О М И Ч Е С К И Х ПРОЦЕССОВ Практический курс для студентов специальностей «Менеджмент организации» и «Государственное и муниципальное управление» Часть 2 Смоленск Издательство СмолГУ 2009 1 УДК 330.4(075.8) ББК 65в6я73 В 190 Печатается по решению редакционно-издательского совета СмолГУ Рецензент Е.П. Емельченков, кандидат физико-математических наук, доцент, заведующий кафедрой информатики Смоленского государственного университета Василенков В.П. В 190 Математическое моделирование социально-экономических процессов: практический курс для студентов специальностей «Менеджмент организации» и «Государственное и муниципальное управление» / В.П. Василенков, И.Б. Болотин; Смол. гос. унт. – Смоленск: Изд-во СмолГУ, 2009. – Ч. 2. – 100 с. Данное пособие предназначено для студентов специальностей «Менеджмент организации» и «Государственное и муниципальное управление» и полностью соответствует программе соответствующего нормативного курса. Кроме того, оно может быть использовано и студентами других специальностей при проведении соответствующих элективных курсов. Основной упор делается на использование четких алгоритмов при решении практических задач. Большое количество простых, но в то же время содержательных примеров, в основном составленных авторами, позволяет улучшить усвоение материала. УДК 330.5(075.8) ББК 65в6я73 © В.П. Василенков, И.Б. Болотин, 2009 © Издательство СмолГУ, 2009 2 Введение В настоящее время деятельность в любой области экономики требует от специалиста применения современных методов, в частности, хорошего знания математических методов и умения их применять для решения конкретно поставленных задач. Математическое моделирование социально-экономических процессов стало неотъемлемой частью методов экономики. Данное учебное пособие предназначено для студентов второго курса специальностей «Менеджмент организации» и «Государственное и муниципальное управление» факультета управления по соответствующему нормативному курсу, а также может быть использовано и студентами других специальностей при проведении соответствующего элективного курса. Главы этой части посвящены применению: • задач оптимизации в экономике; • методов теории игр; • методов теории графов в экономических исследованиях. Как и первая часть, пособие построено таким образом, чтобы студенты могли самостоятельно разобраться с основными определениями и методами, используемыми при изучении социально-экономических процессов. Основной упор делается на использование четких алгоритмов при решении практических задач. Большое количество простых, но в то же время содержательных примеров, в основном составленных авторами, позволяет улучшить усвоение материала. Большинство примеров решено двумя способами – вручную и с использованием компьютера. Авторы поступают так совершенно осознанно, так как считают, что, только «пропустив» через себя полное решение задачи, можно освоить конкретный метод решения. Однако, в отличие от первой части, приведенные решения в системе компьютерной математики Mathcad 2001i Professional существенно используют специфику рассматриваемого круга вопросов. Авторы выражают глубокую признательность профессору В.А. Петрову и заведующему кафедрой информатики Е.П. Емельченкову за ценные замечания, способствовавшие улучшению рукописи данного пособия. 3 Глава 1. Задачи оптимизации в экономике § 1. Постановка некоторых задач линейного программирования Задача о распределении ресурсов. В распоряжении некоторого предприятия имеются определенные ресурсы (сырье, рабочая сила, оборудование и т.п.) R1 , R2 , …, Rm в количествах, соответственно, b1 , b2 , …, bm единиц. С помощью этих ресурсов могут производиться товары T1 , T2 , …, Tn . Для производства одной единицы товара T j необходимо aij единиц ресурса Ri ( i = 1, 2, ..., m , j = 1, 2, ..., n ). Себестоимость каждой единицы товара T j равна s j , а цена каждой такой единицы равна c j . Рынок не может поглотить более чем k j единиц товара T j . Требуется определить, какое количество единиц и какого товара нужно произвести для того, чтобы получить максимальную прибыль. Построение математической модели задачи о распределении ресурсов. Составим следующую таблицу 1.1. Таблица 1.1 … s1 s2 sn Товары … k1 k2 kn … c1 c2 cn Ресурсы … T1 T2 Tn … b1 R1 a11 a12 a1n … b2 R2 a21 a22 a2 n … … … … … … … bm Rm am1 am 2 amn Обозначим через x1 , x2 , …, xn планируемое к производству количество товаров T1 , T2 , …, Tn , соответственно. Ресурсов, которыми располагает предприятие, должно быть достаточно для обеспечения планируемого производства. Значит, должны выполняться следующие неравенства: n ∑ a1 j x j ≤ b1 , j =1 n ∑ a2 j x j ≤ b2 , …, j =1 n ∑ amj x j ≤ bm . j =1 С учетом условий спроса товары следует произвести в количествах не больших, чем их можно продать, т.е. x1 ≤ k1 , x2 ≤ k 2 , …, xn ≤ k n . 4 Прибыль, получаемая предприятием, равна n z = ∑q jxj , где j =1 q j = c j − s j – чистая прибыль, получаемая от реализации одной единицы товара T j . Таким образом, задача о распределении ресурсов сводится к следующей задаче: требуется найти значения переменных x1 , x2 , …, xn , которые удовлетворяют неравенствам: ⎧n ⎪∑ aij x j ≤ bi , i = 1, m , ⎪ j =1 ⎪ (1.1) ⎨x j ≤ k j , ⎪ ⎪ x j ≥ 0, j = 1, n ⎪⎩ и обращают в максимум функцию этих переменных n z = ∑q jxj (1.2). j =1 Транспортная задача. Предположим, что имеется m исходных пунктов A1 , A2 , …, Am (заводов-изготовителей, складов готовой продукции и т.п.) и n пунктов назначения B1 , B2 , …, Bn (складов, торговых учреждений и т.п.). Количество продукции, производимой в пункте Ai ( i = 1, m ), равно ai , а количество продукции, потребляемой в пункте B j ( j = 1, n ), – b j . Пусть cij – стоимость перевозки единицы продукции из пункта Ai в пункт B j . Требуется составить план перевозок, минимизирующий общие затраты по перевозке продукции. Математическая модель транспортной задачи. Обозначим через xij количество продукции, перевозимой из исходного пункта Ai в пункт назначения B j , тогда транспортная задача формулируется следующим образом: требуется найти минимальное значение функции m n z = ∑∑ cij xij (1.3) i =1 j =1 при выполнении следующих ограничений ⎧n ⎪∑ xij ≤ ai , i = 1, m , ⎪ j =1 ⎪⎪ m ⎨∑ xij ≥ b j , j = 1, n , ⎪ i =1 ⎪ xij ≥ 0. ⎪ ⎪⎩ 5 (1.4) Задачи о пищевом рационе. Имеется m видов продуктов питания: P1 , P2 , …, Pm . Известна стоимость единицы каждого продукта: c1 , c2 , …, cm . Из этих продуктов необходимо составить пищевой рацион с содержанием различного рода полезных веществ V1 , V2 , …, Vn не менее b1 , b2 , …, bn единиц соответственно. Единица продукта Pi содержит aij единиц вещества V j . Требуется составить рацион так, чтобы его стоимость была минимальной и он содержал необходимое организму количество полезных веществ. Математическая модель задачи о пищевом рационе. Обозначим через x1 , x2 , …, xm количество приобретаемых продуктов P1 , P2 , …, Pm . Тогда задача о пищевом рационе сводится к следующей задаче: требуется определить значения переменных x1 , x2 , …, xm , при которых функция m z = ∑ ci xi (1.5) i =1 достигает минимума при выполнении ограничений вида ⎧m ⎪∑ aij xi ≥ b j , j = 1, n , ⎪ i =1 ⎪m (1.6) ⎨∑ xi ≤ N , ⎪ i =1 ⎪ x j ≥ 0, ⎪ ⎩ где N – количество продуктов, которое в состоянии «проглотить» организм. § 2. Основная задача линейного программирования. Симплекс-метод Присмотревшись внимательнее к ограничениям и функциям сформулированных выше задач (1.1)-(1.2), (1.3)-(1.4) и (1.5)-(1.6), можно заметить, что переменные входят в них в первой степени, т.е. эти ограничения и функции являются линейными. Задачи такого рода обычно называются задачами линейного программирования. Для рассмотрения алгоритма решения таких задач введем понятие основной задачи линейного программирования. 6 Определение 1.1. Основной задачей линейного программирования называется задача, состоящая в отыскании значений переменных x1 , x2 , …, xn , удовлетворяющих ограничениям ⎧n ⎪∑ aij x j = bi , i = 1, m , ⎨ j =1 ⎪ x ≥ 0, j = 1, n ⎩ j (1.7) и обращающих в минимум функцию n z = ∑c j x j , (1.8) j =1 где aij и c j – заданные числа. Замечание. К задаче (1.7)-(1.8) можно свести любую задачу линейного программирования. Действительно, если, например, функция z обращается в максимум, то функция ~ z = − z обращается в минимум. Кроме того, от любого ограничения-неравенства можно перейти к ограничениюравенству путем введения «фиктивной» неотрицательной переменной. ( ) ( ) Определение 1.2. Упорядоченный набор чисел x1* , x2* , ..., xn* называется опорным решением задачи (1.7)-(1.8), если он удовлетворяет системе ограничений (1.7). Определение 1.3. Упорядоченный набор чисел x1* , x2* , ..., xn* называется оптимальным решением задачи (1.7)-(1.8), если он удовлетворяет системе ограничений (1.7) и обращает в минимум функцию (1.8). Определение 1.4. Функция (1.8) называется целевой функцией задачи (1.7)-(1.8). Алгоритм симплекс-метода I. Отыскание опорного решения Рассмотрим систему ограничений (1.7) в развернутом виде, опустив условия неотрицательности, получим ⎧a11 x1 + a12 x2 + ... + a1n xn = b1 , ⎪a x + a x + ... + a x = b , ⎪ 21 1 22 2 2n n 2 (1.9) ⎨ .......... .......... .......... .......... ⎪ ⎪⎩am1 x1 + am 2 x2 + ... + amn xn = bm . 1. Выразить первые r переменных x1 , x2 , …, xr через остальные n − r переменные xr +1 , …, xn методом Гаусса и получить систему уравнений вида 7 ⎧ x1 = β1 + α1,r +1 xr +1 + α1,r + 2 xr + 2 + ... + α1,n xn , ⎪ ⎪ x2 = β 2 + α 2,r +1 xr +1 + α 2,r + 2 xr + 2 + ... + α 2,n xn , (1.10) ⎨ .......... .......... .......... .......... .......... ...... ⎪ ⎪ xr = β r + α r ,r +1 xr +1 + α r ,r + 2 xr + 2 + ... + α r ,n xn . ⎩ Определение 1.5. Переменные x1 , x2 , …, xr называются базисными, а xr +1 , xr + 2 , …, xn – свободными. 2. Если в системе (1.10) все свободные члены β1 , β 2 , …, β r неотрицательны, то решение (β1 , β 2 , ..., β r , 0, 0, ..., 0 ) – опорное. Перейти к поиску оптимального решения. 3. Если хотя бы одно из чисел β k < 0 ( k = 1, r ), а в соответствующем урав- нении все коэффициенты α k , j ( j = r + 1, n ) отрицательны, то задача не имеет решений. 4. Пусть свободный член β k < 0 . Рассмотреть соответствующее уравнение и найти коэффициент α k , j > 0 . Рассмотреть все коэффициенты α i, j , имеющие разные знаки с соответствующим свободным членом βi и выбрать тот, для которого отношение к нему свободного члена минимально по модулю. 5. Пусть выбран коэффициент α p,q . Из p -го уравнения выразить переменную xq и подставить ее во все уравнения системы (1.10), т.е. ввести переменную xq в состав базисных переменных, а переменную x p сделать свободной. 6. Повторить пункты 2-5. II. Отыскание оптимального решения 1. Подставив базисные переменные, полученные в результате отыскания опорного решения в целевую функцию (1.8), выразить ее через свободные переменные xr +1 , xr + 2 , …, xn . Тогда целевая функция примет вид: (1.11) z = c0 + cr +1 xr +1 + cr + 2 + ... + cn xn . 2. Если все коэффициенты ck ≥ 0 ( k = r + 1, n ), то найденное решение оптимально. 3. Если хотя бы один коэффициент ck < 0 , а в системе (1.10) все коэффициенты ai ,k неотрицательны, то задача не имеет решений (целевая функция неограничена). 4. Пусть коэффициент cq < 0 (если таких несколько, то выбрать наибольший по модулю). Рассмотреть в системе (1.10) все коэффициенты α i ,q < 0 и выбрать тот, для которого отношение к нему свободного члена минимально по модулю. 8 5. Пусть выбран коэффициент α p,q . Ввести переменную xq в состав базисных переменных, а переменную x p сделать свободной. 6. Повторить пункты 2-5. Замечание. Если целевая функция максимизируется, то критерием оптимальности найденного решения будет неположительность коэффициентов ck ≥ 0 ( k = r + 1, n ) в (1.11). Пример 1.1. Автосалон «Смоленский» планирует приступить к реализации трех видов автомобилей «Ford Focus», «Ford Mondeo» и «Ford C-Max», используя при этом площади торговых залов и время обслуживающего персонала. Затраты указанных ресурсов на продажу одной партии товара каждого вида, их объемы и прибыль, получаемая от реализации каждой партии, приведены в таблице 1.2. Найдите оптимальную структуру продаж автомобилей, обеспечивающую автосалону максимальную прибыль. Таблица 1.2 Ресурсы Запас Затраты ресурсов ресурса Ford Focus Ford Mondeo Ford C-Max Время, чел/ч 370 0,5 0,7 0,6 2 Площадь, м 9000 10 19 14 Прибыль, тыс. руб. 500 800 600 Решение Составим математическую модель задачи. Пусть x1 , x2 и x3 – планируемое к продаже количество автомобилей «Ford Focus», «Ford Mondeo» и «Ford C-Max» соответственно. Тогда прибыль, получаемая автосалоном, будет иметь вид: z = 500 x1 + 800 x2 + 600 x3 , (1.12) а ограничения на переменные x1 , x2 и x3 будут задаваться следующей системой неравенств: ⎧0,5 x1 + 0,7 x2 + 0,6 x3 ≤ 370, ⎪ (1.13) ⎨10 x1 + 19 x2 + 14 x3 ≤ 9000, ⎪ ⎩ x j ≥ 0, j = 1, 3. Приведем задачу (1.12)-(1.13) к основной задаче линейного программирования. Введем в рассмотрение функцию ~z = − z и фиктивные переменные x4 , x5 ≥ 0 , тогда задача (1.12)-(1.13) примет вид: ~ z = −500 x1 − 800 x2 − 600 x3 , (1.14) ⎧0,5 x1 + 0,7 x2 + 0,6 x3 + x4 = 370, ⎪ + x5 = 9000, ⎨10 x1 + 19 x2 + 14 x3 ⎪ ⎩ x j ≥ 0, j = 1, 5. 9 (1.15) Воспользуемся алгоритмом симплекс-метода. Найдем опорное решение. Имеем = 370, ⎧5 x1 + 7 x2 + 6 x3 + 10 x4 = 3700, ⎧0,5 x1 + 0,7 x2 + 0,6 x3 + x4 ⎨ ⎨ + x5 = 9000, ⎩10 x1 + 19 x2 + 14 x3 + x5 = 9000, ⎩10 x1 + 19 x2 + 14 x3 136 78 7 ⎧ 292 x x x x5 , = − − + 1 3 4 = 3700, ⎪⎪ ⎧5 x1 + 7 x2 + 6 x3 + 10 x4 25 5 25 ⎨ ⎨ 5 x2 + 2 x3 − 20 x4 + x5 = 1600, ⎩ ⎪ x = 320 − 2 x + 4 x − 1 x . 3 4 5 ⎪⎩ 2 5 5 Решение (292, 320, 0, 0, 0) является опорным. Найдем оптимальное решение. Подставим базисные переменные в целевую функцию (1.14), получим ~ z = −402 000 + 396 x3 + 4600 x4 + 20 x5 . Так как все коэффициенты при свободных переменных положительны, то найденное решение является оптимальным и max z = 402 000 . Таким образом, автосалону «Смоленский» следует планировать к продаже автомобили «Ford Focus» и «Ford Mondeo» в количествах 292 и 320 штук соответственно и отказаться от продажи автомобилей «Ford C-Max», при этом прибыль составит 402 млн. руб. Программа в системе Mathcad 2001i Professional 10 § 3. Анализ модели на чувствительность Под анализом модели на чувствительность понимают изучение реакции оптимального решения на изменения исходной модели. 11 Обычно выделяют две основные задачи анализа на чувствительность: • степень влияния на оптимальное решение изменения запасов ресурсов; • степень влияния на оптимальное решение изменения коэффициентов целевой функции. Рассмотрим каждую из этих задач на основе примера 1.1. 1) Определим предельно допустимое увеличение времени обслуживающего персонала, позволяющее улучшить найденное оптимальное решение. Получим, что при увеличении времени до 450 чел/ч структура продаж будет задаваться таблицей 1.3. Таблица 1.3 Модель автомобиля Количество автомобилей, планируемых к продаже, шт. Ford Focus 900 Ford Mondeo Ford C-Max Максимальная прибыль 450 млн. руб 2) Определим предельно допустимое увеличение торговых площадей, позволяющее улучшить найденное оптимальное решение. Получим, что при увеличении площадей торговых залов до 10 000 м2 структура продаж будет задаваться таблицей 1.4. Таблица 1.4 Модель автомобиля Количество автомобилей, планируемых к продаже, шт. Ford Focus 12 Ford Mondeo 520 Ford C-Max Максимальная прибыль 422 млн. руб. 3) Так как при подстановке найденного оптимального решения задачи 1.1 все неравенства системы (1.13) обращаются в равенства, то снижение запасов ресурсов будет приводить к уменьшению оптимального значения целевой функции. 4) При изменении цены на автомобиль Ford C-Max до 640 тыс. руб. изменения структуры продаж не происходит. 5) Изменение цен на автомобили Ford Focus и Ford Mondeo будет приводить к изменению оптимальной прибыли, однако, если цена, например, на Ford Focus будет изменяться от 438 до 571 тыс. руб., то изменения структуры продаж происходить не будет. Аналогичная картина будет наблюдаться, если цены на Ford Mondeo будут находиться в пределах от 700 до 949 тыс. руб. 12 6) Если поставщик автомобилей потребует от автосалона, чтобы на продажу были выставлены не менее 100 автомобилей Ford C-Max, то структура продаж будет задаваться таблицей 1.5. Таблица 1.5 Модель автомобиля Количество автомобилей, планируемых к продаже, шт. Ford Focus 228 Ford Mondeo 280 Ford C-Max 100 Максимальная прибыль 398 млн. руб. § 4. Двойственные задачи линейного программирования Пусть дана следующая задача линейного программирования: требуется найти значения переменных x1 , x2 , …, xn , при которых функция n z = ∑c j x j (1.16) j =1 достигает наименьшего значения при выполнении ограничений следующего вида: ⎧ n ⎪ ∑ aij x j ≥ bi , i = 1, m1 ; m1 ≤ m, ⎪ jn=1 ⎪ (1.17) ⎨∑ aij x j = bi , i = m1 + 1, m, ⎪ j =1 ⎪ x j ≥ 0, j = 1, n1 ; n1 ≤ n ⎪ ⎩ и x j – произвольного знака при j = n1 + 1, n . Определение 1.6. Двойственной задачей к задаче (1.16)-(1.17) называется задача отыскания значений переменных y1 , y 2 , …, y m , обращающих в максимум функцию m ~ z = ∑ bi yi (1.18) i =1 при выполнении ограничений следующего вида: ⎧m ⎪ ∑ aij yi ≤ c j , j = 1, n1 ; n1 ≤ n, ⎪ im=1 ⎪ j = n1 + 1, n, ⎨∑ aij yi = c j , ⎪ i =1 i = 1, m1 ; m1 ≤ m ⎪ yi ≥ 0, ⎪ ⎩ и yi – произвольного знака при i = m1 + 1, m 13 (1.19) Замечание. Из определения 1.6 видно, что задача (1.16)-(1.17) является двойственной к задаче (1.18)-(1.19). Поэтому говорят о паре двойственных задач. Алгоритм построения двойственной задачи 1. Упорядочить запись исходной задачи, т.е. если целевая функция задачи минимизируется, то ограничения-неравенства должны быть вида ≥ , если максимизируется – то вида ≤ . 2. Если исходная задача является задачей минимизации, то двойственная задача будет задачей максимизации. При этом вектор, образованный из коэффициентов при неизвестных целевой функции исходной задачи, совпадает с вектором констант в правых частях ограничений двойственной задачи. И наоборот. 3. Каждой переменной yi двойственной задачи соответствует i -е ограничение исходной задачи. И наоборот. 4. Матрица из коэффициентов при неизвестных двойственной задачи образуется транспонированием матрицы, составленной из коэффициентов при неизвестных исходной задачи. 5. Если на j -ю переменную исходной задачи наложено условие неотрицательности, то j -е ограничение двойственной задачи будет неравенством, в противном случае – равенством. Аналогично связаны между собой ограничения исходной задачи и переменные двойственной задачи. Пример 1.2. Построить двойственную задачу к данной z = 2 x1 − x2 + x3 + x4 − 2 x5 , (1.20) ⎧3 x1 − 2 x2 + x3 + x4 − x5 ≤ 8, ⎪ x + 3 x + x + 3 x − 2 x = 6, 2 3 4 5 ⎪⎪ 1 (1.21) ≤ 5, ⎨ x1 + x2 + x3 − x4 ⎪2 x − 5 x + x 4 + 3 x 5 ≥ 7, 2 ⎪ 1 ⎪⎩ x1 ≥ 0, x2 ≥ 0, x5 ≥ 0, если целевая функция (1.20) минимизируется. Решение Воспользуемся алгоритмом построения двойственной задачи. Упорядочим запись исходной задачи с учетом того, что целевая функция минимизируется. Получим ⎧− 3 x1 + 2 x2 − x3 − x4 + x5 ≥ −8, ⎪ x + 3 x + x + 3 x − 2 x = 6, 1 2 3 4 5 ⎪⎪ (1.21) ≥ −5, ⎨ − x1 − x2 − x3 + x4 ⎪ 2x − 5x + x 4 + 3 x 5 ≥ 7, 1 2 ⎪ ⎪⎩ x1 ≥ 0, x2 ≥ 0, x5 ≥ 0. 14 Составим матрицу коэффициентов, стоящих при неизвестных в системе ограничений (1.21), и транспонируем ее. Имеем ⎛− 3 1 −1 2 ⎞ ⎟ ⎜ ⎛− 3 2 −1 −1 1 ⎞ ⎟ ⎜ 3 − 1 − 5⎟ ⎜ 2 3 1 3 − 2⎟ ⎜ 1 A=⎜ , AT = ⎜ − 1 1 − 1 0 ⎟ . ⎟ ⎟ ⎜ −1 −1 −1 1 ⎟⎟ ⎜⎜ 1 1 ⎟ ⎜ −1 3 1 3 ⎠ ⎝ 2 −5 0 ⎜ 1 −2 0 3 ⎟⎠ ⎝ Запишем векторы коэффициентов целевой функции (1.20) и констант, стоящих в правых частях системы ограничений (1.21), получим C = (2; − 1;1;1; − 2 ) , B = (− 8; 6; − 5; 7 ) . Так как переменные x1 , x2 и x5 неотрицательны, то первое, второе и пятое ограничения в системе ограничений двойственной задачи будут неравенствами. Кроме того, так как в системе (1.21) первое, второе и четвертое ограничения являются неравенствами, то соответствующие переменные двойственной задачи будут неотрицательными. Пусть y1 , y 2 , y3 и y 4 – переменные двойственной задачи, тогда целевая функция будет иметь вид: ~ z = −8 y1 + 6 y 2 − 5 y3 + 7 y 4 (1.22) и будет максимизироваться, а соответствующая система ограничений примет вид: ⎧− 3 y1 + y 2 − y3 + 2 y 4 ≤ 2, ⎪ 2 y + 3 y − y − 5 y ≤ −1, 1 2 3 4 ⎪ ⎪⎪ − y1 + y 2 − y3 = 1, (1.23) ⎨ − + + + = 3 1 , y y y y 1 2 3 4 ⎪ ⎪ y1 − 2 y 2 + 3 y 4 ≤ −2, ⎪ ⎪⎩ y1 ≥ 0, y 2 ≥ 0, y 4 ≥ 0 . Для пары двойственных задач (1.16)-(1.17) и (1.18)-(1.19) справедливо следующее утверждение, называемое принципом двойственности. Теорема 1.1. Если одна из двойственных задач имеет оптимальное решение ( x1 , x2 , ..., xn ) , то и другая имеет оптимальное решение ( y1 , y2 ,..., ym ) . При этом экстремальные значения целевых функций совпадают, т.е. справедливо равенство n m j =1 i =1 ∑ c j x j = ∑ bi yi . (1.24) Если целевая функция одной из задач двойственной пары неограничена, то другая задача не имеет решения. Замечание. Из теоремы 1.1 следует, что для разрешимости одной из двойственных задач необходимо и достаточно, чтобы каждая из задач имела хотя бы одно решение. При этом решения пары двойственных задач 15 (x1 , x2 ,..., xn ) и ( y1 , y2 ,..., ym ) будут оптимальными тогда и только тогда, когда выполняется равенство (1.24). Экономическая интерпретация двойственной задачи Пусть некоторое предприятие располагает ресурсами b1 , b2 , …, bm , которые могут использоваться для выпуска n видов продукции. Пусть также известны стоимость единицы j -го вида продукции c j ( j = 1, n ) и норма потребления i -го ( i = 1, m ) ресурса на производство единицы j -ой продукции, равная aij . Требуется определить объем производства продукции каждого вида x j , максимизирующий суммарную стоимость производимой продукции n z = ∑c j x j . (1.23) j =1 При этом расход ресурсов не должен превышать их наличия, т.е. ⎧n ⎪∑ aij x j ≤ bi , i = 1, m, ⎨ j =1 ⎪ x ≥ 0, j = 1, n . ⎩ j (1.23) Соответствующая двойственная задача будет формулироваться следующим образом. Предположим, что некоторая организация может закупить все ресурсы, которыми располагает предприятие. Необходимо определить оптимальные цены yi ( i = 1, m ) на эти ресурсы исходя из условия, что покупающая организация должна уплатить сумму, не меньшую той, которую может выручить предприятие при организации собственного производства продукции. Получим, что система ограничений поставленной задачи имеет вид: ⎧m ⎪∑ a ji yi ≥ c j , j = 1, n , (1.25) ⎨ i =1 ⎪ y ≥ 0, i = 1, m , ⎩ i а целевая функция задается равенством m ~ z = ∑ bi yi (1.26) i =1 и минимизируется. Замечание. Здесь каждое j -oe ограничение из системы (1.25) представляет собой неравенство, левая часть которого равна оценке всех ресурсов, расходуемых на производство j -го вида продукции, а правая часть – стоимости единицы этой продукции. 16 Пример 1.3. В условиях финансового кризиса компания «Два товарища» хочет поглотить автосалон «Смоленский». Какой вариант поглощения будет наиболее оптимальным для обеих сторон. Решение Составим двойственную задачу к задаче (1.12)-(1.13), получим, что требуется найти значения переменных y1 , y 2 , обращающих в минимум функцию ~ z = 370 y1 + 9000 y 2 (1.27) и удовлетворяющих системе ограничений ⎧0,5 y1 + 10 y 2 ≥ 500, ⎪0,7 y + 19 y ≥ 800, ⎪ 1 2 (1.28) ⎨ y y + ≥ , 6 14 600 , 1 2 ⎪ ⎪⎩ y1 , y 2 ≥ 0. Решим задачу (1.27)-(1.28) симплекс-методом. Введем неотрицательные фиктивные переменные y3 , y 4 , y5 , получим = 500, ⎧0,5 y1 + 10 y 2 − y3 ⎪ − y4 = 800, ⎨0,7 y1 + 19 y 2 ⎪0,6 y + 14 y − y5 = 600. 1 2 ⎩ Найдем опорное решение. Получим, 38 ⎧ ⎪ y1 = 600 + 5 y3 − 4 y 4 , ⎪ 7 1 ⎪ y3 + y 4 , (1.28) ⎨ y 2 = 20 − 25 5 ⎪ 16 2 ⎪ y y y4 . 40 = + + 5 3 ⎪ 25 5 ⎩ Значит, решение (600; 20; 0; 0; 40 ) является опорным. Проверим найденное решение на оптимальность. Выразим целевую функцию (1.27) через свободные переменные, получим ~ z = 402 000 + 292 y3 + 320 y 4 . (1.28) Так как все коэффициенты при свободных переменных в целевой функции положительны, то найденное решение является оптимальным. Таким образом, компании «Два товарища» следует сделать автосалону «Смоленский» предложение на 402 млн. руб. Программа в системе Mathcad 2001i Professional 17 18 § 5. Целочисленное программирование Нередко приходится рассматривать задачи, в которых неизвестные величины могут принимать только целочисленные значения. Например, задачи, связанные с нахождением оптимального сочетания различных компьютеров, обеспечивающих наибольшую производительность и т.п., т.е. задач, в которых рассматриваемые объекты являются неделимыми. При решении таких задач с целочисленными переменными используют различные модификации симплекс-метода. Наиболее известные методы решения целочисленных задач – метод отсечений и метод ветвей и границ. Рассмотрим основную задачу целочисленного программирования: требуется найти значения переменных x1 , x2 , …, xn , обращающих в минимум функцию n z = ∑c j x j (1.29) j =1 и удовлетворяющих системе ограничений вида: ⎧n ⎪∑ aij x j = bi , i = 1, m , ⎪ j =1 ⎪ ⎨ x j ≥ 0, ⎪ ⎪ x j ∈ Z , j = 1, n . ⎪⎩ (1.30) Алгоритм метода отсечений 1. Найти симплекс-методом оптимальное решение задачи (1.29)-(1.30), отбросив условия целочисленности. 19 2. Пусть результатом п. 1 служит система ⎧ x1 = β1 + α1,r +1 xr +1 + α1,r + 2 xr + 2 + ... + α1,n xn , ⎪ ⎪ x2 = β 2 + α 2,r +1 xr +1 + α 2,r + 2 xr +1 + ... + α 2,n xn , (1.31) ⎨ .......... .......... .......... .......... .......... .......... ⎪ ⎪ xr = β r + α r ,r +1 xr +1 + α r ,r + 2 xr + 2 + ... + α r ,n xn . ⎩ Если все числа β1 , β 2 , …, β r целые, то найденное решение (β1 , β 2 ,..., β r , 0, 0,..., 0) – оптимально. 3. Если задача (1.29)-(1.30) неразрешима без условий целочисленности, то исходная задача неразрешима. 4. Если среди свободных членов β1 , β 2 , …, β r в (1.31) есть хотя бы один нецелый, то выбрать тот, который имеет наибольшую дробную часть. Пусть выбран свободный член β k . Сформировать правильное отсечение в виде неравенства {− α k ,r +1}xr +1 + {− α k ,r +2 }xr +2 + ... + {− α k ,n }xn ≥ {β k }. (1.32) 5. Преобразовать отсечение (1.32) введением фиктивной целочисленной переменной xn+1 в уравнение вида: {− α k ,r +1}xr +1 + {− α k ,r +2 }xr +2 + ... + {− α k ,n }xn − xn+1 = {β k }. (1.33) 6. Получить расширенную задачу, добавив уравнение (1.33) к системе (1.31). 7. Составленную расширенную задачу решить симплекс-методом. Если оптимальное решение будет целочисленным, то оно является решением исходной задачи (1.29)-(1.30). В противном случае повторить п. 4-7. Замечание. Если в процессе решения появится уравнение с нецелым свободным членом и целыми остальными коэффициентами, то исходная задача неразрешима в целых числах. Пример 1.4. Фирма «Лучшие окна» производит и осуществляет установку пластиковых окон и дверей. Контейнер объемом 12 м3 помещен в фургон грузоподъемностью 1200 кг. Контейнер требуется заполнить дверьми и окнами. Масса (в кг), объем (в м3) и стоимость (в руб.) единицы груза приведены в таблице 1.6. Таблица 1.6 Вид груза Масса Объем Стоимость Окно 30 1,5 8000 Дверь 10 1 4500 Определите оптимальную загрузку контейнера так, чтобы стоимость перевозимого груза была максимальной, а на объект доставлялось не менее двух дверей. 20 Решение Пусть x1 и x2 – планируемое к загрузке количество окон и дверей соответственно. Тогда по условию задачи требуется найти значения переменных x1 и x2 , обращающих в максимум функцию z = 8000 x1 + 4500 x2 (1.32) и удовлетворяющих системе ограничений вида: ⎧30 x1 + 10 x2 ≤ 1200, ⎪1,5 x + x ≤ 12, 2 ⎪⎪ 1 (1.33) ⎨ x2 ≥ 2, ⎪ x ≥ 0, ⎪ 1 ⎪⎩ x1 , x2 ∈ Z . Введем фиктивные неотрицательные целые переменные x3 , x4 и x5 . Тогда система (1.33) примет вид: ⎧30 x + 10 x + x = 1200, 2 3 ⎪ 1 + x4 = 12, ⎪1,5 x1 + x2 ⎪ − x5 = 2, x2 (1.34) ⎨ ⎪ x ≥ 0, ⎪ j ⎪ x ∈ Z , j = 1, 5. ⎩ j Воспользуемся алгоритмом метода отсечений, получим 20 2 2 ⎧ x x x5 , = − − 1 4 = 1200, ⎪ ⎧30 x1 + 10 x2 + x3 3 3 3 ⎪ ⎪ + x5 , + 10 x4 = 120, ⎨15 x1 + 10 x2 ⎨ x2 = 2 ⎪ x = 980 + 20 x + 10 x . ⎪ x2 − x5 = 2 ; 4 5 ⎩ ⎪ 3 ⎩ ⎛ 20 ⎞ Решение ⎜ ; 2; 980; 0; 0 ⎟ является опорным. Проверим его на оптималь⎝ 3 ⎠ ность. Выразим целевую функцию через свободные переменные, получим 187000 16000 14650 z= − x4 − x5 . (1.35) 3 3 3 Воспользуемся замечанием к алгоритму симплекс-метода. Так как в (1.35) все коэффициенты при свободных переменных отрицательны, то найденное решение является оптимальным. Переменная x1 не является целой, поэтому построим правильное отсечение 2 2 2 ⎧ 20 ⎫ ⎧2⎫ ⎧2⎫ x 4 + x5 ≥ ⎨ ⎬ x 4 + ⎨ ⎬ x5 ≥ ⎨ ⎬ , 3 3 3 ⎩3⎭ ⎩3⎭ ⎩3⎭ 21 и преобразуем его в эквивалентное уравнение, введя новую переменную x6 , получим 2 2 2 x 4 + x5 − x 6 = . (1.35) 3 3 3 Составим расширенную задачу. 20 2 2 ⎧ x x x5 , = − − 1 4 ⎪ 3 3 3 ⎪ + x5 , ⎪ x2 = 2 (1.36) ⎨ 980 20 10 , x x x = + + 4 5 ⎪ 3 ⎪2 2 2 ⎪ x 4 + x5 − x 6 = . 3 3 ⎩3 Решим расширенную задачу (1.36) симплекс-методом. Имеем − x6 , ⎧ x1 = 6 ⎪x = 2 + x5 , ⎪⎪ 2 (1.36) ⎨ x3 = 1000 − 10 x5 + 30 x6 , ⎪ 3 ⎪ x4 = 1 − + x x6 . 5 ⎪⎩ 2 Решение (6; 2;1000;1; 0; 0) является опорным. Проверим его на оптимальность, получим z = 57000 + 4500 x5 − 8000 x6 . (1.37) Так как коэффициент при переменной x5 в (1.37) положителен, то найденное решение не является оптимальным. Введем переменную x5 в состав базисных переменных, получим − x6 , ⎧ x1 = 6 ⎪ 3 ⎪ x2 = 3 − x 4 + x6 , ⎪ 2 (1.37) ⎨ = + + 990 10 15 , x x x 3 4 6 ⎪ ⎪ 3 − x 4 + x6 . ⎪ x5 = 1 ⎩ 2 Проверим решение (6; 3; 990; 0;1; 0 ) на оптимальность. Выразим функцию (1.37) через свободные, получим z = 61500 − 4500 x4 − 1250 x6 . (1.38) Так как все коэффициенты (1.38) отрицательны, то найденное решение является оптимальным. Таким образом, для оптимальной загрузки контейнера требуется взять 6 окон и 3 двери, при этом стоимость перевозимого груза составит 61 500 руб. 22 Алгоритм метода ветвей и границ 1. Найти симплекс-методом оптимальное решение задачи (1.29)-(1.30), отбросив условия целочисленности. 2. Пусть результатом п. 1 служит система ⎧ x1 = β1 + α1,r +1 xr +1 + α1,r + 2 xr + 2 + ... + α1,n xn , ⎪ ⎪ x2 = β 2 + α 2,r +1 xr +1 + α 2,r + 2 xr +1 + ... + α 2,n xn , (1.38) ⎨ .......... .......... .......... .......... .......... .......... ⎪ ⎪ xr = β r + α r ,r +1 xr +1 + α r ,r + 2 xr + 2 + ... + α r ,n xn . ⎩ Если все числа β1 , β 2 , …, β r целые, то найденное решение (β1 , β 2 ,..., β r , 0, 0,..., 0) оптимально. 3. Если задача (1.29)-(1.30) неразрешима без условий целочисленности, то исходная задача неразрешима. 4. Если среди свободных членов β1 , β 2 , …, β r в (1.38) есть хотя бы один нецелый, то выбрать тот, который имеет наибольшую дробную часть. Пусть выбран свободный член β k . Составить две новые задачи (задача 1 и задача 2), добавив в систему ограничений (1.38) дополнительные ограничения xk ≤ [β k ] и xk ≥ [β k ] соответственно. 5. Составленные задачи решить симплекс-методом. Если оптимальное решение составленных задач будет целочисленным, то оптимальным исходной задачи (1.29)-(1.30) является решение той из дополнительных задач, в которой значение целевой наименьшее. В противном случае повторить п. 4-5. Программа в системе Mathcad 2001i Professional 23 24 25 § 6. Транспортная задача Рассмотрим следующую задачу. Пусть в m пунктах A1 , A2 , …, Am находится однородный продукт в количествах a1 , a2 , …, am единиц соответственно, который должен быть доставлен n потребителям B1 , B2 , …, Bn в количествах b1 , b2 , …, bn единиц соответственно. Транспортные расходы, связанные с перевозкой единицы продукта из пункта Ai ( i = 1, m ) в пункт B j ( j = 1, n ), составляют cij . Требуется составить такой план перевозок, который при минимальных транспортных расходах обеспечивает удовлетворение спроса во всех пунктах потребления B j за счет распределения всего продукта, находящегося в пунктах отправки Ai . Для решения поставленной задачи составим транспортную таблицу 1.7. Таблица 1.7 Потребитель Запасы груза Поставщик … B1 B2 Bn … A1 c11 c12 c1n a1 x11 x12 x1n … A2 c21 c22 c2 n a2 x21 x22 x2 n … … … … … … … Am cm1 cm 2 cmn am xm1 xm 2 xmn Потребность b1 b2 bn … в грузе Замечание. В транспортной таблице 1.7 xij количество груза, пе- ревозимого из пункта отправки Ai в пункт потребления B j , причем xij ≥ 0 . 26 Определение 1.7. Матрица C = (cij ) ( i = 1, m , j = 1, n ) называется матрицей тарифов, а сами числа cij – тарифами. Определение 1.8. Планом транспортной задачи называется матрица X = (xij ) ( i = 1, m , j = 1, n ), в которой все элементы неотрица- тельны. Математическая модель транспортной задачи имеет вид: требуется найти неотрицательные значения переменных xij ( i = 1, m , j = 1, n ), обращающих в минимум целевую функцию m n z = ∑∑ cij xij (1.39) i =1 j =1 и удовлетворяющих следующим ограничениям: ⎧n ⎪∑ xij = ai , i = 1, m , ⎪ j =1 ⎪⎪ m (1.40) ⎨∑ xij = b j , j = 1, n , = 1 i ⎪ ⎪ xij ≥ 0 . ⎪ ⎪⎩ Теорема 1.2. Для разрешимости транспортной задачи (1.39)(1.40) необходимо и достаточно, чтобы выполнялось следующее равенство m n i =1 j =1 ∑ ai = ∑ b j . (1.41) Замечание. На практике условие (1.41), как правило, не выполняется, поэтому поступают следующим образом: • если суммарный спрос превышает суммарный запас продукта, т.е. n m j =1 i =1 ∑ b j > ∑ ai , (1.42) то в рассмотрение вводится фиктивный m + 1 пункт отправки Am+1 с запасом продукта n m j =1 i =1 am+1 = ∑ b j − ∑ ai , (1.41) причем тарифы на доставку фиктивным поставщиком равны нулю; • если суммарный запас продукта превышает суммарный спрос, т.е. m n i =1 j =1 ∑ ai > ∑ b j , (1.41) то в рассмотрение водится фиктивный n + 1 пункт потребления Bn+1 со спросом, равным 27 m n i =1 j =1 bn+1 = ∑ ai − ∑ b j , (1.41) при этом тарифы на перевозку равны нулю. Опорный план транспортной задачи Так как система ограничений (1.40) транспортной задачи содержит m + n уравнений и mn неизвестных, то справедлива следующая теорема. Теорема 1.3. Каждый опорный план транспортной задачи (1.39)(1.40) содержит m + n − 1 базисную и mn − (m + n − 1) свободную переменные. Определение 1.9. Клетка соответствующая базисной переменной опорного плана называется загруженной, а – свободной переменной – свободной. Определение 1.9. Циклом в транспортной таблице 1.7 называется набор клеток, в котором две и только две соседние клетки расположены в одной строке или одном столбце и последняя клетка набора лежит в той же строке или столбце, что и первая, при этом ровно одна клетка является свободной. Замечание. Графическим изображением цикла является замкнутая ломаная, звенья которой расположены только в строках и столбцах транспортной таблицы, а все вершины, за исключением одной, расположены в загруженных клетках. Теорема 1.4. План транспортной задачи (1.39)-(1.40) является опорным тогда и только тогда, когда из m + n − 1 занятых им клеток в транспортной таблице 1.7 нельзя образовать ни одного цикла. Алгоритм построения опорного плана методом наименьшего элемента 1. Загрузить в транспортной таблице клетку с наименьшим тарифом. 2. Загрузить клетку той же строки (столбца) со следующим по величине тарифом. 3. Повторить п.2 до тех пор, пока не будут исчерпаны все запасы и удовлетворен весь спрос. 4. Если в результате будут загружена m + n − 1 клетка, то опорный план построен. В противном случае все последующие клетки заполнить нулями, до тех пор, пока количество загруженных клеток будет равно m + n − 1. Одним из наиболее простых способов решения транспортной задачи (1.39)-(1.40) является метод потенциалов. 28 Определение 1.10. Числа ui и v j , соответствующие загружен- ным клеткам транспортной таблицы и удовлетворяющие системе уравнений ui + v j = cij , (1.42) называются потенциалами i -го поставщика и j -го потребителя. Замечание. Система (1.42) имеет m + n неизвестных и m + n − 1 уравнений, поэтому для ее решения один из потенциалов можно считать равным нулю. Определение 1.11. Числа ∆ kp = ckp − (u k + v p ), (1.43) соответствующие свободным клеткам транспортной таблицы, называются оценками свободных клеток. Алгоритм метода потенциалов 1. Условия задачи (1.39)-(1.40) записать в виде транспортной таблицы. 2. Сравнить суммарный запас и суммарный спрос и в случае необходимости ввести фиктивный пункт отправки или потребления. 3. Построить опорный план. 4. Вычислить потенциалы ui и v j поставщиков и потребителей, решив систему (1.42). 5. Вычислить оценки свободных клеток ∆ kp по формулам (1.43). 6. Если все оценки свободных клеток неотрицательны, то найденный план является оптимальным. Если среди оценок свободных клеток ∆ kp есть хотя бы одна отрицательная, то выбрать клетку с наибольшей по модулю оценкой. 7. Построить цикл с началом в выбранной клетке и расставить в вершинах получившейся ломаной знаки «плюс» и «минус» по часовой стрелке, начиная с выбранной клетки. 8. Выбрать загруженные клетки, в которых стоит знак «минус», и найти среди них минимальное значение α . 9. Изменить значения в вершинах цикла на величину α , учитывая знак, стоящий в клетке. 10. Повторить п. 4-9. Замечание. Если в п.5 алгоритма все оценки свободных клеток ∆ kp положительны, то задача имеет единственное решение. Если же среди неотрицательных оценок имеется хотя бы одна нулевая, то задача имеет бесконечно много решений. Пример 1.5. Компания «Жар и холод», занимающаяся производством мороженого, имеет четыре предприятия. Производительность каждого предприятия равна 170, 130, 190 и 200 тыс. шт. ежемесячно. Мороженое отправляется в три города – Смоленск, Москву и Минск, потребление в ко29 торых составляет 150, 270 и 250 тыс. шт. соответственно. Транспортные расходы на перевозку 1 тыс. шт. мороженого с предприятий по городам приведены в таблице 1.8. Таблица 1.8 Города Смоленск Москва Минск Предприятия П1 5 4 6 П2 4 5 9 П3 6 2 5 П4 7 3 5 Найдите план перевозок, минимизирующий транспортные расходы. Решение Составим транспортную таблицу 1.9. Таблица 1.9 Города Смоленск Москва Минск Запасы Предприятия П1 5 4 6 170 П2 4 5 9 130 П3 6 2 5 190 П4 7 3 5 200 Спрос 150 270 250 Найдем суммарный спрос и запасы, получим 150 + 270 + 250 = 670 , 170 + 130 + 190 + 200 = 690 . Так как запасы превышают спрос, то введем фиктивный город Фантом с потреблением 20 тыс. шт. мороженого в месяц, получим таблицу 1.10. Таблица 1.10 Города Смоленск Москва Минск Фантом Запасы Предприятия 4 5 – 6 + П1 170 40 130 5 9 4 П2 130 110 20 5 6 2 П3 190 190 5 7 3 – + П4 200 80 120 Спрос 150 270 250 20 Построим опорный план (см. таблицу 1.10). Найдем потенциалы поставщиков и потребителей. Решив систему уравнений (1.42), получим 30 ⎧u1 = 0, ⎪u = −1, ⎪ 2 ⎪u3 = −2, ⎪ ⎪u 4 = −1, ⎨ ⎪v1 = 5, ⎪v2 = 4, ⎪ ⎪v3 = 6, ⎪v = 1. ⎩ 4 Найдем оценки свободных клеток, используя формулы (1.43), полу⎧u1 + v1 = 5, ⎪u + v = 6, ⎪ 1 3 ⎪u 2 + v1 = 4, ⎪ ⎨u 2 + v4 = 0, ⎪u + v = 3, 2 ⎪ 3 ⎪u 4 + v3 = 5, ⎪ ⎩u1 = 0 ; чим ∆12 = 4 − (0 + 5) = −1, ∆ 31 = 6 − (− 2 + 5) = 3, ∆ 22 = 5 − (− 1 + 4 ) = 2, ∆ 41 = 7 − (− 1 + 5) = 3, ∆14 = 0 − (0 + 1) = −1, ∆ 33 = 5 − (− 2 + 6) = 1, ∆ 23 = 9 − (− 1 + 6 ) = 4, ∆ 44 = 0 − (− 1 + 1) = 0 . Так как среди оценок свободных клеток есть отрицательные, то построенный план не является оптимальным. Построим цикл, соответствующий свободной клетке (1; 2) (см. таблицу 1.10). Найдем минимальное значение среди загруженных клеток, в которых стоит знак «минус», имеем min{80,130} = 80 . Перейдем к новому плану, изменив значения в клетках, соответствующих вершинам цикла, получим транспортную таблицу 1.11. Таблица 1.11 Города Смоленск Москва Минск Фантом Запасы Предприятия 5 4 6 – + 0 170 П1 40 80 50 4 5 9 П2 130 – + 110 20 6 2 5 190 П3 190 7 3 5 200 П4 200 Спрос 150 270 250 20 Найдем потенциалы поставщиков и потребителей. Решив систему (1.42), получим 31 ⎧u1 + v1 = 5, ⎧u1 = 0, ⎪u + v = 4, ⎪u = −1, 2 ⎪ 1 ⎪ 2 ⎪u1 + v3 = 6, ⎪u3 = −2, ⎪ ⎪ ⎪u 2 + v1 = 4, ⎪u 4 = −1, ⎨ ⎨ ⎪u 2 + v4 = 0, ⎪v1 = 5, ⎪u3 + v2 = 2, ⎪v2 = 4, ⎪ ⎪ ⎪u 4 + v3 = 5, ⎪v3 = 6, ⎪u = 0 ; ⎪v = 1. ⎩ 4 ⎩ 1 Найдем оценки свободных клеток. Используя формулы (1.43), полу- чим ∆14 = 0 − (0 + 1) = −1, ∆ 33 = 5 − (− 2 + 6 ) = 1, ∆ 23 = 9 − (− 1 + 6 ) = 4, ∆ 42 = 3 − (− 1 + 4 ) = 0, ∆ 22 = 5 − (− 1 + 4 ) = 2, ∆ 41 = 7 − (− 1 + 5) = 3, ∆ 31 = 6 − (− 2 + 5) = 3, ∆ 44 = 0 − (− 1 + 1) = 0 . Так как среди оценок свободных клеток есть отрицательные, то построенный план не является оптимальным. Построим цикл, соответствующий свободной клетке (1; 4 ) (см. таблицу 1.11). Найдем минимальное значение среди загруженных клеток, в которых стоит знак «минус», имеем min{ 40, 20} = 20 . Перейдем к новому плану, изменив значения в клетках, соответствующих вершинам цикла, получим транспортную таблицу 1.12. Таблица 1.12 Города Смоленск Москва Минск Фантом Запасы Предприятия 4 6 5 П1 170 20 80 50 20 5 9 4 П2 130 130 5 6 2 190 П3 190 5 7 3 200 П4 200 Спрос 150 270 250 20 Найдем потенциалы поставщиков и потребителей. Решив систему (1.42), получим 32 ⎧u1 + v1 = 5, ⎧u1 = 0, ⎪u + v = 4, ⎪u = −1, 2 ⎪ 1 ⎪ 2 ⎪u1 + v3 = 6, ⎪u3 = −2, ⎪ ⎪ ⎪u1 + v4 = 0, ⎪u 4 = −1, ⎨ ⎨ ⎪u 2 + v1 = 4, ⎪v1 = 5, ⎪u3 + v2 = 2, ⎪v2 = 4, ⎪ ⎪ ⎪u 4 + v3 = 5, ⎪v3 = 6, ⎪u = 0 ; ⎪v = 0 . ⎩ 4 ⎩ 1 Найдем оценки свободных клеток. Используя формулы (1.43), получим ∆ 22 = 5 − (− 1 + 4 ) = 2, ∆ 33 = 5 − (− 2 + 6 ) = 1, ∆ 23 = 9 − (− 1 + 6 ) = 4, ∆ 41 = 7 − (− 1 + 5) = 3, ∆ 24 = 0 − (− 1 + 0 ) = 1 ∆ 42 = 3 − (− 1 + 4 ) = 0, ∆ 31 = 6 − (− 2 + 5) = 3, ∆ 44 = 0 − (− 1 + 0 ) = 1. Так как все оценки свободных клеток неотрицательны, то найденный план является оптимальным. Таким образом, план перевозок имеет вид ⎛ 20 80 50 ⎞ ⎜ ⎟ 130 ⎜ ⎟ X =⎜ , 0 190 0 ⎟ ⎜⎜ ⎟⎟ 200 ⎝ ⎠ при этом минимальные затраты на транспортировку мороженого составят z = 2620 единиц. Замечание. Так как оценка свободной клетки ∆ 42 = 0 , то задача имеет бесконечно много решений. Программа в системе Mathcad 2001i Professional 33 34 § 7. Дробно-линейное программирование Часто на практике наряду с получением максимальной прибыли требуется оценить и другие экономические показатели, характеризующие эффективность работы предприятия. Например, предприятие производит кирпич трех видов – силикатный, красный и облицовочный. Себестоимость производства тысячи штук кирпича каждого вида равна 5, 4 и 3 тыс. руб. соответственно, а отпускные цены составляют 7, 6 и 4 тыс. руб. Тогда если x1 , x2 и x3 тыс. штук – планируемое к производству количество кир7 x + 6 x2 + 4 x3 задает рентабельность пича каждого вида, то функция z = 1 5 x1 + 4 x2 + 3 x3 работы предприятия. Определение 1.12. Функция вида n z= p0 + ∑ p j x j j =1 n q0 + ∑ q j x j (1.44) j =1 называется дробно-линейной функцией аргументов x1 , x2 , …, xn . Рассмотрим задачу дробно-линейного программирования: требуется найти значения переменных x1 , x2 , …, xn , удовлетворяющих системе линейных ограничений вида: ⎧n ⎪∑ aij x j = bi , i = 1, m (1.45) ⎨ j =1 ⎪ x ≥ 0, j = 1, n , ⎩ j где aij , bi – заданные числа, и обращающих в минимум дробно-линейную функцию (1.44). Для решения задачи (1.44)-(1.45) введем новые переменные y0 , y1 , …, y n по формулам: 35 y0 = 1 n q0 + ∑ q j x j , y j = y0 ⋅ x j , j = 1, n . (1.46) j =1 Замечание. Часто из экономических соображений вытекает, что величина y0 положительна. Далее, умножив обе части уравнений в системе ограничений (1.45) на y0 > 0 и учитывая формулы (1.46), получим следующую основную задачу линейного программирования: требуется найти значения переменных y0 , y1 , …, yn , удовлетворяющих системе ограничений вида: ⎧n ⎪∑ aij y j − bi y0 = 0, i = 1, m , ⎪ j =1 ⎪⎪ n ⎨∑ q j y j = 1, ⎪ j =0 ⎪ y , y ≥ 0 , j = 1, n , ⎪ 0 j ⎪⎩ и обращающих в минимум функцию n z = ∑ pjyj . (1.47) (1.48) j =0 Алгоритм решения задачи дробно-линейного программирования 1. Ввести новые переменные y0 , y1 , …, y n по формулам (1.46) и получить задачу (1.47)-(1.48). 2. Симплекс-методом найти оптимальное решение задачи (1.47)-(1.48). 3. Найти значение переменных x1 , x2 , …, xn , используя формулы yj xj = . (1.49) y0 Пример 1.6. Завод по производству соков «Сады Смоленщины» изготавливает два вида соков из трех видов фруктов (яблоки, апельсины, персики). Соки поставляются в торговую сеть в пакетах по 2 л и 1,5 л. Все данные о производстве и реализации представлены в таблице 1.13. Таблица 1.13 Расход фруктов (в кг) для сока Фрукты Запас, кг 2л 1,5 л Яблоки 650 1 0,5 Персики 245 0,3 0,25 Апельсины 800 0,75 1 Прибыль, получаемая от реализации 13 5 одного пакета (руб.) 36 Составьте план производства сока, для которого рентабельность будет наибольшей, если известно, что затраты на двухлитровый пакет составляют 5 руб., на полуторалитровый – 2 руб. Решение Пусть x1 , x2 – планируемое к производству количество двухлитровых и полуторалитровых пакетов сока соответственно. Тогда получим следующую математическую модель задачи. Требуется найти значения переменных x1 и x2 , удовлетворяющих системе ограничений вида: ⎧ x1 + 0,5 x2 ≤ 650, ⎪0,3 x + 0,25 x ≤ 245, ⎪ 1 2 (1.50) ⎨ x x + ≤ , 75 800 , 1 2 ⎪ ⎪⎩ x1 , x2 ≥ 0, и обращающих в максимум функцию 13 x1 + 5 x2 z= . (1.51) 5 x1 + 2 x2 Введем фиктивные переменные x3 , x4 и x5 , тогда система ограничений (1.50) примет вид: = 650, ⎧ x1 + 0,5 x2 + x3 ⎪ 0,3 x + 0,25 x + x4 = 245, 1 2 ⎪ (1.52) ⎨0,75 x + x2 + x5 = 800, 1 ⎪ ⎪ x j ≥ 0, j = 1, 5. ⎩ 1 , тогда с учетом формул (1.46) получим сле5 x1 + 2 x2 дующую задачу линейного программирования: Пусть y0 = z = 13 y1 + 5 y 2 , (1.52) ⎧ − 650 y0 = 0, y1 + 0,5 y 2 + y3 ⎪ + y4 − 245 y0 = 0, ⎪ 0,3 y1 + 0,25 y 2 ⎪ + y2 + y5 − 800 y0 = 0, ⎨0,75 y1 ⎪ 5y + 2 y2 = 1, 1 ⎪ ⎪ y0 > 0, y j ≥ 0, j = 1, 5. ⎩ (1.53) Решив задачу (1.52)-(1.53) симплекс-методом, получим 37 1 1 1 ⎧ y y y3 , = + + 2 ⎪ 3250 6500 650 ⎪ ⎪y = 1 − 2 y , ⎪ 1 5 5 2 (1.54) ⎨ 1 6 49 ⎪y = y + y , − ⎪ 4 65 65 2 130 3 ⎪ 5 15 16 ⎪ y5 = y 2 + y3 , − 52 26 13 ⎩ 13 1 z = − y2 . (1.55) 5 5 Таким образом, используя формулы (1.49), найдем значения переменных x1 , x2 и наибольшее значение целевой функции (1.51). Имеем 13 x1 = 650 , x2 = 0 , z = . 5 Значит, рентабельность завода «Сады Смоленщины» будет наибольшей, если предприятие сделает ставку на производство соков только в двухлитровых пакетах. Программа в системе Mathcad 2001i Professional 38 § 8. Многокритериальные задачи Экономическая эффективность производства обычно количественно измеряется системой экономических показателей (чистый доход, прибыль, рентабельность, валовой доход на единицу сопоставимых по качеству товаров и т.п.). При этом максимальное значение одного из показателей во39 все не означает, что одно предприятие работает лучше другого. В этом случае охарактеризовать эффективность всего производства может только система таких показателей. Определение 1.13. Задачи, решаемые с учетом множества (системы) показателей, называют многокритериальными задачами. Замечание. Отметим, что оптимальные планы задач, получаемые при оптимизации по разным показателям, вообще говоря, будут отличаться друг от друга. Поэтому при решении многокритериальных задач требуется построить план, при котором система показателей была бы наилучшей (компромиссной). Выделяют несколько способов построения таких компромиссных планов: • Метод уступок. Применяется в том случае, когда показатели оптимизации не являются равнозначными. • Метод равных и наименьших отклонений. Применяется, когда все критерии равнозначны и в компромиссном плане относительные отклонения всех критериев от своих оптимальных значений должны быть равны и минимальны. Алгоритм метода уступок 1. Расположить критерии z1 , z 2 , …, z p по их значимости, считая наиболее важным первый критерий. 2. Решить задачу по первому критерию, т.е. отыскать оптимальное значение целевой функции z1 , равное z1* . 3. Сделать уступку по первому критерию, т.е. изменить значение z1 до значения k1 z1* , где 0 < k1 < 1 . 4. Ввести в систему ограничений дополнительное ограничение z1 ≥ k1 z1* , если критерий максимизировался, и z1 ≤ k1 z1* в противном случае. 5. Решить задачу по второму критерию z 2 , т.е. найти оптимальное зна6. 7. 8. 9. чение z 2* целевой функции z 2 . Обратиться к п. 3 алгоритма и сделать уступку для второго критерия k 2 z 2* , 0 < k 2 < 1 . Обратиться к п. 4 алгоритма и ввести в систему ограничений дополнительное неравенство z 2 ≥ k 2 z 2* или z 2 ≤ k 2 z 2* . Решить новую задачу с двумя дополнительными ограничениями по третьему критерию z3 и т.д. Процесс решения закончить тогда, когда получено решение по всем критериям. 40 Пример 1.7. Предприятие «Ай, да валенки мои!» изготавливает валенки для девочек и мальчиков, располагая при этом производственными мощностями четырех видов в следующих количествах: первого вида – не менее 12, а остальных – не более 10, 6, 7. Нормы затрат мощностей каждого вида на одну тыс. пар валенок для девочек составляет соответственно 3, 1, 1 и 0, на одну тыс. пар валенок для мальчиков – 4, 1, 0 и 1. Прибыль от сбыта, чистый доход и затраты на одну тыс. пар валенок для девочек и мальчиков составляют 300000 руб. и 500000 руб., 300000 руб. и 100000 руб., 200000 руб. и 100000 руб. соответственно. Найдите компромиссный план производства валенок обоих видов, считая наиболее предпочтительным критерием прибыль с отклонением от максимального значения на 20%, чистый доход с отклонением 40% и менее важным – критерий затрат. Решение Пусть x1 , x2 тыс. штук – планируемое к производству количество пар валенок для девочек и мальчиков соответственно. Тогда получим следующую математическую модель задачи. Требуется найти неотрицательные значения переменных x1 и x2 , удовлетворяющих системе ограничений ⎧3 x1 + 4 x2 ≥ 12, ⎪ x + x ≤ 10, ⎪ 1 2 (1.56) ⎨ ≤ x 6 , ⎪ 1 ⎪⎩ x2 ≤ 7 и обращающих в максимум функции (1.57) z1 = 300 x1 + 500 x2 , z 2 = 300 x1 + 100 x2 (1.58) с отклонением от экстремальных значений на 20% и 40% соответственно и – в минимум функцию z3 = 200 x1 + 100 x2 . (1.59) Решим задачу (1.56-1.59) по алгоритму метода уступок. Введем фиктивные неотрицательные переменные x3 , x4 , x5 и x6 , тогда система ограничений (1.56) примет вид: = 12, ⎧3 x1 + 4 x2 − x3 ⎪x + x + x4 = 10, ⎪ 1 2 (1.60) ⎨ x x 6 , + = 1 5 ⎪ ⎪⎩ x2 + x 6 = 7. Решив задачу (1.57)-(1.60) симплекс-методом, получим ⎧ x1 = 3 − x4 + x6 , ⎪x = 7 − x6 , ⎪ 2 (1.61) ⎨ x 25 3 x x , = − − 4 6 ⎪ 3 ⎪⎩ x5 = 3 + x4 − x6 , z1 = 4400 − 300 x4 − 200 x6 . (1.62) 41 Сделаем уступку по первому критерию. Введем дополнительное ограничение 300 x1 + 500 x2 ≥ 0,8 ⋅ 4400 в систему (1.61), добавив фиктивную переменную x7 , получим ⎧ x1 = 3 − x4 + x6 , ⎪x = 7 − x6 , ⎪⎪ 2 (1.62) ⎨ x3 = 25 − 3 x4 − x6 , ⎪x = 3 + x − x , 4 6 ⎪ 5 ⎪⎩300 x1 + 500 x2 − x7 = 3520. Решив задачу (1.58)-(1.62), получим − x5 , ⎧ x1 = 6 ⎪x = 4 − x4 + x5 , ⎪⎪ 2 − 4 x4 + x5 , (1.63) ⎨ x3 = 22 ⎪x = 3 + x4 − x5 , ⎪ 6 ⎪⎩ x7 = 280 − 500 x4 + 200 x5 , z 2 = 2200 − 100 x4 − 200 x5 . (1.63) Сделав уступку по второму критерию и введя ограничение 300 x1 + 100 x2 − x8 = 0,6 ⋅ 2200 в (1.63), получим − x5 , ⎧ x1 = 6 ⎪x = 4 − x4 + x5 , ⎪ 2 ⎪⎪ x3 = 22 − 4 x4 + x5 , (1.64) ⎨ = 3 + − , x x x 4 5 ⎪ 6 ⎪ x7 = 280 − 500 x4 + 200 x5 , ⎪ ⎪⎩300 x1 + 100 x2 − x8 = 1320. Решив задачу (1.59)-(1.64), получим 77 1 1 ⎧ = − + x x x8 , 1 7 ⎪ 30 1200 240 ⎪ ⎪ x = 11 + 1 x − 1 x , 7 8 ⎪ 2 2 400 400 ⎪ 177 3 1 ⎪ x3 = + x7 + x8 , ⎪ 10 400 400 ⎨ ⎪ x = 29 − 1 x − 1 x , 7 8 ⎪ 4 15 600 600 ⎪ 103 1 1 ⎪ x5 = + x7 − x8 , 30 1200 240 ⎪ ⎪ 3 1 1 − x7 + x8 , ⎪ x6 = 2 400 400 ⎩ 42 (1.64) 3190 1 7 + x7 + x8 . (1.64) 3 12 12 Таким образом, предприятию «Ай, да валенки мои!» следует планировать к производству 2567 пар валенок для девочек и 5500 пар – для мальчиков, при этом прибыль составит 3,52 млн. руб., чистый доход – 1,32 млн. руб., а затраты – 1,063 млн. руб. z3 = Программа в системе Mathcad 2001i Professional 43 44 45 Метод равных и наименьших отклонений При решении задач линейного программирования методом уступок, вообще говоря, мы имеем различные отклонения критериев от их экстремальных значений. Потребуем, чтобы в компромиссном плане относительные отклонения всех критериев от своих экстремальных значений были равны и минимальны. Кроме того, будем предполагать, что в области допустимых решений задачи не существует плана, оптимизирующего все критерии. Пусть z1 , z 2 , …, z p – критерии оптимизации, а z1* , z 2* , …, z *p – их оптимальные значения. Тогда условие равенства относительных отклонений примет вид z p − z *p z1 − z1* z 2 − z 2* = ... = = . (1.65) z1* z 2* z *p Рассмотрим два произвольных фиксированных критерия z s и zt . Возможны случаи. 1. Оба критерия одного смысла. Тогда равенство относительных отклонений можно записать в виде: z s zt (1.66) − = 0. z s* zt* 2. Критерии разного смысла. Тогда равенство отклонений примет вид: z s zt + = 2. (1.67) z s* zt* Так как все относительные отклонения одинаковы, то для минимизации достаточно взять любое из относительных отклонений. n Пусть целевые функции исходной задачи имеют вид: z k = ∑ ckj x j j =1 ( k = 1, p ). 46 Определение 1.13. Если к системе ограничений исходной задачи добавить ограничения вида (1.66), (1.67) и n ∑ ckj x j − z k = 0 , k = 1, p , где j =1 критерии исходной задачи включены в состав неизвестных, а в качестве целевой функции взята одна из целевых функций z k , то вновь полученная задача называется замещающей. Алгоритм метода равных и наименьших отклонений 1. Решить задачу отдельно по каждому критерию, т.е. найти экстремальные значения каждого из них. 2. Составить замещающую задачу. 3. Найти решение замещающей задачи. Пример 1.8. Решить задачу из примера 1.7, считая, что все критерии равнозначны. Решение Математическая модель задачи. Требуется найти неотрицательные значения переменных x1 и x2 , удовлетворяющих системе ограничений ⎧3 x1 + 4 x2 ≥ 12, ⎪ x + x ≤ 10, ⎪ 1 2 (1.68) ⎨ ≤ 6 , x 1 ⎪ ⎪⎩ x2 ≤ 7 и обращающих в максимум функции z1 = 300 x1 + 500 x2 , (1.69) z 2 = 300 x1 + 100 x2 (1.70) и в минимум функцию z3 = 200 x1 + 100 x2 . (1.71) Решим задачу, используя алгоритм метода равных и наименьших отклонений. Найдем экстремальные значения функций (1.69)-(1.71), удовлетворяющих системе ограничений (1.68), получим z1* = 4400 , z 2* = 2200 и z3* = 300 . Составим замещающую задачу: требуется найти неотрицательные значения переменных x1 , x2 , …, x6 , z1 , z 2 , z3 , удовлетворяющих системе ограничений 47 ⎧ ⎪ ⎪3 x + 4 x − x = 12, 2 3 ⎪ 1 ⎪ x1 + x2 + x4 = 10, ⎪ x + x = 6, 5 ⎪ 1 ⎪ x 2 + x 6 = 7, ⎪ (1.72) ⎨300 x1 + 500 x2 − z1 = 0, ⎪300 x + 100 x − z = 0, 1 2 2 ⎪ ⎪200 x1 + 100 x2 − z3 = 0, ⎪ ⎪ z1 − z 2 = 0, ⎪ 4400 2200 ⎪ z z ⎪ 1 + 3 =2 ⎩ 4400 500 и обращающих в минимум функцию z = 200 x1 + 100 x2 . (1.73) Решая задачу (1.72)-(1.73) симплекс-методом, получим 11 ⎧ = , x 1 ⎪ 430 ⎪ ⎪ x = 11 , ⎪ 2 430 ⎪ 5083 ⎪ x3 = − , 430 ⎪ ⎪ 2139 , ⎪ x4 = 215 ⎪ ⎪ 2569 , ⎨ x5 = 430 ⎪ 2999 ⎪ , = x 6 ⎪ 430 ⎪ ⎪ z = 880 , ⎪ 1 43 ⎪ ⎪ z 2 = 440 , 43 ⎪ (1.74) ⎪ 330 . ⎪ z3 = 43 ⎩ Таким образом, исходная задача решений не имеет. Замечание. Рассмотренные примеры 1.7 и 1.8 показывают, что решения многокритериальных задач в различных постановках будут различны. А постановки некоторых задач могут являться некорректными. 48 Программа в системе Mathcad 2001i Professional 49 50 51 Задачи и упражнения 1. Решите симплекс-методом задачи: ⎧ x1 + 4 x2 − x3 + x4 = 16, ⎪ ⎨4 x1 − 6 x2 + 3 x3 − 7 x4 = 20, а) ⎪ ⎩ x j ≥ 0, j = 1, 4, z = 8 x1 − 6 x2 − 5 x3 + 2 x4 → max ; ⎧ x1 + x4 + 6 x6 = 9, ⎪3 x + x − 4 x + 2 x = 2, 2 3 6 ⎪ 1 ⎨ x + 2 x + x + 2 x = 6, б) ⎪ 1 2 5 6 ⎪ x j ≥ 0, j = 1, 6, ⎩ z = x1 − x2 + x3 + x4 + x5 − x6 → max . 52 2. Мебельная фабрика выпускает шкафы-купе, стенки и спальные гарнитуры. Суточный плановый выпуск соответственно равен 90, 70 и 60 штук. Суточные ресурсы фабрики составляют 800 единиц производственного оборудования, 910 единиц сырья и 790 единиц электроэнергии. Расход ресурсов на единицу продукции приведен в таблице. Расход ресурсов на одно изделие Ресурсы Шкаф-купе Стенка Спальный гарнитур Оборудование 2 3 4 Сырье 1 4 5 Электроэнергия 2 3 4 Стоимость одного шкафа – 11 у.е., стенки – 17 у.е. и спального гарнитура – 25 у.е. Сколько необходимо производить изделий каждого вида, чтобы стоимость продукции, выпущенной сверх плана, была максимальной? 3. Стеклянное полотно длиной 200 см необходимо разрезать на заготовки трех типов А, Б и В длиной соответственно 57, 82 и 101 см для производства 50 витражей. На каждый витраж требуется 4 заготовки типов А и Б и 5 заготовок типа В. Определите, какое количество стеклянных полотен нужно разрезать, чтобы отходы от раскроя были минимальными. 4. Пшеница и кукуруза высаживаются на участках различного плодородия площадью 100 и 200 га. Данные об урожайности приведены в таблице. Урожайность (ц/га) участка Культура I II Пшеница 20 15 Кукуруза 35 30 По плану должно быть собрано не менее 1500 ц пшеницы и 4500 ц кукурузы. Цена 1 ц пшеницы равна 6 у.е., кукурузы – 4 у.е. Найдите оптимальное сочетание посевов пшеницы и кукурузы, которое обеспечивает максимальную выручку от продажи. 5. На приобретение нового оборудования для проведения параллельных вычислений выделено 20000 у.е. Оборудование должно быть размещено на площадь 72 м2. Вычислительная лаборатория может заказать оборудование двух видов: более мощные компьютеры типа А стоимостью 5000 у.е., требующие для установки 3 м2 площади (с учетом проходов) и выполняющие 800 млн. операций в секунду, и менее мощные компьютеры типа Б стоимостью 2000 у.е., занимающие площадь 6 м2 и выполняющие 200 млн. операций в секунду. Можно заказать не более трех компьютеров типа А. Найдите оптимальный вариант приобретения компьютеров, обеспечивающий максимальную производительность вычислений. 53 6. На приобретение оборудования для нового производственного участка мебельной фабрики выделена 21 000 у.е. Оборудование должно быть размещено на площади, не превышающей 37 м2. Предприятие может заказать оборудование двух видов: более мощные станки типа А стоимостью 3 000 у.е., требующие площадь в 6 м2 (с учетом проходов) и обеспечивающие производительность 7 000 заготовок за смену, и менее мощные станки типа Б стоимостью 2 000 у.е., занимающие площадь 3 м2 и дающие за смену 4 000 заготовок. Найдите оптимальный вариант приобретения оборудования, обеспечивающий новому участку максимальную производительность. 7. Решите транспортную задачу, исходные данные которой приведены в таблице. Пункты В1 В2 В3 В4 Запасы 100 А1 1 2 3 1 200 А2 2 3 4 6 300 А3 3 4 7 12 Потребности 100 100 300 300 8. В резерве трех железнодорожных станций А, Б и В находится соответственно 60, 80 и 70 вагонов. Составьте оптимальный план перегона этих вагонов к четырем пунктам погрузки зерна, если пункту №1 требуется 40 вагонов, пункту №2 – 60, пункту №3 – 80, а пункту №4 – 60 вагонов. При этом следует учесть, что в пунктах №2 и №3 нет условий для длительного хранения зерна, а поэтому его необходимо вывезти из этих пунктов полностью. Стоимость перегона одного вагона со станции А в указанные пункты равна соответственно 11, 12, 15 и 14 у.е., со станции Б – 14, 13, 12 и 11 у.е., со станции В – 15, 12, 14 и 16 у.е. 9. В организации объявлен конкурс на замещение должности курьера, оператора ЭВМ и секретаря-референта. На эти должности претендуют три человека: А, Б и В. После проведения тестирования ими были получены баллы (способность к данной профессии), представленные в таблице. СекретарьКурьер Оператор ЭВМ референт А 5 4 7 Б 6 7 3 В 8 11 2 Как должен поступить начальник отдела кадров, чтобы принятые на работу претенденты принесли наибольшую пользу компании? 10. Банки «Внешэкономбанк», «Русский стандарт», «Сбербанк РФ» и «Юниаструм» выделяют кредиты четырем предприятиям. Суммы, которые банки могут выделить на кредиты, потребность предприятий в кредитах и процентные ставки в расчете на 100 у.е. приведены в таблице. 54 Банк «Внешэкономбанк» «Русский стандарт» «Сбербанк РФ» «Юниаструм» Потребности в кредитах А1 1 2 3 4 А2 2 3 4 5 А3 3 4 7 6 А4 1 6 12 8 200 200 250 350 Кредиты 250 200 400 150 Найдите оптимальное распределение кредитов между предприятиями, максимизирующее общую прибыль, которую могут получить банки за пользование взятыми предприятиями кредитами. 11. Найдите неотрицательные значения переменных x1 , x2 , удовлетворяющих системе ограничений ⎧3 x1 + 2 x2 ≥ 9, ⎪2 x − 3 x ≤ 8, ⎪ 1 2 ⎨ ⎪− x1 + x2 ≤ 2, ⎪⎩ x2 ≤ 5, обращающих в максимум функцию z1 = x1 + x2 с отклонением от экстремального значения на 40%, и в минимум функцию z 2 = x1 + 3x2 . Составьте задачу, соответствующую приведенной математической модели. 12. Найдите неотрицательные значения переменных x1 , x2 , удовлетворяющих системе ограничений ⎧ x1 + 2 x2 ≥ 6, ⎪ ⎨ x1 ≤ 4, ⎪ x ≤ 5, ⎩ 2 обращающих в максимум функцию z1 = x1 + 2x2 , и – в минимум функцию z 2 = x1 + x2 . Составьте задачу, соответствующую приведенной математической модели. 55 Глава 2. Элементы теории игр § 1. Основные понятия теории игр Определение 2.1. Игрой называют упрощенную модель конфликтной ситуации, которая предполагает наличие следующих компонент: заинтересованных сторон, возможных действий каждой стороны и интересов сторон. В игре заинтересованные стороны называются игроками, причем каждый из них может предпринимать не менее двух действий. Игра ведется по определенным правилам. Суть игры состоит в том, что каждый из ее участников принимает такие решения, которые как он предполагает, могут обеспечить ему наилучший результат. Например, при игре в прятки некоторые из игроков предпочитают прятаться далеко от водящего, а другие – непосредственно за его спиной. Для игр характерна неопределенность результата. Причины неопределенности обычно относятся к следующим трем группам: • комбинаторные источники (например, шахматы); • случайные факторы (например, карточные игры); • стратегическое происхождение неопределенности (игрок не знает, какого образа действий придерживается его противник). Замечание. В качестве игрока может выступать как отдельное лицо, так и группа лиц, объединенных общностью цели. Каждый игрок в ходе игры выбирает образ своих действий самостоятельно, имея лишь общее представление о множестве допустимых ответных решений соперников, т.е. ни один из игроков не может полностью контролировать положение. Определение 2.2. Исходом игры называется значение некоторой функции, называемой функцией выигрыша. Определение 2.3. Если сумма выигрышей игроков равна нулю, то игру называют игрой с нулевой суммой. Определение 2.4. Игры, в которых участники действуют в строгом соответствии с правилами, в равной мере сознательно стремятся добиться наилучшего для себя результата, называются стратегическими. Определение 2.5. Если в игре участвуют два игрока, имеющих противоположные интересы, то игру называют парной. Определение. 2.6. Стратегией игрока называется совокупность принципов, определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от сложившейся ситуации. При этом вариант действий называется чистой стратегией. 56 Определение 2.7. Если количество чистых стратегий игроков конечно, то игра называется конечной, в противном случае – бесконечной. В экономике модель поведения лиц в виде игры возникает, например, при попытке нескольких фирм завоевать наиболее выгодное место на конкурентном рынке, или, например, при желании нескольких компаний разделить некоторые ресурсы между собой так, чтобы каждому досталось как можно больше. Игроками в конфликтных экономических ситуациях являются фирмы, банки, отдельные лица и другие экономические агенты. Ниже будет рассмотрена модель парной конечной стратегической игры с нулевой суммой. Пусть игроки A и B располагают конечным числом чистых стратегий A1 , A2 , …, Am и B1 , B2 , …, Bn соответственно. Игрок A может выбирать любую свою чистую стратегию Ai ( i = 1, m ), в ответ на которую игрок B может выбирать любую свою чистую стратегию B j ( j = 1, n ). Так как игра состоит только из личных ходов игро- ков, то выбор пары чистых стратегий (Ai , B j ) однозначно определяет ре- зультат aij – выигрыш игрока A . При этом в силу того, что игра является игрой с нулевой суммой, проигрыш игрока B составляет − aij . Если известны значения aij выигрыша для каждой пары чистых стратегий (Ai , B j ) , то можно составить матрицу выигрышей игрока A вида ⎛ a11 a12 ... a1n ⎞ ⎜ ⎟ ⎜ a21 a22 ... a2 n ⎟ P=⎜ . (2.1) ... ... ... ... ⎟ ⎜⎜ ⎟⎟ a a a ... m2 mn ⎠ ⎝ m1 Определение 2.8. Матрица (2.1) называется платежной матрицей игры. Пусть α i = min aij ( i = 1, m ), тогда α i минимальный возможный вы1≤ j ≤ n игрыш игрока A при применении им чистой стратегии Ai . Аналогично, β j = max aij ( j = 1, n ) – максимально возможный проигрыш игрока B в 1≤ i ≤ m случае применения им чистой стратегии B j . Определение 2.9. Число α = max α i = max min aij называется 1≤ i ≤m 1≤ i ≤ m 1≤ j ≤ n чистой нижней ценой игры (максимином), а соответствующая ему чистая стратегия игрока A называется максиминной. Замечание. Число α показывает, какой минимальный гарантированный выигрыш может получить игрок A , правильно применяя свои чистые стратегии при любых действиях игрока B . 57 Определение 2.10. Число β = min β j = min max aij называется 1≤ j ≤n 1≤ j ≤n 1≤ i ≤ m чистой верхней ценой игры (минимаксом), а соответствующая ему чистая стратегия игрока B называется минимаксной. Замечание. Число β показывает, какой максимальный проигрыш может быть у игрока B при правильном выборе им своих чистых стратегий независимо от действий игрока A . Таким образом, правильно применяя свои чистые стратегии, игрок A обеспечит себе выигрыш не менее α , а игрок B – проигрыш не более β , причем α ≤ β . Определение 2.11. Если α = β , то говорят, что игра имеет седловую точку в чистых стратегиях и чистую цену игры v = α = β . Определение 2.12. Пару чистых стратегий (Ai , B j ) , соответст- вующих α и β , называют седловой точкой игры, а элемент aij – седловым элементом платежной матрицы. Замечание. Стратегии Ai и B j , образующие седловую точку, являются оптимальными для каждого из участников игры. Определение 2.13. Если игра имеет седловую точку, то упорядоченную тройку (Ai , B j , v ) называют решением игры. Определение 2.14. Если в платежной матрице (2.1) элементы k -й строки не меньше соответствующих им элементов s -й строки, то говорят, что чистая стратегия Ak доминирует над чистой стратегией As . Замечание. Если чистая стратегия Ak доминирует над чистой стратегией As , то игроку A невыгодно использовать свою чистую стратегию As . Поэтому из платежной матрицы можно исключить строку с номером s , что приведет к уменьшению размерности платежной матрицы, т.е. упростит решение игры. Аналогично определяется доминирование чистых стратегий для игрока B . Определение 2.15. Если в платежной матрице элементы k -го столбца не больше соответствующих им элементов s -го столбца, то говорят, что чистая стратегия Bk доминирует над чистой стратегией Bs . Замечание. Как и в случае игрока A , если чистая стратегия Bk доминирует над чистой стратегией Bs , то игроку B невыгодно применять свою чистую стратегию Bs . Поэтому из платежной матрицы можно исключить столбец с номером s . 58 Пример 2.1 (Дилемма заключенного). Двое подозреваемых арестованы после беспрецедентного ограбления банка, названного ограблением тысячелетия, и содержатся в разных камерах. Чтобы заставить их признаться в ограблении, полицейские делают им предложение: если ни один из них не заговорит, обоим дадут по одному году тюрьмы за наличие других мелких провинностей; если один выдаст другого, а другой не заговорит, тот, кто выдал, будет освобожден, а тому, кто не признался, дадут пятьдесят лет; если оба выдадут друг друга, оба получат по десять лет тюремного заключения. Каждый знает, что другому сделали такое же предложение. Как должны поступить подозреваемые? Решение Составим платежную матрицу игры, получим таблицу 2.1. Таблица 2.1 Поведение второго подозреваемого Поведение первого αi подозреваемого Говорить Молчать Говорить -10 -10 Молчать -50 -1 -50 βj -10 Замечание. Элементы платежной матрицы отрицательны, так как подозреваемые стремятся уменьшить срок заключения. Найдем нижнюю и верхнюю цену игры, получим α = max α i = −10 , 1≤ i ≤ 2 β = min β j = −10 . Таким образом, игра имеет седловую точку. 1≤ j ≤ 2 Упростим платежную матрицу игры. Стратегия «Говорить» первого подозреваемого доминирует над его стратегией «Молчать», поэтому вычеркнем вторую строку в платежной матрице, получим таблицу 2.2. Таблица 2.2 Поведение первого Поведение второго подозреваемого αi подозреваемого Говорить Молчать Говорить -10 -10 βj -10 Для второго подозреваемого в платежной матрице, представленной в таблице 2.2, стратегия «Говорить» доминирует над его стратегией «Молчать», поэтому вычеркнем второй столбец, получим таблицу 2.3. Таблица 2.3 Поведение первого Поведение второго подозреваемого αi подозреваемого Говорить Говорить -10 -10 βj -10 Таким образом, каждому из подозреваемых наиболее выгодно дать показание на своего сообщника и получить десять лет тюремного заключения. 59 § 2. Решение игр методами линейного программирования Предположим, что игра не имеет седловой точки, т.е. нижняя и верхняя цена игры не совпадают. Определение 2.16. Смешанной стратегией игрока A называется вектор p = ( p1 , p2 , ..., pm ) , координаты которого удовлетворяют условиям pi ≥ 0 ( i = 1, m ) и m ∑ pi = 1 , где i =1 pi – вероятность, с которой игрок A вы- бирает чистую стратегию Ai . Определение 2.17. Смешанной стратегией игрока B называется вектор q = (q1 , q2 , ..., qn ) , координаты которого удовлетворяют условиям q j ≥ 0 , ( j = 1, n ) и n ∑ q j = 1 , где j =1 q j – вероятности, с которыми игрок B выбирает стратегию B j . Замечание. Здесь под вероятностью понимается частота, с которой игроки применяют ту или иную свою чистую стратегию. При использовании смешанных стратегий игра приобретает случайный характер, случайной становится и величина выигрыша игроков. Определение 2.18. Функция m n z ( p, q ) = ∑∑ aij pi q j (2.2) i =1 j =1 называется платежной. Определение 2.18. Смешанные стратегии p и q называют оптимальными, если они образуют седловую точку для платежной функции (2.2), т.е. если они удовлетворяют условию max min z ( p, q ) = min max z ( p, q ) = v . (2.3) p q q p При этом величину v называют ценой игры. Математическая модель игры в смешанных стратегиях Предположим, что платежная матрица игру упрощена. Составим следующую таблицу 2.4, соответствующую платежной матрице Таблица 2.4 B1 (q1 ) B2 (q2 ) Bn (qn ) αi … A1 ( p1 ) a11 a12 a1n α1 … A2 ( p2 ) a21 a22 a2 n α2 … … … … … … … Am ( pm ) am1 am 2 amn αm … βj β1 β2 βn … 60 Пусть p = ( p1 , p2 , ..., pm ) – смешанная стратегия игрока A , v – цена игры, тогда для решения игры в смешанных стратегиях требуется найти неотрицательные значения переменных p1 , p2 , …, pm , удовлетворяющих системе ограничений ⎧ ⎪a p + a p + ... + a p ≥ v, m1 m 21 2 ⎪ 11 1 ⎪a12 p1 + a22 p2 + ... + am 2 pm ≥ v, ⎪ (2.4) ⎨.............................................. ⎪a p + a p + ... + a p ≥ v, mn m 2n 2 ⎪ 1n 1 m ⎪ ⎪∑ pi = 1, ⎩ i =1 и обращающих в максимум функцию z = v. (2.5) Замечание. Вообще говоря, в системе (2.4) v является неизвестной, удовлетворяющей условию α ≤ v ≤ β , причем произвольного знака. Если среди элементов платежной матрицы есть хотя бы один отрицательный, то, увеличив все элементы платежной матрицы на наибольший по модулю отрицательный элемент a , получим матрицу, все элементы которой неотрицательны. Поэтому в системе ограничений (2.4) можно считать величину v неотрицательной. При этом оптимальным значением функции (2.5) будет являться величина z − a . Аналогично, если q = (q1 , q2 , ..., qn ) – смешанная стратегия игрока B , а v – цена игры, то для решения игры требуется найти неотрицательные значения переменных q1 , q2 , …, qn , удовлетворяющих системе ограничений ⎧ ⎪ ⎪a11q1 + a12 q2 + ... + a1n qn ≤ v, ⎪a21q1 + a22 q2 + ... + a2 n qn ≤ v, ⎪ (2.6) ⎨............................................ ⎪a q + a q + ... + a q ≤ v, m2 2 mn n ⎪ m1 1 n ⎪ ⎪∑ q j = 1 ⎩ j =1 и обращающих в минимум функцию ~ z = v. (2.7) Замечание. Так же, как и в случае игрока A , цена игры v является переменной произвольного знака. Замечание. Задачи (2.4)-(2.5) и (2.6)-(2.7) являются парой двойственных задач. Поэтому цена игры в каждой из них будет одинакова. 61 Пример 2.2. Два конкурирующих предприятия «Левый» и «Правый», выпускающие обувь, имеют следующие доли общего сбыта своей продукции на местном рынке: «Левый» – 53%, «Правый» – 47%. Оба предприятия пытаются увеличить объем своих продаж. Для этого у них имеются следующие возможности: расширить сеть сбыта, реклама, увеличить ассортимент. Анализ показал, что изменения доли рынка предприятия «Левый» на рынке обуви в случае осуществления обоими предприятиями указанных мероприятий, задаются таблицей 2.5. Таблица 2.5 Мероприятия фирмы «Правый» Мероприятия Увеличение Отказ от Расширение фирмы «Левый» Реклама ассортимента проведения сети Расширение –4 –1 –3 6 сети Реклама –5 1 5 Увеличение –1 –3 –5 5 ассортимента Отказ от –8 –7 –6 проведения Как изменится доля рынка каждого предприятия после проведения ими соответствующих мероприятий? Какие мероприятия наиболее эффективны для каждого из предприятий? Решение Упростим платежную матрицу игры. Заметим, что стратегия «Расширение сети» фирмы «Левый» доминирует над стратегией «Отказ от проведения», поэтому вычеркнем в платежной матрице четвертую строчку. Получим таблицу 2.6. Таблица 2.6 Мероприятия фирмы «Правый» Мероприятия Увеличение Отказ от Расширение фирмы «Левый» Реклама ассортимента проведения сети Расширение –4 –1 –3 6 сети Реклама –5 1 5 Увеличение –1 –3 –5 5 ассортимента Аналогично, стратегия «Расширение сети» фирмы «Правый» доминирует над стратегией «Отказ от проведения», поэтому вычеркнем последний столбец в платежной матрице. Получим таблицу 2.7. 62 Таблица 2.7 Мероприятия фирмы «Левый» Расширение сети Реклама Увеличение ассортимента Мероприятия фирмы «Правый» Увеличение Расширение сети Реклама ассортимента –4 –1 –3 –5 1 –1 –3 –5 Найдем нижнюю и верхнюю цену игры, получим α = −4 , β = −1 . Значит, игра не имеет седловой точки. Увеличим все элементы платежной матрицы на 5, получим таблицу 2.8. Таблица 2.8 Мероприятия фирмы «Правый» Мероприятия Увеличение фирмы «Левый» Расширение сети Реклама ассортимента Расширение 1 4 2 сети Реклама 5 6 Увеличение 4 2 ассортимента Составим математическую модель задачи. Пусть p = ( p1 , p2 , p3 ) – смешанная стратегия, применяемая предприятием «Левый», v – цена игры, тогда требуется найти неотрицательные значения переменных p1 , p2 , p3 , p4 и v , удовлетворяющих системе ограничений + 4 p3 ≥ v , ⎧ p1 ⎪ 4 p + 5 p + 2 p ≥ v, ⎪ 1 2 3 (2.8) ⎨ p p v 2 6 , + ≥ 2 ⎪ 1 ⎪⎩ p1 + p2 + p3 = 1 и обращающих в максимум целевую функцию z = v. (2.9) Введем неотрицательные фиктивные переменные p4 , p5 , p6 , тогда система ограничений (2.8) примет вид: + 4 p3 − p 4 − v = 0, ⎧ p1 ⎪ 4p + 5p + 2p − p5 − v = 0, ⎪ 1 2 3 (2.10) ⎨ 2 6 , + − − = p p p v 1 2 6 ⎪ ⎪⎩ p1 + p2 + p3 = 1. Решив задачу (2.10)-(2.9) симплекс-методом, получим 63 2 1 1 1 ⎧ = − − + p p p p6 , 2 1 4 ⎪ 5 2 10 10 ⎪ ⎪p = 3 − 1 p + 1 p − 1 p , ⎪ 3 5 2 1 10 4 10 6 (2.11) ⎨ 4 3 3 7 ⎪ p5 = + p1 + p4 + p6 , ⎪ 5 2 10 10 ⎪ 12 3 2 ⎪v = − p1 − p4 − p6 , 5 5 5 ⎩ 12 3 2 (2.12) z = − p1 − p4 − p6 . 5 5 5 Значит, смешанная стратегия предприятия «Левый» имеет вид 13 ⎛ 2 3⎞ p = ⎜ 0, , ⎟ , а цена игры составляет − . 5 ⎝ 5 5⎠ Таким образом, фирме «Левый» не следует использовать стратегии «Расширение сети» и «Отказ от проведения», а оставшиеся стратегии применять с частотой 0,4 и 0,6 соответственно, при этом доля рынка компании уменьшится на 2,6 процента. Проведем анализ поведения предприятия «Правый». Требуется найти неотрицательные значения переменных q1 , q2 , q3 и v , удовлетворяющих системе ограничений ⎧ q1 + 4q2 + 2q3 ≤ v, ⎪ 5q 2 + 6 q 3 ≤ v , ⎪ (2.13) ⎨ q q v + ≤ 4 2 , 2 ⎪ 1 ⎪⎩ q1 + q2 + q3 = 1 и обращающих в минимум функцию ~ z = v. (2.14) Введем фиктивные неотрицательные переменные q4 , q5 и q6 , тогда система ограничений (2.13) примет вид − v = 0, ⎧ q1 + 4q2 + 2q3 + q4 ⎪ 5q2 + 6q3 + q5 − v = 0, ⎪ (2.15) ⎨ 4 2 , + + − = q q q v 2 6 ⎪ 1 ⎪⎩ q1 + q2 + q3 = 1. Решив задачу (2.15)-(2.14) симплекс-методом, получим 64 3 3 1 1 ⎧ q q q q6 , = − + − 1 2 5 ⎪ 5 10 10 10 ⎪ ⎪q = 2 − 7 q − 1 q + 1 q , ⎪ 3 5 10 2 10 5 10 6 (2.16) ⎨ 3 1 1 ⎪q = 1 − q + q + q , 2 5 6 ⎪ 4 2 2 2 ⎪ 12 4 2 3 ⎪v = + q 2 + q5 + q 6 , 5 5 5 5 ⎩ 12 4 2 3 (2.17) z = + q 2 + q5 + q 6 . 5 5 5 5 Значит, смешанная стратегия предприятия «Правый» имеет вид 13 ⎛3 2⎞ q = ⎜ , 0, ⎟ , а цена игры составляет − . 5 ⎝5 5⎠ Таким образом, фирме «Правый» не следует использовать стратегии «Реклама» и «Отказ от проведения», а оставшиеся стратегии применять с частотой 0,6 и 0,4 соответственно, при этом доля рынка компании увеличится на 2,6 процента. Программа в системе Mathcad 2001i Professional 65 66 67 § 3. Игры с природой В экономической практике нередко приходится сталкиваться с ситуациями, в которых один из участников безразличен к результату игры. Такие игры называют играми с природой, понимая под термином «природа» всю совокупность внешних обстоятельств, в которых сознательному игроку приходится принимать решения. Например, определение объема выпуска сезонной продукции в ожидании наиболее выгодного уровня спроса для ее реализации или формирование пакета ценных бумаг в расчете на более высокие дивиденды. В играх с природой степень неопределенности возрастает при принятии решения сознательным игроком, поскольку если в стратегических играх каждый из участников ожидает наихудшего для себя результата от действий партнера, то природа может принимать такие ответные действия, которые ей совсем невыгодны, а выгодны сознательному игроку. Поэтому можно сказать, что природа коварна, но не злонамеренна, она не стремится использовать в своих интересах ошибки соперника или информацию о его стратегии. Пример 2.3. Для отопления городка «Теплое лето» используется уголь, цена на который зависит от времени года и характера зимы. Летом 1 т угля стоит 6500 руб., в мягкую зиму – 7000 руб., в обычную – 8000 руб., а в холодную – 9000 руб. Расход угля за отопительный сезон полностью определяется характером зимы: на мягкую зиму требуется 6000 т, на обычную – 7000 т, а в холодную – 8000 т. Для подготовки к отопительному сезону мэр городка планирует приобрести некоторое количество угля ле68 том, а в случае необходимости, недостающую часть угля можно будет приобрести и зимой. При этом продать излишки угля возможности не будет. С каким предложением должен выступить мэр городка «Тепло летом» перед городским советом, чтобы экономия городского бюджета была наибольшей? Решение Мэр городка имеет возможность приобрести летом от 6000 т до 8000 т угля. В зависимости от типа зимы затраты (в млн. руб.) на приобретение угля представим в виде таблицы 2.9. Таблица 2.9 Закупка Вид зимы αi угля, т Мягкая Обычная Холодная 6000 –390 –398 –406 –406 7000 –455 –455 –464 –464 8000 –520 –520 –520 –520 βj –390 –398 –406 Найдем нижнюю и верхнюю цену игры, получим α = max α i = −406 , 1≤ i ≤3 β = min β j = −406 . Значит, игра имеет седловую точку, а чистая стратегия 1≤ j ≤3 мэра города состоит в покупке 6000 т угля летом, при этом в бюджете городка на отопление требуется выделить 406 млн. руб. Замечание. Так как игра из примера 2.3 имеет седловую точку, то ее платежная матрица может быть упрощена. Однако при упрощении матрицы нельзя отбрасывать доминируемые стратегии природы, так как она может реализовать любое свое состояние независимо от того, выгодно это игроку или нет. Пример 2.4. Фирма «Напитки покрепче» продает на улицах Смоленска квас и горячий чай. Данные о себестоимости, отпускных ценах и объемах реализации приведены в таблице 2.10. Таблица 2.10 Отпускная цена, руб. Объем реализации, ед. Себестоимость Вид В холодВ день изединицы проВ теплую напитка ную поготовлеПозже дукции, руб. погоду году ния Квас 8 12 3 6000 1200 Чай 5 8 2 1000 4000 Определите ежедневный объем производства кваса и чая, обеспечивающий предприятию наибольший доход. Решение Составим платежную матрицу игры, учитывая, что менеджер компании «Напитки покрепче» имеет возможность воспользоваться стратегиями: 69 «6000 ед. кваса и 1000 ед. чая» и «1200 ед. кваса и 4000 ед. чая», а природа реализует либо теплую, либо холодную погоду. Получим таблицу 2.11. Таблица 2.11 Природа αi Игрок Теплая погода Холодная погода «6000 ед. кваса 27000 –16200 –16200 и 1000 ед. чая» «1200 ед. кваса –3200 16800 –3200 и 4000 ед. чая» Нижняя и верхняя цены игры равны α = −3200 и β = 16800 соответственно. Так как природа может реализовать любое свое состояние, то найдем стратегию менеджера предприятия. Составим математическую модель задачи. Увеличим все элементы платежной матрицы на 16200, тогда если p = ( p1 , p2 ) – смешанная стратегия менеджера, то требуется найти неотрицательные значения переменных p1 , p2 и v удовлетворяющих системе ограничений ≥ v, ⎧43200 p1 ⎪ (2.18) ⎨ 13000 p1 + 33000 p2 ≥ v, ⎪ p1 + p2 = 1 ⎩ и обращающих в максимум функцию z = v. (2.19) Введем неотрицательные фиктивные переменные p3 и p4 , тогда система ограничений (2.18) примет вид: − p3 − v = 0, ⎧43200 p1 ⎪ (2.20) − p4 − v = 0, ⎨ 13000 p1 + 33000 p2 ⎪ p1 + p2 = 1. ⎩ Решив задачу (2.20)-(2.19) симплекс-методом, получим 25 1 1 ⎧ ⎪ p1 = 79 + 63200 p3 − 63200 p4 , ⎪ 54 1 1 ⎪ − p3 + p4 , (2.21) ⎨ p2 = 79 63200 63200 ⎪ 151 ⎪ 1782000 165 = − − v p p4 , 3 ⎪⎩ 79 316 316 1782000 165 151 (2.22) z= − p3 − p4 . 79 316 316 Таким образом, в среднем ежедневно целесообразно производить 6000 p1 + 1200 p2 = 2719 ед. кваса и 1000 p1 + 4000 p2 = 3051 ед. чая. При этом, независимо от погоды, средний доход компании составит 6357 руб. 70 Программа в системе Mathcad 2001i Professional 71 72 § 4. Принятие решений в условиях неопределенности Предположим, что в распоряжении игрока имеется m стратегий A1 , A2 , …, Am , а у природы предполагается наличие n возможных состояний B1 , B2 , …, Bn . Как уже было отмечено выше, игры с природой отличаются от стратегических игр тем, что природа может реализовать любое свое состояние независимо от действий игрока. Поэтому применение смешанных стратегий имеет весьма ограниченный характер, т.е. не всегда можно найти для них интерпретацию для использования в реальной обстановке. Таким образом, более естественным в играх с природой являются рекомендации для игрока, основанные на дополнительной информации и с использованием различных критериев. Определение 2.19. Пусть P = (aij ) – платежная матрица игры, а a j = max aij . Матрица 1≤ i ≤ m ⎛ r11 r12 ... r1n ⎞ ⎜ ⎟ ⎜ r21 r22 ... r2 n ⎟ R=⎜ , ... ... ... ... ⎟ ⎜⎜ ⎟⎟ r r ... r mn ⎠ ⎝ m1 m 2 где rij = a j − aij ( i = 1, m ; j = 1, n ), называется матрицей рисков. (2.23) Замечание. Матрица рисков отражает величину прибыли, которую игрок рискует недополучить в случае принятия того или иного решения. Байесовская стратегия Пусть нам известны вероятности состояний природы q1 = P(B1 ) , q2 = P(B2 ) , …, qn = P(Bn ) , где n ∑ q j = 1 . В этом случае в качестве показаj =1 теля эффективности, который максимизируется, берется математическое ожидание выигрыша, т.е. n ai = ∑ p j aij , (2.24) j =1 а показателя, который минимизируется, – математическое ожидание риска, т.е. n ri = ∑ p j rij (2.25) i =1 с учетом вероятностей всех возможных условий. Пример 2.5. Компания «Технодром» с целью привлечения покупателей планирует проведение ярмарки на открытом воздухе. Согласно ар73 хивным материалам метеосводок за много лет, можно выделить четыре типа метеорологических условий: зной, дождь, комфортно и холодно с ве1 1 1 1 и соответственно. В зависимости роятностями их наступления , , 5 5 2 10 от погодных условий ярмарку смогут посетить различные категории людей, поэтому компания выбирает один из трех вариантов проведения ярмарки: выставить полный, частичный или сокращенный ассортимент. Данные о доходах от проведения ярмарки приведены в таблице 2.12. Какие рекомендации может дать менеджер руководству компании? Таблица 2.12 Природа Менеджер Зной Дождь Комфортно Холодно Полный 6 5 9 2 ассортимент Частичный 2 3 6 8 ассортимент Сокращенный 3 2 7 5 ассортимент Решение Вычислим средний доход ai , соответствующий выставленному компанией ассортименту товаров по формуле (2.24), получим (2.24) a1 = 6 ⋅ 0,2 + 5 ⋅ 0,2 + 9 ⋅ 0,5 + 2 ⋅ 0,1 = 6,9 , a2 = 2 ⋅ 0,2 + 3 ⋅ 0,2 + 6 ⋅ 0,5 + 8 ⋅ 0,1 = 4,8 , (2.24) a3 = 3 ⋅ 0,2 + 2 ⋅ 0,2 + 7 ⋅ 0,5 + 5 ⋅ 0,1 = 5 . (2.24) Таким образом, наибольший средний доход компания получит в случае проведения выставки с полным ассортиментом. Оценим риск компании в данных условиях. Составим матрицу рисков, получим таблицу 2.13. Таблица 2.13 Природа Менеджер Зной Дождь Комфортно Холодно Полный 6 ассортимент Частичный 4 2 3 ассортимент Сокращенный 3 3 2 3 ассортимент Найдем средний риск ri в соответствии с представленным ассортиментом по формуле (2.25), получим r1 = 0,2 ⋅ 0 + 0,2 ⋅ 0 + 0,5 ⋅ 0 + 0,1 ⋅ 6 = 0,6 , (2.25) r2 = 0,2 ⋅ 4 + 0,2 ⋅ 2 + 0,5 ⋅ 3 + 0,1 ⋅ 0 = 2,5 , (2.25) r3 = 0,2 ⋅ 3 + 0,2 ⋅ 3 + 0,5 ⋅ 2 + 0,1 ⋅ 3 = 2,5 . (2.25) 74 Таким образом, минимальный риск соответствует первой стратегии. Значит, менеджер может рекомендовать руководству выставить на выставку полный ассортимент товаров. Замечание. Вообще говоря, средний риск обращается в минимум тогда же, когда средний доход обращается в максимум. Действительно, так как ai + ri = ∑ p j aij + ∑ p j (a j − aij ) = ∑ p j a j = const , то ai = const − ri , и n n n j =1 j =1 j =1 средние величины достигают своих экстремальных значений одновременно. Стратегия Вальда Согласно этому критерию в качестве оптимальной выбирается та стратегия игрока, при которой минимальный выигрыш максимален, т.е. игроку гарантируется выигрыш не меньший, чем нижняя цена игры с природой α = max min aij . (2.26) 1≤ i ≤ m 1≤ j ≤ n Замечание. Стратегию Вальда обычно называют стратегией «крайнего пессимизма», так как в результате рассмотрения стратегий выбирается тот образ действий, при котором складывается самая худшая ситуация. В примере 2.5 он соответствует любой из стратегий, так как во всех трех случаях нижняя цена достигается и равна 2. Стратегия Сэвиджа Согласно этому критерию в качестве оптимальной стратегии выбирается та, при которой величина риска принимает наименьшее значение r = min max rij . (2.27) 1≤ i ≤ m 1≤ j ≤ n Замечание. Так же, как и стратегия Вальда, критерий Сэвиджа является критерием крайнего пессимизма в том смысле, что наихудшим вариантом считается тот, при котором потеря выигрыша максимальна. В примере 2.5 стратегией Сэвиджа является «Сокращенный ассортимент», соответствующий значению r = 3 . Стратегия Гурвица Согласно этому критерию не следует руководствоваться ни крайним пессимизмом, ни крайним оптимизмом, а действовать более взвешенно: η = max⎛⎜ χ ⋅ min aij + (1 − χ ) max aij ⎞⎟ , 0 ≤ χ ≤ 1 . (2.28) 1≤ j ≤ n 1≤ i ≤ m⎝ 1≤ j ≤ n ⎠ Замечание. Выбор χ субъективен и выражает меру пессимизмаоптимизма игрока. Если χ = 1 , то стратегия Гурвица соответствует стратегии Вальда, а в случае χ = 0 – стратегии «розового оптимизма». 75 В примере 2.5 при χ = 0,5 получим, что стратегией Гурвица является «Полный ассортимент», при этом η = 5,5 . Программа в системе Mathcad 2001i Professional 76 77 Замечание. Все три критерия, рассмотренные для чистых стратегий, можно перенести и на случай смешанных стратегий. Например, согласно стратегии Гурвица следует выбирать ту смешанную стратегию p = ( p1 , p2 , ..., pm ) , для которой функция m m ⎞ ⎛ z = max ⎜⎜ χ min ∑ pi aij + (1 − χ ) max ∑ pi aij ⎟⎟ 1≤ j ≤ n pi ,1≤ i ≤ m i =1 ⎠ ⎝ 1≤ j ≤n i =1 достигает своего наибольшего значения. (2.29) Задачи и упражнения 1. В игру играют двое. Оба игрока одновременно показывают один, два или три пальца. Если сумма чисел, показанная пальцами, четна, то первый игрок выигрывает соответствующее число очков, а второй – проигрывает. Если же сумма нечетна, то выигрыш распределяется наоборот. Как должен играть каждый игрок, чтобы обеспечить себе максимальный выигрыш? 2. Двое играют в следующую игру. Первый игрок прячет в одной руке одну белую, а в другой – черную пешку. Второй игрок угадывает. Если второй угадал, то он получает от первого игрока одно очко, а если не 78 угадал, то отдает. Как должен играть второй игрок, чтобы получить максимальное число очков? 3. Найдите оптимальную стратегию игры «Камень-ножницы-бумага». 4. Зазывала и Лопух играют в следующую игру. Каждый из игроков имеет на руках по три карты: Зазывала – бубновый и трефовый тузы и бубновую двойку, а Лопух – бубновый и трефовый тузы и двойку треф. Игроки одновременно выбирают и показывают друг другу по одной карте. Если масти карт разные, то выигрывает Лопух, в противном случае – Зазывала. Если вскрытыми оказываются две двойки, то никто не выигрывает, в противном случае сумма выигрыша равна числу очков той карты, которую показал выигравший. Стоит ли Лопуху играть в эту игру? 5. Постройте следующую игру: один из игроков прячет в одном из n мест предмет стоимостью c j ( j = 1, n ), другой игрок ищет этот предмет, и если находит, то получает c j , в противном случае получает 0. Найдите цену игры и стратегии игроков. 6. Зрители Василий и Петр, присутствующие на конкурсе «Студенческая весна», называют один из девяти факультетов Fi ( i = 1, 9 ), причем факультет Fn побеждает факультет Fm , если n > m . Зритель, назвавший выигрышное по сравнению с партнером название, получает k очков. Если оба партнера называют один и тот же факультет, то их игра заканчивается в ничью. Найдите оптимальные стратегии игроков. 7. В районе улиц Оршанская и Пригородная планируется создание мастерской по ремонту бытовой техники в стационарных условиях не более 8000 шт. в год. Опыт других аналогичных предприятий показывает, что поток заявок на ремонт в условиях стационара выражается цифрами 2000, 4000, 6000 и 8000 шт. в год. Прибыль от ремонта единицы бытовой техники в среднем составляет 900 руб., потери, вызванные отказом в ремонте из-за недостатка мощностей, оценивается в 500 руб., а убытки от простоя специалистов обходятся в 600 руб. в расчете на одну ед. техники. Дайте рекомендации о мощности создаваемой мастерской. 8. На технологическую линию фирмы «Колбасы дяди Васи» по производству колбасы поступает сырье для производства колбас первого и высшего сортов. Линия может работать в трех режимах. Доход предприятия от реализации единицы продукции первого сорта при различных работах технологической линии составляет соответственно 500, 300 и 100 руб., а высшего сорта – 200, 500 и 600 руб. В каких режимах и сколько времени должна работать технологическая линия предприятия, чтобы доход от выпущенной продукции был наибольшим? 9. Банк «Золотые горы» имеет возможность выделить 10 млн. руб. на формирование портфеля акций. Ценные бумаги можно приобрести у компаний «Смоленск-Нефть», «Смоленск-Газ» и «Нано-Смоленск». Номинальная стоимость компании «Смоленск-Нефть» составляет 3000 руб., «Смоленск-Газ» – 2000 руб., «Нано-Смоленск» – 5000 руб. На конец года рынок может оказаться в одном из двух состояний – «Хорошо» и 79 «Отлично». Эксперты установили, что дивиденды компаний для этих состояний будут выражаться числами 10% и 15%, 8% и 12%, 14% и 8% соответственно. Какие рекомендации можно дать руководству банка по формированию портфеля акций для максимально возможной суммы прибыли? 10. Денис – прилежный студент факультета управления Смоленского государственного университета, который обычно получает хорошие отметки. Перед завтрашним экзаменом Денис столкнулся с небольшой проблемой, его сокурсники решили организовать вечеринку на всю ночь. Денис имеет три альтернативы: участвовать в вечеринке всю ночь, половину ночи участвовать, а половину учиться и учиться всю ночь. Профессор, принимающий завтрашний экзамен, непредсказуем в том смысле, что экзамен может оказаться легким, средним или трудным. В зависимости от сложности экзамена и времени, затраченного на повторение, можно ожидать баллы (в стобалльной системе), приведенные в таблице. Экзамен Время на повторение Легкий Средний Трудный Не было 85 60 40 Полночи 92 85 81 Всю ночь 100 88 82 Какую рекомендацию можно дать Денису? 11. Пусть в задаче 10 Денис заинтересован в получении отметки в четырехбалльной системе (90 и более – «отлично», 80 – «хорошо», 70 – «удовлетворительно», менее 70 – «неудовлетворительно»). Изменит ли это отношение к отметкам выбор Дениса? 12. Сформулируйте задачу по данным таблицы. B1 B2 B3 B4 A1 5 10 18 25 A2 8 7 8 23 A3 21 18 12 21 A4 30 22 19 15 pj 0,2 0,1 0,4 0,3 Дайте рекомендации, используя различные критерии. 80 Глава 3. Применение теории графов в экономике § 1. Основные понятия теории графов Определение 3.1. Графом G называется пара множеств G = X ,U , где X – множество вершин, U – множество отрезков (ребер), их соединяющих. Замечание. Обычно ребро обозначается следующим образом: u{a, b} , где a и b – вершины, которые соединяет ребро. Определение 3.2. Граф называется конечным, если множества X и U конечны, т.е. число вершин и ребер графа конечно. Определение 3.3. Две вершины графа называются смежными, если они различны и соединены непосредственно друг с другом ребром. Определение 3.4. Ребро называют инцидентным вершине, если оно соединено с ней. Определение 3.5. Матрицей смежности графа, содержащего n вершин a1 , a2 , …, an , в котором любые две вершины соединены не более чем одним ребром, называется матрица S размера n × n , в которой элемент sij равен 1, если имеется ребро, соединяющее вершины ai и a j , и sij = 0 – в противном случае. Пример 3.1. Постройте матрицу смежности графа, изображенного на рисунке 3.1. a2 a4 a1 a6 a3 a5 Рис. 3.1 Решение Так как граф, изображенный на рисунке 3.1, содержит 6 вершин, то матрица смежности графа будет размера 6 × 6 . Получим ⎛0 1 0 1 0 0⎞ ⎜ ⎟ ⎜1 0 0 1 0 0⎟ ⎜0 0 0 1 0 0⎟ ⎟. S =⎜ (3.1) 1 1 1 1 ⎜ ⎟ ⎜0 0 0 0 0 1⎟ ⎜ ⎟ ⎜0 0 0 1 1 0⎟ ⎝ ⎠ 81 Замечание. Матрица смежности графа симметрична относительно главной диагонали. Определение 3.5. Ориентированное ребро (имеющее направление) называется дугой. Определение 3.6. Граф, состоящий из множества вершин и дуг, называется ориентированным графом или орграфом. Замечание. В орграфе дуга обозначается u (a, b ) , где a – вершина, из которой выходит дуга u , b – вершина, в которую эта дуга входит. Определение 3.7. Последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей, называется путем и обозначается µ(u1 , u 2 , ..., u k ) . Определение 3.8. Путь, у которого начальная вершина совпадает с конечной, называется контуром. Определение 3.9. Контур, состоящий из одной дуги, называется петлей. Определение 3.10. Матрицей инцидентности орграфа без петель, содержащего n вершин a1 , a2 , …, an и m дуг u1 , u 2 , …, u m , называется матрица T размера n × m , в которой элемент tij равен 1, если дуга u j выходит из вершины ai , tij = −1 , если дуга u j входит в вершину ai , и tij = 0 , если дуга u j не инцидентна вершине ui . Пример 3.2. Постройте матрицу инцидентности орграфа, изображенного на рисунке 3.2. a2 u1 a1 u3 u2 a3 a4 u5 a6 u4 a5 u7 u6 Рис. 3.2 Решение Так как орграф, изображенный на рисунке 3.2, содержит 6 вершин и 7 ребер, то матрица инцидентности графа будет размера 6 × 7 . Получим 0 0 0 0⎞ ⎛−1 1 ⎜ ⎟ 0 −1 0 0 0⎟ ⎜1 ⎜0 0 1 0 1⎟ ⎜ ⎟. T= (3.1) − − − 1 1 1 1 ⎜ ⎟ ⎜0 0 0 0 1 − 1⎟ ⎜ ⎟ ⎜0 0 0 1 − 1 0 ⎟⎠ ⎝ 82 Определение 3.11. Орграф называется взвешенным, если каждой его дуге u поставлено в соответствие некоторое число L(u ) , называемое его весом (длиной). Определение 3.12. Длиной пути µ(u1 , u 2 , ..., u k ) называется сумма длин дуг, входящих в этот путь, т.е. k L(µ ) = ∑ L(ui ) . (3.1) i =1 Замечание. В графе аналогом контура является цикл, а аналогом пути – цепь. Замечание. Любой граф можно сделать орграфом, заменив каждое его ребро двумя противоположно направленными дугами. Определение 3.13. Граф называется связным, если любые две его вершины связаны цепью. Определение 3.14. Конечный связный граф без циклов называется деревом. Определение 3.15. Две вершины a и b орграфа называются сильно связанными, если существует путь из вершины a в вершину b и – из b в a . Определение 3.16. Говорят, что орграф сильно связен, если любая пара его различных вершин сильно связана. Определение 3.17. Два графа G и H называются изоморфными, если между множествами их вершин существует взаимно однозначное соответствие, сохраняющее смежность. § 2. Задача о кратчайшем пути Пусть задан взвешенный граф G = X ,U , X = {a1 , a2 , ..., an }. Рассмотрим следующую задачу: требуется для любых двух вершин a и b найти цепь µ ab наименьшей длины. Данная задача имеет весьма важное практическое приложение, например, при планировании маршрутов передвижения транспорта, последовательностей взаимосвязанных работ и т.п. Алгоритм поиска кратчайшего пути 1. Перейти от графа G к изоморфному графу H , в котором начальной вершиной является a0 , а конечной – an . 2. Каждую вершину ai пометить индексом λ i = ∞ ( i = 1, n − 1 ), λ n = 0 . 83 3. Найти такое ребро {ai , a j }, для которого λ j − λ i > L({ai , a j }), и заменить индекс λ j индексом λ' j = λ i + L({ai , a j }) < λ j . 4. Продолжать процесс до тех пор, пока остается хотя бы одно ребро, для которого можно уменьшить λ j . После окончания данной процедуры индекс λ1 начальной вершины a1 является длиной кратчайшего пути между вершинами a1 и an . Сам путь будет найден при движении от начальной вершины к конечной переходом от вершины с большим индексом к вершине с меньшим индексом. При этом переход должен осуществляться таким образом, чтобы разность между индексами смежных вершин была равна длине соединяющего их ребра. Пример 3.3. Схема метрополитена города С и время движения поездов метро между станциями в минутах изображена на рисунке 3.3. Найдите маршрут от станции «Любовь» до станции «Разлука», отнимающий у пассажира наименьшее время. 10 3 3 4 6 3 5 8 12 5 2 7 10 Любовь 15 3 2 7 5 1 3 10 12 1 8 4 12 Разлука 1 7 3 Рис. 3.3 Решение Схема метрополитена города представляет собой граф. Пусть станция «Любовь» соответствует вершине графа a1 , а станция «Разлука» – вершине графа a20 . Время движения поездов между станциями соответствует длине соответствующего ребра графа, изображенного на рисунке 3.3. Тогда требуется найти цепь наименьшей длины, соединяющей вершины графа a1 и a20 . Воспользовавшись алгоритмом поиска кратчайшего пути, получим граф, изображенный на рисунке 3.4. 84 20 3 4 27 3 5 31 23 5 2 7 10 15 3 7 8 19 a1 10 6 21 12 30 17 3 2 9 7 28 5 1 13 10 3 23 12 1 12 1 14 7 an 10 8 18 4 26 2 3 13 Рис. 3.4 Таким образом, наименьшее время движения пассажира между станциями составит 31 минуту, а сам путь выделен на рисунке. Применение методов линейного программирования Пусть дан взвешенный орграф G = X ,U , где X = {a1 , a2 , ..., an }. Пусть uij – дуга, соединяющая вершины ai и a j , причем L(uij ) = cij ( i = 1, n , j = 1, n ). Каждой дуге графа uij поставим в соответствие перемен- ную xij , которая может принимать значения из множества {0,1}, считая xij = 1 , если ребро uij входит в путь и xij = 0 – в противном случае. Тогда длина искомого пути будет задаваться функцией n n z = ∑∑ cij xij . (3.2) i =1 j =1 Разделим все вершины графа на начальную a1 , промежуточные и конечную an . Тогда каждой промежуточной вершине, входящей в кратчайший путь, будет инцидентно ровно две дуги, а начальной и конечной вершинам – одна дуга. Значит, для каждой промежуточной вершины ak ( k = 2, n − 1 ) сумма pk входящих и qk выходящих дуг должны удовлетворять соотношениям pk qk i =1 j =1 ∑ xik = ∑ xkj , (3.3) т.е. сумма входящих дуг в промежуточную вершину должна быть равна сумме выходящих из нее дуг. 85 Для начальной и конечной вершин должны выполняться соотношения p1 q1 i =1 pn j =1 qn i =1 j =1 ∑ xi1 = 0 , ∑ x1 j = 1 , (3.4) ∑ xin = 1 , ∑ xnj = 0 . (3.5) Замечание. Если потребовать неотрицательность переменных xij , то условия (3.3)-(3.5) будут необходимыми и достаточными для того, чтобы переменные xij принимали значения во множестве {0,1}. Таким образом, для нахождения кратчайшего пути в орграфе требуется найти неотрицательные значения переменных xij ( i = 1, n , j = 1, n ), удовлетворяющих ограничениям (3.3)-(3.5) и обращающих в минимум функцию (3.2). Замечание. Если cij = c ji , то кратчайший путь может быть найден в графе. Замечание. Так как система ограничений и целевая функция сформулированной выше задачи обычно содержат большое количество переменных, то ее «ручное» решение весьма громоздко. Программа в системе Mathcad 2001i Professional 86 87 88 89 90 § 3. Задача о наибольшем потоке Определение 3.18. Транспортной сетью называется взвешенный орграф, имеющий ровно одну вершину без входящих дуг (вход сети) и ровно одну вершину без выходящих дуг (выход сети). Замечание. Вес дуги u в транспортной сети обычно называется пропускной способностью дуги и обозначается C (u ) . В каждой дуге u сети может существовать поток ϕ(u ) , удовлетворяющий условию 0 ≤ ϕ(u ) ≤ C (u ) . При этом для каждой вершины сети, кроме входа и выхода, сумма входящих потоков должна быть равна сумме выходящих потоков. Замечание. Можно считать, что C (u ) и ϕ(u ) – целые числа. Рассмотрим следующую задачу: при заданной конфигурации транспортной сети и известных пропускных способностях дуг найти наибольшую величину потока, которую может пропустить транспортная сеть, а также распределение полученного потока по дугам. Сформулированная задача имеет большое количество интерпретаций в зависимости от того, что понимается под дугами и вершинами графа. Например, трубопроводы, железные дороги, телефонная сеть, по которым пересылают нефть, газ, грузы, сообщения. Пусть вершина a1 – вход сети, а an – ее выход. Определение 3.19. Дуга u называется насыщенной, если поток, проходящий по этой дуге, равен ее пропускной способности, т.е. ϕ(u ) = C (u ) . Определение 3.20. Поток Φ , входящий в выход сети, называется полным, если каждый путь, ведущий из входа сети a1 в ее выход an , содержит хотя бы одну насыщенную дугу. Алгоритм нахождения наибольшего потока I. Нахождение полного потока 1. Найти путь из вершины a1 в вершину an , все дуги которого не насыщены, и увеличить в них потоки на единицу, т.е. ϕ′(u ) = ϕ(u ) + 1. 2. Повторять п. 1 до тех пор, пока поток в сети не станет полным. II. Нахождение наибольшего потока 1. Пометить вершину a1 индексом 1. 2. Если ai – уже помеченная вершина, то пометить индексом + i все непомеченные вершины, в которые идут ненасыщенные дуги из ai , и индексом − i все непомеченные вершины, из которых идут дуги с ненулевым потоком в ai . 3. Если в результате этого процесса вершина an не будет помечена, то найденный поток наибольший. В противном случае, между вершинами 91 a1 и an найдется путь, все вершины которого различны и с точностью до знака помечены номерами предыдущих вершин. Поток во всех дугах этого пути увеличить на единицу, если при движении от a1 к an дуга проходится в направлении ее ориентации, и уменьшить на единицу в противном случае. 4. Повторить п. 1-3 до тех пор, пока не будет найден наибольший поток. Пример 3.4. Газотранспортная система города С представлена на рисунке 3.5. Найдите распределение объема газа по каждому из трубопроводов, при котором общий объем транспортируемого газа будет наибольшим. a3 3 a2 4 1 1 2 a1 3 5 8 5 a4 a6 a5 Рис. 3.5 Решение Найдем полный поток, получим рисунок 3.6. a3 3 a2 1 1 a1 7 2 1 1 4 3 1 8 3 5 5 5 a4 4 2 a6 a5 Рис. 3.6 Дуги (a3 , a6 ) , (a4 , a3 ) и (a4 , a5 ) являются насыщенными. Найдем теперь наибольший поток, получим рисунок 3.7. a3 4 2 3 a2 1 1 1 a1 7 2 1 8 1 a4 1 4 3 1 5 5 Рис. 3.7 92 4 2 5 3 5 a5 -3 a6 Так как вершина a6 помечена, то найденный поток не является наибольшим. Изменим потоки в дугах пути, соединяющего вершины a1 и an , и повторим алгоритм. Получим рисунок 3.8. a3 3 a2 2 1 1 a1 8 1 2 2 3 1 1 8 1 4 5 5 a4 4 4 5 a6 a5 Рис. 3.8 Так как вершина a6 не помечена, то найденный поток наибольший. Таким образом, наибольший объем газа, который можно передать через газотранспортную сеть города С, равен 8, а его распределение по трубопроводам представлено на рисунке 3.8. Замечание. Отметим, что дуга (a1 , a2 ) является лишней в рассматриваемой транспортной сети. Применение методов линейного программирования Пусть дан взвешенный орграф G = X ,U , где X = {a1 , a2 , ..., an }. Пусть uij – дуга, соединяющая вершины ai и a j , причем C (uij ) = cij ( i = 1, n , j = 1, n ). Каждой дуге графа uij поставим в соответствие переменную xij , которая представляет собой поток, проходящий по дуге uij , тогда 0 ≤ xij ≤ C (uij ) . (3.6) Разделим все вершины графа на вход сети a1 , промежуточные вершины и выход сети an . Тогда в каждой промежуточной вершине должно выполнятся условие сохранения потока, т.е. для каждой промежуточной вершины ak ( k = 2, n − 1 ) сумма pk входящих и qk выходящих потоков должны удовлетворять соотношениям pk qk i =1 j =1 ∑ xik = ∑ xkj . (3.7) Для входа и выхода сети должны выполняться соотношения q1 qn j =1 j =1 ∑ x1 j = ∑ xnj , (3.8) т.е. сумма выходящего потока должна быть равна сумме входящего потока. 93 Тогда величина потока, проходящего через сеть, будет равна величине потока, выходящего из вершины an , т.е. q1 z = ∑ x1 j . (3.9) j =1 Таким образом, для нахождения наибольшего потока, проходящего через транспортную сеть, требуется найти неотрицательные значения переменных xij ( i = 1, n ; j = 1, n ), удовлетворяющих ограничениям (3.6)-(3.8) и обращающих в максимум функцию (3.9). Программа в системе Mathcad 2001i Professional 94 Замечание. К задаче о потоке в сети можно свести, например, n n транспортную задачу, выбрав в качестве целевой функцию z = ∑∑ cij xij i =1 j =1 § 4. Построение графа наименьшей длины Пусть имеется некоторое количество пунктов a1 , a2 , …, an , которые нужно соединить между собой дорогами (линиями электропередач, трубопроводами и т.п.). Для каждой пары пунктов ai и a j ( i = 1, n , j = 1, n ) из- вестна стоимость (длина, время постройки и т.п.) L{ai , a j }. Необходимо выбрать самый экономичны вариант соединения между собой всех пунктов a1 , a2 , …, an . Для решения поставленной задачи рассмотрим взвешенный граф 95 G = X ,U , где X = {a1 , a2 , ..., an }. Тогда граф G должен иметь минимальную длину входящих в него ребер. Определение 3.21. Связный граф, имеющий минимальную длину входящих в него ребер, называется графом наименьшей длины (остовом). Замечание. Граф наименьшей длины не содержит циклов, поэтому является деревом. Значит, для соединения n вершин потребуется n − 1 ребро. Алгоритм построения графа наименьшей длины 1. Построить самое короткое ребро u1 . 2. Из оставшихся ребер построить самое короткое ребро u k ( 2 ≤ k ≤ n − 1 ), которое в совокупности с остальными ребрами не образует циклов. 3. Повторять п.2 до тех пор, пока не будут исчерпаны все ребра. Замечание. Приведенный выше алгоритм обычно называют жадным. Пример 3.5. Проводится газификация поселков А, Б, …, Ж Первоапрельского района Весенней губернии. Расстояние между населенными пунктами (в км) приведено в таблице 3.1. Постройте конфигурацию газопровода, имеющего наименьшую протяженность. Таблица 3.1 Пункты А Б В Г Д Е Ё Ж А 3 6 7 5 7 15 12 Б 3 1 6 4 7 13 9 В 6 1 6 4 3 9 7 Г 7 6 6 8 4 3 6 Д 5 4 4 8 2 8 3 Е 7 7 3 4 2 5 2 Ё 15 13 9 3 8 5 5 Ж 12 9 7 6 3 2 5 Решение Воспользовавшись алгоритмом построения графа наименьшей длины, получим рис. 3.9. В Б Г 1 3 3 А 3 4 Ё 2 Е Д 2 Ж Рис. 3.9 96 Задачи и упражнения 1. Постройте граф по заданной матрице смежности S , если ⎛0 1 0 0 1 1⎞ ⎜ ⎟ 1 1 1 1 ⎜ ⎟ ⎜0 1 0 0 1 1⎟ ⎟. S =⎜ ⎜0 1 0 0 1 0⎟ ⎜1 0 1 1 0 1⎟ ⎜ ⎟ ⎜1 1 1 0 1 0⎟ ⎝ ⎠ 2. Постройте орграф по заданной матрице инцидентности T , если 1 0 0 0⎞ ⎛1 ⎜ ⎟ 0 0 0⎟ ⎜−1 0 1 ⎜ 0 −1 0 1 0 1⎟ ⎟. T =⎜ ⎜ 0 0 0 −1 −1 0⎟ ⎜ 0 0 −1 0 1 0⎟ ⎜ ⎟ ⎜ 0 1 −1 0 0 1⎟ ⎝ ⎠ 3. На орграфе, заданном на рис.3.10 , найдите кратчайший путь из вершины 1 в вершину 5. 2 4 3 2 1 2 3 3 1 1 1 4 5 2 Рис. 3.10 Составьте соответствующую задачу линейного программирования и решите ее. 4. Для орграфа, заданного на рис. 3.10, найдите наибольший поток из вершины 1 в вершину 5. Составьте соответствующую задачу линейного программирования и решите ее. 5. Транспортная система городка С представлена на рис. 3.11. Найдите максимальный поток автомобилей, который способна обслужить данная система, если цифрами обозначена максимальная пропускная способность каждого участка дороги (тыс. машин в день). 97 2 1 5 1 4 2 3 2 2 2 2 Рис. 3.11 Дайте рекомендации мэру городка о необходимости расширения транспортной сети. 6. Решите задачу из примера 3.5 методами линейного программирования. 7. Каждый день Некто утром отправляется из дома А на работу в Б, а вечером возвращается домой. Схема проезда, время на каждом участке дороги представлены на рис. 3.12. Найдите путь, требующий минимального времени на проезд в зависимости от времени суток. 1 4 9 1 А 5 3 8 6 3 4 2 3 Б 6 2 7 1 Рис. 3.12 8. Для обустройства загородного дома Олег Архипович решил проложить дорожки, соединяющие все объекты инфраструктуры: дом (А), баня (Б), гараж (В), домик для гостей (Г), беседка (Д), бассейн (Е), водопад (Ё), теннисный корт (Ж) и футбольное поле (З). Длина предполагаемых дорожек между объектами приведена в таблице. А Б В Г Д Е Ё Ж З А 10 10 80 40 20 100 60 70 Б 10 20 100 20 10 90 120 100 В 10 20 60 40 60 110 50 60 Г 80 100 60 40 40 90 40 60 Д 40 20 40 40 40 80 60 80 Е 20 10 60 40 40 120 20 30 Ё 100 90 110 90 80 120 30 80 Ж 60 120 50 40 60 20 30 10 З 70 100 60 60 80 30 80 10 Разработайте проект наименьшей стоимости. 98 Рекомендуемая литература 1. Акулич И.Л. Математическое программирование / И.Л. Акулич. – М.: Высш. шк., 1986. 2. Вентцель Е.С. Исследование операций / Е.С. Вентцель. – М.: Сов. радио, 1972. 3. Вентцель Е.С. Теория вероятностей / Е.С. Вентцель. – М.: Высшая школа, 2005. 4. Волков И.К. Исследование операций: учебное пособие для вузов / И.К. Волков, Е.А. Загоруйко. – 2-е изд. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. 5. Волошин Г.Я. Методы оптимизации в экономике: учебное пособие / Г.Я. Волошин. – М.: Издательство «Дело и сервис», 2004. 6. Гасс С. Путешествие в страну Линейного программирования / С. Гасс. – М.: Мир, 1971. 7. Кузнецов А.В. Высшая математика: Математическое программирование / А.В. Кузнецов, В.А. Сакович, Н.И. Холод. – Мн.: Высш. шк., 1994. 8. Кузнецов А.В. Руководство к решению задач по математическому программированию: учебное пособие / А.В. Кузнецов, Н.И. Холод, Л.С. Костевич. – 2-е изд., перераб. и доп. – Мн.: Высш. шк., 2001. 9. Таха Х. Введение в исследование операций / Х. Таха. – М.: Мир, 2005. 99 Оглавление Введение Глава 1. Задачи оптимизации в экономике § 1. Постановка некоторых задач линейного программирования § 2. Основная задача линейного программирования. Симплекс-метод § 3. Анализ модели на чувствительность § 4. Двойственные задачи линейного программирования § 5. Целочисленное программирование § 6. Транспортная задача § 7. Дробно-линейное программирование § 8. Многокритериальные задачи Задачи и упражнения Глава 2. Элементы теории игр § 1. Основные понятия теории игр § 2. Решение игр методами линейного программирования § 3. Игры с природой § 4. Принятие решений в условиях неопределенности Задачи и упражнения Глава 3. Применение теории графов в экономике § 1. Основные понятия теории графов § 2. Задача о кратчайшем пути § 3. Задача о наибольшем потоке § 4. Построение графа наименьшей длины Задачи и упражнения Рекомендуемая литература Дизайн обложки Г.Х. Блакуновой Редактор Л.В. Бушуева Издательство Смоленского государственного университета Подписано к печати 12.11.2009. Формат 60×84 1/16. Бумага офсетная. Печать ризографическая. Усл. п. л. 6,25. Уч.-изд. л. 6,25. Тираж 150 экз. Заказ № Отпечатано с оригинал-макета авторов в ИТЦ СмолГУ 214000, Смоленск, ул. Пржевальского, д. 4 100 3 4 4 6 11 13 19 26 35 39 52 56 56 60 68 73 78 81 81 83 91 95 97 99