Линейное и целочисленное программирование.

Тема 1 Линейное и целочисленное программирование. §1.1 Общая постановка задачи программирования. Классические задачи. линейного Общая задача линейного программирования формулируется следующим образом. Даны система m линейных уравнений и неравенств с n переменными и линейная функция . Необходимо найти такое решение системы , где (j=1,2,…,l, l ), при котором линейная функция F принимает оптимальное значение (т.е. максимальное или минимальное). Записанная выше система называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функций или функцией цели. Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение системы ограничений, удовлетворяющее условию неотрицательности переменных, при котором линейная функция F принимает оптимальное значение. Каноническая задача линейного программирования имеет вид , (j=1,2,…,l, l ) и линейная функция F . Она отличается от других задач тем, что ее система ограничений является системой уравнений и все переменные неотрицательные. При необходимости перехода от неравенства к уравнению вводятся дополнительные переменные. Неравенство заменяется уравнением и условием неотрицательности дополнительной переменной , а неравенство 1 уравнением . Дополнительные переменные вводят в целевую функцию с коэффициентом, равным нулю. В канонической задаче целевая функция может как минимизироваться, так и максимизироваться. Для того чтобы перейти от нахождения максимума к нахождению минимума или наоборот, достаточно изменить знаки коэффициентов целевой функции. Полученная в результате этого задача и исходная задача имеют одно и тоже оптимальное решение, а значения целевых функций на этом решении отличаются только знаком. Моделью будем называть условный образ какого-либо объекта, приближенно воссоздающий этот объект с помощью некоторого языка. В экономико-математических моделях таким объектом является экономический процесс, а языком – классические и специально разработанные математические методы. Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта, которое выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений. Для составления модели задачи линейного программирования, заданной в текстовой форме, необходимо: 1. ввести обозначение для неизвестных задачи 2. проанализировать ограничения для них (например, неотрицательность) 3. составить систему ограничений 4. составить целевую функцию и установить вид экстремума. Этапы экономико-математического моделирования: 1) Постановка цели и задачи исследования. Качественное описание объекта в виде экономической модели. 2) Формирование математической модели, изучаемого объекта. Выбор или разработка методов исследования. 3) Анализ математической модели и полученных результатов. Построение математических моделей простейших экономических задач. 1. Задача об использовании ресурсов (задача планирования производства) Для изготовления двух видов продукции и используют четыре вида ресурсов, , и . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице. Вид ресурса Число единиц ресурсов, затрачиваемых на изготовление единицы продукции Запас ресурса 18 1 2 3 16 2 1 5 - 1 21 3 - Прибыль, получаемая от единицы продукции и – соответственно 2 и 3 руб. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Решение. Составим экономико-математическую модель. Пусть и – число единиц продукции соответственно и запланированных к производству. Для их изготовления потребуется единиц ресурса , 2 единиц ресурса , , единиц ресурса и единиц ресурса . Так как потребление ресурсов , и не должно превышать их запасов, соответственно 18,16,5 и 21 ед., то связь между потреблением ресурсов и их запасами выразится системой неравенств По смыслу задачи переменные , . Суммарная прибыль F составит руб. от реализации продукции и – от реализации продукции , т.е. . Экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий записанной системе неравенств при котором функция F принимает максимальное значение. 2. Задача составления рациона (задача о диете, задача о смесях). Имеется два вида корма I и II, содержащих питательные вещества (витамины) , . Содержание числа единиц питательных веществ в 1 кг каждого вида корма необходимы минимум питательных веществ приведены в таблице. Питательное вещество Необходимый минимум питательных веществ 9 Число единиц питательных веществ в 1 кг корма 3 I II 3 1 8 1 2 12 1 6 Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела. Решение. Составим экономико-математическую модель. Пусть и – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать 3 единиц питательного вещества , единиц питательного вещества , , единиц питательного вещества . Так как содержание питательных веществ , в рационе должно быть не менее соответственно 9, 8, и 12 единиц, то получим систему неравенств: При этом переменные , . Общая стоимость рациона F . Экономико-математическая модель: составить дневной рацион , удовлетворяющий записанной выше системе с условием , , при котором функция принимает минимальное значение. §1.2 Решение задач графическим методом. линейного программирования Геометрическим методом может быть решена задача в стандартной форме с двумя переменными. К такой форме может быть сведена и каноническая задача, когда n-m=2, где n – число переменных, а m – число уравнений. Линейная функция является прямой. Пусть F=а. Прямая, вдоль которой линейная функция F сохраняет постоянное значений F=a, называется линией уровня, которая имеет вид . При увеличении или уменьшении значений постоянной а линия уровня будет перемещаться вдоль многогранника решений. Направление возрастания значений линейной функции определяется вектором - градиентом функции F: . Передвигая линию уровня в направлении вектора определяется оптимальное решение в точке «входа» в многогранник решений в задаче минимизации функции F и в точке «выхода» в задаче максимизации F. 4 Алгоритм графического решения задачи линейного программирования. 1. построить ОДР 2. Построить вектор нормали n   c1 , c2  целевой функции (указывает на направление возрастания целевой функции) 3. Построить верхнюю и нижнюю опорные прямые, т.е. крайние линии уровня целевой функции, имеющие общие точки с О.Д.Р. 4. определить координаты экстремальных точек (пересечение опорных прямых с О.Д.Р.) Замечание: 1. Если О.Д.Р. пустое множ., то задача не имеет решения, ввиду несовместности системы ограничений 2. Если О.Д.Р. неограниченна по направлению вектора n то сама целевая функция неограниченна сверху в этой области. (в противном случае зеркально). Пример. Найти наибольшее и наименьшее значения линейной функции F  3x1  4 x2 в области решений системы: (1) ( 2) (3) Решение. На первом этапе определим многоугольник решений системы неравенств, на втором - найдем наибольшее и наименьшее значения функции F на полученном многоугольнике решений. 1. Построим многоугольник решений заданной системы неравенств (рис. 1). x2 B С L A n{3;4}    (3) x1 (2) (1) Рис. 1 Множество точек треугольника АВС образуют область решений данной системы. 5 2. Найдем наибольшее и наименьшее значения функции F  3x1  4 x2 на треугольнике решений системы неравенств. Рассмотрим прямую L, построенную по линейной функции F  c1 x1  c2 x2 при условии, что F= a, где a – заданное число. По уравнению 3x1  4 x2  a строим прямую L следующим образом: Сначала построим вектор нормали n . Координаты вектора n определяются по коэффициентам при x1 и x 2 в уравнении 3x1  4 x2  a . Следовательно, n 3;4. Если начало вектора поставить в начало координат, то конец вектора n определяется координатами точки (3;4). Проведем прямую L через начало координат перпендикулярно вектору n (в этом случае уравнение принимает вид 3x1  4 x 2  0 , где a  0 ). Будем передвигать  прямую L параллельно самой себе в направлении, указанном вектором n , до треугольника АВС и найдем точки «входа» и «выхода» области. Точка «входа» прямой L - точка А, а точка «выхода» – точка B. Стрелка вектора n показывает направление роста значения функции F  3x1  4 x2 . Точки и А и С определяются при решении систем линейных уравнений. Точка А – это пересечение прямых (1) и (3). Решая систему уравнений,  x1  x 2  3,   x1  7 x 2  77. 8х2 = 80 => х2 = 10, тогда х1 = 7. Получим точку А(7; 10). Точка В – это пересечение прямых (1) и (2). Решим систему уравнений   x1  x2  3,  5 x1  5 x2  15,  =>  5 x  3 x  97 . 1 2   5 x1  3x2  97. 8х2 = 112 => х2 = 14, тогда х1 = 11. Точка В (11;14). Таким образом, в точке A(7;10) функция F принимает наименьшее значение (Z  61) , в точке B(11;14) - наибольшее ( Z  89) . §1.3 Симплекс-метод. Понятие о методе искусственного базиса. Симплексный метод – метод последовательного улучшения решения (плана) и нахождения оптимального решения (плана). Он заключается в том, что в начале находится любое допустимое базисное решение, соответствующее одной из угловых точек многогранника решений, а затем это решение целенаправленно улучшается, переходя к новому базисному решению в соседней угловой точке, при котором значение целевой функции не уменьшается (не увеличивается) в задаче на максимум (минимум), 6 пока не будет получено оптимальное решение. Этот метод, является универсальным, с помощью которого можно решить любую задачу линейного программирования. Все необходимые базисные решения целесообразно получать с помощью таблиц Гаусса. В первый блок таблицы заносятся данные исходной задачи. При необходимости некоторые уравнения системы ограничений следует умножать на -1 (чтобы все свободные члены были неотрицательными). Последнюю строку, которую назовем индексной, заполняем коэффициентами целевой функции, представленной в виде уравнения , где – свободный член L(X). Вместо записываем в первом блоке только , а в последующих блоках – результаты вычислений. … … … … … … … Св. член … … Каждая итерация, т.е. переход от одного блока таблицы к другому осуществляется известными элементарными преобразованиями Жордана – Гаусса для строк. Они сводятся к следующим действиям: 1) Выбирают p-й разрешающий столбец из условия, что (в задаче на максимум) и хотя бы один элемент в нем ; 2) Выбирают q-ю разрешающую строку из условия , для . 3) На пересечении разрешающей строки и разрешающего столбца выбирается разрешающий коэффициент . 4) Разрешающая строка делится на . 5) Все остальные элементы таблицы пересчитываются по формулам , , , , . Теорема 1. (Основная теорема симплекс-метода) Если после выполнения очередной итерации: 1) Найдется хотя бы одна отрицательная оценка (при решении задачи на максимум) и в каждом столбце с такой оценкой окажется хотя бы один положительный элемент, то можно улучшить решение, выполнив следующую итерацию; 7 2) Найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, то функция L не ограничена в области допустимых решений ( ); 3) Все оценки окажутся неотрицательными, тогда достигнуто оптимальное решение. Опорным решением задачи линейного программирования называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Число отличных от нуля координат опорного решения не может быть больше ранга r системы векторов условий (числа линейно независимых уравнений системы ограничений). Будем в дальнейшем считать, что система ограничений состоит из линейно независимых уравнений, т.е. r=m. Если число отличных от нуля координат опорного решения равно mто решение называется невырожденным, в противном случае (меньше m) – вырожденным. Базисом опорного решения называется базис системы векторов условий задачи, включающий в свой состав векторы, соответствующие отличным от нуля координатам опорного решения. Теорема 2. (Оптимальности решения) Допустимое базисное решение является оптимальным в том и только в том случае, когда среди коэффициентов индексной строки нет отрицательных в задаче на максимум (нет положительных в задаче на минимум). Если коэффициенты индексной строки имеют разные знаки, то соответствующее допустимое базисное решение не является оптимальным как в задаче на максимум, так и в задаче на минимум, и следует переходить к другому базисному решению. Алгоритм симплексного метода решения задачи линейного программирования. 1. Получить нулевое уравнение. Для этого функцию цели выразить через свободные переменные имеющегося опорного решения и перенести все переменные в левую часть. Присоединить нулевое уравнение к системе ограничений как дополнительное уравнение. 2. Рассмотреть оценки свободных переменных. Если все оценки неотрицательны (неположительны), то имеющееся решение доставляет максимум (минимум) функции цели. Если в задаче требуется найти максимум (минимум), то выписать найденное оптимальное решение и соответствующее максимальное (минимальное) значение функции цели. В противном случае в качестве разрешающего выбрать столбец p, которому соответствует отрицательная (положительная) оценка. 3. Найти соотношения ai 0 aip разрешающей выбрать строку, найденных соотношений. для всех которой 8 aip  0 , i  1, 2,..., m. соответствует В качестве наименьшее из 4. Выполнить одну итерацию метода Жордано-Гауса. Перейти к пункту 2. Особые случаи решения задач симплекс-алгоритмом. 1. После выбора разрешающего столбца может оказаться, что что разрешающую строку выбрать невозможно. Это может быть только тогда, когда среди коэффициентов разрешающего столбца нет положительных элементов. В этом случае задача линейного программирования решений не имеет. 2. После отыскания оптимального решения оценки некоторых свободных переменных равны нулю. Это значит, что имеет место альтернативный оптимум. Действительно, если ввести в базис переменную, имеющую нулевую оценку, то получится другое, также оптимальное решение. 3. После выбора разрешающего столбца и нахождения отношений вида ai 0 aip имеет несколько таких минимальных отношений. Если выбор разрешающей строки производить бессистемно, то может произойти «зацикливание», т.е. ситуация, когда циклически находится некоторая группа одних и тех же опорных решений. В этом случае для предотвращения зацикливания в качестве разрешающей следует всегда выбирать строку с наименьшим номером в системе ограничений. Метод искусственного базиса применяется для решения задач линейного программирования симплексным методом в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов. Согласно данному методу для задачи линейного программирования составляется так называемая расширенная задача, которая решается симплексным методом. На основе результатов решения расширенной задачи либо находится оптимальное решение исходной задачи, либо устанавливается причина ее отсутствия. Пусть имеется каноническая задача линейного программирования , (j=1,2,…,l, l ). Без ограничений общности можно считать, что правые части уравнений системы ограничений неотрицательны. Для исходной задачи составляют расширенную, используя при этом искусственные переменные. Искусственными переменными называют неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на минимум с 9 коэффициентом +М, а в задаче на максимум с коэффициентом –М. число М сколь угодно большое по сравнению с единицей. В общем случае расширенная задача на максимум имеет вид: , (j=1,2,…,l, l ). Если расширенная задача линейного программирования имеет оптимальное решение , у которого все искусственные переменные равны нулю, то исходная задача имеет оптимальное решение , которое получается из отбрасыванием нулевых искусственных переменных (признак оптимальности решения). Если расширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная отлична от нуля, то исходная задача не имеет решения виду несовместности системы ограничений (признак отсутствия решения ввиду несовместности системы ограничений). Если расширенная задача не имеет решения, ввиду неограниченности целевой функции, то исходная задача не имеет решения по той же причине (признак отсутствия решения ввиду неограниченности). 1. §1.5 Транспортная задача линейного программирования. Математическая модель. Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны ( ) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи записываются в таблице вида … 10 … … … … … … … Переменными (неизвестными) транспортной задачи являются ( ) – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок . Математическая модель транспортной задачи в общем случае имеет вид. , (1) , (2) (3) , . (4) Целевая функция задачи выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Равенство (2) из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью. Вторая группа из n уравнений в равенстве (3) выражает требование полностью удовлетворить запросы всех n потребителей. Неравенство (4) является условием неотрицательности всех переменных задачи. Т.о. математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи , , удовлетворяющие системам ограничений , , условиям неотрицательности и обеспечивающие минимум целевой функции . В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. . Такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом. 2.Опорное решение транспортной задачи. 11 Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Ввиду того что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения используют циклы. Циклом называется такая последовательность клеток таблицы транспортной задачи , , ,…, , в которой две и только две соседние клетки расположены в одной строке или столбце. Причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , является опорным только в том случае, когда на занятых им клеток таблицы нельзя образовать ни одного цикла. Для проверки возможности образования цикла используют метод вычеркивания. Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, т.к. цикл имеет две и только две клетки в каждой строке или в столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение – опорным. Если же после вычеркивания останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным. 3.Метод потенциалов. Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система n+m действительных чисел, и , , удовлетворяющих следующим условиям: при (5) при . (6) Числа и называют потенциалами. 12 Группа равенств (5) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет n+m неизвестных , и , . Число уравнений системы, как число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Т.к. число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно (чаще нуль), а остальные найти из системы. Группа неравенств (6) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде: , при . Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи. Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные. Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k), соответствующую . Если , то решение оптимальное. Если же , то для соответствующей клетки (l,k) строят цикл и улучшают решение, перераспределяя груз по этому циклу. Особенности решения транспортных задач с неправильным балансом: 1. Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. , то необходимо ввести фиктивного (n+1)го потребителя с запросами , равным разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза . 2. Если суммарные запросы потребителей превосходят суммарные запросы поставщиков, т.е. , то необходимо ввести фиктивного (m+1)-го поставщика с запасами , равными разности суммарных запросов потребителей и запасов поставщиков, и нулевыми стоимостями перевозок единиц груза . 3. При составлении начального опорного решения в последнюю очередь следует распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствует наименьшая стоимость перевозок, равная нулю. Алгоритм решения транспортных задач методом потенциалов. 1. Проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок. 2. Построить начальное опорное решение (методом северо-западного угла или др. методом). 13 3. Построить систему потенциалов, соответствующих опорному решению. 4. Проверить выполнение условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам , и те из них, которые больше нуля записывают в левые нижние углы клеток. Если для всех свободных клеток , то вычисляют значение целевой функции и решение задачи заканчивается, т.к. полученное решение является оптимальным. Если же имеется, хотя бы одна клетка с положительной оценкой. Опорное решение не является оптимальным. 5. Перейти к новому опорному решению. На котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка . Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается , остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1. 6. Далее перейти к п.3. Тема 5 Теория игр. §5.1 Игровые модели. Платежная матрица. Нижняя и верхняя цена игры. Методы решения задач с конфликтными ситуациями разработаны математической теорией, которая носит название теория игр. Математичекая модель конфликтной ситуации назыавется игрой, стороны, учавствующие в конфликте, – игроками, а исход игры конфликта – выйгрышем. Для каждой игры вводятся правила, т.е. система условий, определяющая: 1) варианты дейсвтия игроков; 2) объем информации каждого игрока о поведении партнеров; 3) выйгрыш, к которому приводит каждая совокупность действий. Как правило, выйгрыш (или проигрыш) может быть задан количественно. Игра называется парной, если в ней учавствуют два игрока, и множественной, если число игроков больше двух. Парная игра называется игрой с нулевой суммой, или антагонистической, если выйгрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными, когда это сознательный выбор игроком одного из возможных дейсвтий и случайными, когда это 14 случайно выбранное действие. Далее будем рассматривать только личные ходы игроков. Опр. Стратегией игрока называется совокупнотсь правил, определяющих выбор его дейсвтия при каждом личном ходе в зависимости от сложившейся ситуации. Опр. Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в данной игре, т.е. максимальный выйгрыш. Опр. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае. Для того чтобы решить игру или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выйгрыш, когда второй придерживается своей стратегии. Задача теории игр – выявление стратегий игроков. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии, такие стратегии называются оптимальными. Оптимальные стратегии должны удовлетворять условию устойчивости, т.е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре. Если игра повторяется достаточно много раз, то игроков может интересовать не выйгрыш и проигрыш в каждой конкретной партии, а средний выигрыш (проигрыш) во всех партиях. Целью теории игр является определении оптимальной стратегии для каждого игрока. Рассмотрим парную конечную игру с нулевой суммой. Пусть игрок А располагает m различными стратегиями, котороые обозначим . Пусть у игрока В имеется n различных стратегий, . В этом случае игра имеет размерность . В результате выбора игроками любой пары стратегий и ( ; .) однозначно определяется исход игры, т.е. выйгрыш игрока А (положительный или отрицательный) и проигрыш игрока В. Если предположить, что значения известны для любой пары стратегий ( , ), то матрица ( ; элементами котоой являются выйгрыши, соответствующие стратегиям ( , называется платежной матрицей или матрицей игры. … … … … 15 … … … … … ). ), Строки этой таблицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. Пример. Каждый из двух игроков А и В одновременно и независимо друг от друга записывает на листе бумаги любое целое число. Если выписанные числа имеют одинаковую четность, то игрок А получает от игрока В 1 рубль, а если разную, то наоборот – игрок А платит 1 рубль игроку В. Решение. У игрока А две стратегии: - записать нечетное число, записать нечетное число. У игрока В такие же две стратегии: - записать четное число - записать нечетное число. Выбор игроками соответственно стратегий , однозначно определяет исход игры – выигрыш игрока А. Матрица этой игры имеет следующий вид . Рассмотрим игру с матрицей ( ; ) и определим наилучшую среди стратегий . Выбирая стратегию , игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий , для которой выйгрыш для игрока А минимален. Обозначим через наименьший выйгрыш игрока А при выборе им стратегии для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е. . Среди всех чисел ( ) выберем наибольшее – нижняя цена игры, или максимальный выигрыш (максимин). Это гарантированный выйгрыш игрока А при любой стратегии игрока В. Следовательно, Стратегия, соответствующая максимуму, называется максиминной стратегией. Игрок B заинтересован в том, чтобы уменьшить выигрыш игрока A. Выбирая стратегию , он учитывает максимально возможный при этом выигрыш для A. Пусть . Среди всех чисел выберем наименьшее – верхняя цена игры, или минимальный выигрыш (минимакс). Это гарантированный проигрыш игрока B. Следовательно, Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегией, называется принципом минимакса. Этот принцип 16 следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. Пример. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (r), зеленого (g) или синего (b) цветов и расплачиваются друг с другом так, как показанов матрице игры . Считая, что эта 3х3 игра повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков. Начнем с последовательного анализа стратегий игрока A, не забывая о том, что выбирая стратегию игрока A, должно принимать в расчет, что его противник B может ответить на нее той из своих стратегий, при которой выигрыш игрока A будет минимальным. Запишем эти минимальные выигрыши в правом столбце таблицы: -2 2 3 2 1 -3 -1 1 1 -2 1 -3 Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре. Аналогичные рассуждения можно провести и за игрока B. Так как игрок B заинтересован в том, чтобы обратить выигрыш игрока A в минимум, то ему нужно проанализировать каждую свою стратегию с точки зрения максимального выигрыша игрока A. -2 2 3 3 2 1 -3 2 -1 1 1 1 -2 1 -3 Если игрок B будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1. В рассматриваемой игре числа maxmin и minmax совпали: . Это значение называется чистой ценой игры или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. 17 Выделенные стратегии и являются оптимальными для игроков A и B, , , это означает, что при многократном повторении игры отказ от выбранной стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш). Пара чистых стратегий и дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой. В предыдущем примере - седловая точка. §5.2 Решение игр в смешанных стратегиях. Если игра не имеет седловой, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии. Смешанной тратегией игрока А называется применение чистых стратегий с вероятностями , причем сума вероятностей равна единицы. Смешаные стратегии игрока А записываются в виде матрицы или в виде строки стратегии игрока B обозначаются или . Аналогично смешанные , где . Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой единица соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение. Цена игры удовлетворяет неравенству , где β – нижняя и верхняя цены игры. Основная теорема теории игр – теорема Неймана. Каждая конечная игра имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий. Пусть и – пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной. Теорема 6 (об активных стратегиях). Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры , если второй игрок не выходит за пределы своих активных стратегий. 18 Игра размера 2 х 2 является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответствующих этой точке. В игре, в которой отсутствует седловая точка, в соответсвии с основной теоремой игр оптимальное решение существует и определяется парой смешанных стратегий и . Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок A придерживается своей оптимальной стратегии , то его средний выигрыш будет равен цене игры , какой бы активной стратегией ни пользовался игрок B. Для игры 2 2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока A (проигрыш игрока B) – случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока A (оптимальная стратегия) будет равен и для первой, и для второй стратегии противника. Пусть игра задана платежной матрицей , а игроки A и B используют оптимальные смешанные стратегии ; . Эти стратегии и цена игры определяются из систем уравнений решения которых , , , , . Пример. Найти оптимальные стратегии игры, заданной платежной матрицей . Решение. Т.к. , , поэтоиу решение ищем в смешанных стратегиях. Для игрока А стредний выйгрыш равен цене игры v (при ). Для игрока В средний проигрыш равен цене игры v (при ). Системы уравнений, записанные ранее, в этом случае имеют вид . 19 Решая эти системы, получаем , . Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, при этом средний выйгрыш равен 0. Пусть игра m x n , без седловой точки задана платежной матрицей ,i= 1, 2, … , m; j = 1, 2, … , n. Игрок A обладает стратегиями , , … , , а игрок B – стратегиями , , … , . Необходимо определить оптимальные стратегии и Цель игрока A (B) – максимизировать (минимизировать) гарантированный выигрыш (проигрыш), т.е. цену игры ν, или минимизировать (максимизировать) величину 1/ν. При такой постановке оптимальной стратегии и определяются как решения двух взаимно двойственных задач линейного программирования: при ограничениях , ,…, где при ограничениях , , , где ,…, , . При этом цена игры . Пример. Предприятие может выпускать три вида продукции , получая при этом прибыль, зависящую от спроса, который может быть в одном из четырех состояний . Дана матрица, ее элементы характеризует прибыль, которую получит предприятие при выпуске i-й продукуции с j-м состоянием спроса. 3 3 6 8 9 10 4 2 7 7 5 4 Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным. Решение. Задача сводится к игровой модели, в которой игра предприятия A против спроса B задана платежной матрицей. Прежде чем решать задачу, 20 можно попытаться упростить игру, проведя анализ платежной матрицы и отбросив стратегии, заведомо невыгодные или дублирующие. Так, вторая стратегия (второй столбец матрицы) является явно невыгодной для игрока B по сравнению с первой (элементы второго столбца не меньше элементов первого столбца), так как цель игрока B – уменьшить выигрыш игрока A. Поэтому второй столбец можно отбросить. Получим матрицу P размера 3 х 3: . спрос вид продукции 3 9 7 6 4 5 8 2 4 9 6 8 3 2 4 4 6 Определим нижнюю и верхнюю цены игры в таблице. Так как , то седловая точка отсутствует и оптимальное решение следует искать в смешанных стратегиях игроков: и . Обозначим , i = 1, 2, 3 и , j = 1, 2, 3, составим две взаимно двойственные задачи линейного программирования. Задача 1 , j = 1, 2, 3 , i = 1, 2, 3 . . Задача 2 Решая каждую задачу симплексным методом, получаем при оптимальном базисном решении Из соотношений находим цену игры . По формулам , 21 ; ; ; , т.е. , т.е. . . (учтено исключение второго столбца исходной матрицы). Итак, оптимальный спрос в 20% случаев находится в состоянии и 80% – в состоянии . Итак, предприятие должно выпустить 40% продукции и 60% продукции , а продукцию не выпускать. 22