Теории графов. Методы и модели линейного программирования. Теория игр

Оглавление Тема1 МЕТОДЫ И МОДЕЛИ ТЕОРИИ ГРАФОВ И СЕТЕВОГО МОДЕЛИРОВАНИЯ 3 Тема 2 Элементы теории графов 11 Тема3 Методы решения сетевых задач 18 Тема 4 Методы сетевого планирования 40 Тема 5 МЕТОДЫ И МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 51 Тема 6 Методы решения задач коммерческой деятельности 59 Тема 7. Алгебраический симплексный метод 65 Тема 8 Другие методы решения задачи линейного программирования 74 Тема 9 Метод потенциалов 81 ГЛАВА 10. МЕТОДЫ И МОДЕЛИ ТЕОРИИ ИГР 91 Тема 11 Методы и модели решения игровых задач 103 Тема 12 Игровые модели в условиях коммерческого риска 116 Тема1 МЕТОДЫ И МОДЕЛИ ТЕОРИИ ГРАФОВ И СЕТЕВОГО МОДЕЛИРОВАНИЯ В коммерческой деятельности большинство возникающих задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Коммерческую деятельность можно рассматривать как совокупность задач, предназначенных для передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов — области математики, началом развития которой явилась задача о кенигсбергс-ких мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов (рис. 4.1.1), которые связывали с берегами и друг с другом два острова. Задача заключалась в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи. Позже Д. К. Максвелл и Г. Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50-60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов. Рис. 1.1. Модель задачи о кенигсбергских мостах Элементы теории графов В коммерческой деятельности коммерсантам постоянно приходится решать задачи поиска покупателей продукции, товаров, имеющихся в распоряжении у предприятий, клиентов-посредников как на территории России, так и за рубежом. При этом в движении постоянно пребывают люди, деньги, товары, документы, информация. После определения возможных мест, которые необходимо посетить, возникает задача выбора оптимального маршрута их посещения, так называемая задача коммивояжера, которая представлена графически на рис. 4.1.2. Палех Горький Рис. 1.2. Неориентированный граф задачи коммивояжера Структура изображения задачи на рис. 4.1.1 называется графом. Граф задается двумя множествами: непустым множеством X и множеством U, содержащим пары элементов из множества X. При этом элементы множества U могут повторяться, а также могут повторяться элементы в парах. Граф, заданный на множествах X и U, обозначается G = (X, U). Если элементы в парах множества U не упорядочены, то граф называется неориентированным, в противном случае — ориентированным, или орграфом. Элементы множества X называют вершинами графа, а множества U — ребрами для неориентированного графа и дугами для орграфа. На плоскости граф задается в виде точек (вершин) и линий, соединяющих некоторые из них (ребер или дуг). На рис. 4.1.3, 4.1.4 изображены соответственно неориентированный и ориентированный графы. Рис. 1.3. Несвязный неориентированный граф Рис. 1.4. Ориентированный граф Для неориентированного графа на рис. 4.1.3 множество вершин X и ребер U можно записать так: X = {X1, Х2, Х3, Х4, Х5, X6, X7}, U = {(x1, х1), (х1, х2), (х3, х2), (х3, х4), (х3, х5), (х4, х5), (х5, х6)} Для ориентированного графа множества вершин и дуг записываются следующим образом: X = { Х1, Х2, Х3, X4),U = {( X1, X2), (X1, Х3), (Х3, Х2), (Х3, Х3), (X3, Х4)} или U = {и1 и2, и3, и4, и5} Приведем ряд определений для неориентированных графов. Ребро, начало и конец которого совпадают, называется петлей (х1 х1), рис. 4.1.3. Вершины называются смежными, или соседними, если существует ребро, их соединяющее (х1, х2), (х3, х4), (х3, х5), (х4, х5), (х5, х6), вершины х3 и х6 несмежные. Если вершина Является началом или концом ребра, то вершина и ребро называются инцидентными. Степенью вершины называется число инцидентных ей ребер, степень вершины х обозначается d(x). Например, рис. 4.1.2 d(x2) = 2; d(x3) = 3; d(x4) = 2; d(x5) = 3; d(x1) = 3, поскольку ребро (x1, x1) учитывается дважды. Вершина, степень которой равна нулю d(x7) = 0, называется изолированной х7. Вершина, степень которой равна единице d(x6) = 1, называется висячей, или тупиковой х6. Последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего, называется маршрутом. Число ребер в маршруте определяет его длину: ((х1, х2, х3, х5, х4, х3, х3)- маршрут, длина которого равна 6, рис. 4.1.3. Цепью называется маршрут, в котором все ребра попарно различны. Например, (х4; х3; х2; x1; х1) - цепь, длина которой равна 4. Простой называется цепь, в которой все вершины попарно различны, например, (х1, х2, х3, х4, х5), рис. 4.1.3. Граф называется связным, если для любых двух его вершин существует цепь, соединяющая эти вершины. Граф представленный на рис. 4.1.2, - связный, а на рис. 4.1.3 - несвязный, поскольку не существует цепи, соединяющей вершину (х7) с остальными. Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины. Диаметром графа называется максимальное расстояние между его вершинами. Циклом (простым циклом) называется цепь (простая цепь), начало и конец которой совпадают (на рис. 4.1.3 "эта последовательность (х3; х4; х5; х3)). Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Его можно нарисовать, не отрывая карандаша от бумаги и не повторяя линий «одним росчерком» (рис. 4.1.76). Подграфом графа G называется граф G1 с множеством вершин Х1 и множеством ребер U1, такой, что Х1  X, U1  U. Для графа на рис. 4.1.3 подграфом может быть граф G1 = (Х1, U1), где Х1 = (х1, х2, х3, х4, х5), a U1 = {(х1, х2), (х2, х3), (х3, х4), (х3, х5)). Подграф называется собственным, если он отличен от самого графа, например G1 и G2. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа, на рис. 4.1.3 граф имеет две компоненты связности. Вершина графа, удаление которой повышает число компонент связности, называется точкой сочленения. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей ребер. Точкой сочленения является, например, вершина х3 (см. рис. 4.1.3), удаление которой приводит к появлению третьей компоненты связности. Деревом называется связный граф без циклов рис. 1.5. Рис. 1.5. Дерево Вершина х1 является корнем дерева. Лесом называется граф без циклов, представляющий собой совокупность деревьев рис. 1.6. Рис. 1.6. Лес Граф называется полным, если любые две его вершины соединены ребром (см. рис. 4.1.2). Граф называется регулярным степени d, если все его вершины имеют степень d. На рис. 1.2 регулярный граф степени d = 5. Регулярный граф, все вершины которого имеют степень 1, называется паросочетанием. Граф называется двухдольным, если множество его вершин X может быть разделено на два непересекающихся подмножества таким образом, что каждое ребро графа соединяет вершины из двух разных подмножеств. Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Например, для графа рис. 4.1.7а цепь (6, 1, 5,4, 3, 2,8,9,10,11,12,13,14,15, 20,19,18,17,16, 7) является гамильтоновой. Гамильтоновым циклом называется гамильтоновая цепь, начало и конец которой совпадают. Если в конец предыдущей цепи дописать вершину 6, получим гамильтонов цикл. Граф называется гамильтоновым, если в нем имеется гамильтонов цикл (см. рис. 1.7а). Термин гамильтонов связано с именем голландского математика У. Гамильтона, который в 1859 г. предложил игру «Кругосветное путешествие». Каждой из двенадцати вершин додекаэдра (см. рис. 1.7а) соответствует один из городов мира. Необходимо, переезжая из города в город по ребрам додекаэдра, посетить каждый город только один раз и вернуться назад. Эта задача сводится к поиску простого цикла, проходящего через каждую вершину графа Рис. 1.7. Графы Задачи, касающиеся эйлеровых и гамильтоновых цепей и циклов, часто встречаются на практике. Например, в ситуациях, когда качество выполнения комплекса коммерческих операций, работ, мероприятий существенно зависит от последовательности, в которой они выполняются. Граф называется взвешенным, если каждому его ребру поставлено в соответствие некоторое число, называемое весом ребра, например расстояние между городами, стоимость или время проезда между ними. Задачу коммивояжера можно представить как в виде ориентированного, так и неориентированного графа рис. 1.8 а,б. Предложенный вариант решения задачи коммивояжера представляет собой кольцевой маршрут, где каждый город посещается только один раз, начиная с любого населенного пункта. Для ориентированных графов в основном все определения сохраняются, однако имеются некоторые отличия. Последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей, называется путем. Длина пути определяется количеством в нем дуг. Путь называется простым, если в нем дуга не встречается дважды, в противном случае он является составным. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Путь, который начинается и заканчивается в одной и той же вершине, называется контуром. В неориентированном графе пользуются термином не путь, а цепь, а вместо контура — цикл. Рис. 1.8. Графы В графе рис. 1.4 путем является, например, последовательность (х1; х3; х3; х2). Последовательность (х2; х3; х4) путем не является, так как не существует дуги, соединяющей х2 и х3. Для ориентированного графа вместо степени вершины вводится понятие полустепеней исхода и захода. Если вершина является началом дуги, то дуга называется исходящей из вершины, если концом, то — заходящей. Полустепенью исхода вершины d-(x) называется число дуг, исходящих из этой вершины, полустепенью захода d+(x) — число дуг, заходящих в вершину. Для графа, изображенного на рис. 4.1.4, можно записать: d-(x3) = 2, d-(x1) = 2, d+(x3) = 2, d+( x1) = 0. При выполнении анализа на компьютере граф неудобно задавать графически, а лучше представлять его в виде матриц, операции с которыми достаточно просто проводить на компьютере. Известно несколько типов матриц, позволяющих задавать граф. Матрицей смежности графа, содержащего n-вершин, называется квадратная матрица Аnхm, каждый элемент которой аij определяется следующим образом: 1, если вершины i и j соединены ребром или дугой; 0, в противном случае. Для графа с кратными ребрами (дугами) вместо 1 записывается число ребер (дуг) между вершинами i и j. Для неориентированного графа, представленного на рис. 1.3, матрица смежности имеет размерность (7x7) и записывается в виде Слева и сверху проставлены номера вершин. Для ориентированного графа, изображенного на рис. 4.1.4, матрица смежности имеет размерность (4x4) и записывается в виде Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности. Тема 2 Элементы теории графов Матрицей инцидентности ориентированного графа с п вершинами и m ребрами называется матрица В c n строками и т столбцами, элемент которой bij определяется следующим образом: 1, если вершина является началом ребра (i, j); -1, если вершина является концом ребра (i, j); 2, если вершина и начало, и конец ребра (i, j); 0, если вершина и ребро не инцидентны. Для ориентированного графа, представленного на рис. 1.4, матрица инцидентности В4х5 имеет следующий вид: Взвешенный ориентированный граф без петель, в котором выделено k-вершин, называемых полюсами, является k-полюсной цепью. Среди сетей особо выделяется двухполюсная транспортная сеть (рис. 4.1.9) S — (N, U) с множеством вершин N и множеством дуг U, для которых выполняется следующее условие: 1) существует только одна вершина сети s  N,в которую не заходит ни одна дуга. Эта вершина называется входом, или истоком сети; 2) существует только одна вершина сети t  N, из которой не выходит ни одной дуги сети. Эта вершина называется выходом, или стоком сети; 3) каждой дуге сети и  U поставлено в соответствие неотрицательное число с(u), называемое пропускной способностью дуги. Рис. 1.9. Транспортная сеть Примерами вершин сети могут быть пересечения автострад, электростанции, телефонные узлы, железнодорожные узлы, аэропорты, водохранилища, товарные склады. Примерами дуг сети могут быть дороги, линии электропередачи, телефонные линии, авиалинии, водные магистрали, нефте- и газопроводы. Постановку и решение подобных задач можно получить с помощью методов сетевого моделирования. 4.2. Природа потоков в сетях и принцип их сохранения Сходство сетевых представлений наблюдается в природе, технике и различных сферах деятельности человека. Так, например, с высоты птичьего полета или самолета можно наблюдать сетевую модель формирования реки, например Волги от ее истоков маленькие ручейки и реки, соединяясь во взаимосвязанные артерии, объединяются в одно большое русло, по которому потоки воды устремляются в Каспийское море. Такие же аналогии представляют собой сети железных дорог, по которым транспортные потоки направляются из пунктов отправления в пункты назначения, осуществляя перевозку потоков грузов и пассажиров. Совокупность линии электропередач так же представляют собой вместе энергетическую сеть, по которой потоки электроэнергии от электростанций по проводам поступают к потребителям. Автомобильные дороги как в масштабе города, района, области, так и в более крупных масштабах страны или, например, части света -Европы представляют собой сети, по которым движутся потоки автомобилей. Нефте- и газопроводы в совокупности представляют собой сети трубопроводов, по которым потоки нефти или газа поступают от источников к потребителям. Водопроводные сети обеспечивают движение потоков воды по трубопроводам от источников к потребителям. Аналогичные сети представляют собой маршруты движения кораблей и самолетов, обеспечивающие перемещение потоков пассажиров и грузов по планете. Такие же аналогии представляют собой телефонные, радио и телекоммуникационные сети, по которым циркулируют информационные потоки, например компьютерные сети связи различного назначения. Особый интерес представляют сети, образованные движением товарных и финансовых потоков, которые могут пояснить очень многие явления нашей жизни, поскольку они являются необходимыми для обеспечения жизни людей. Перечисленные сетевые аналогии потоковых процессов имеют динамический характер, связанный с перемещениями различных по своей природе масс в пространстве: электроэнергии, нефти, газа, воды, воздуха, железнодорожного, воздушного, автомобильного транспорта, товаров, финансов, пешеходов, информации и т.п. Причем существование этих потоков необходимо для обеспечения и поддержания жизнедеятельности человека. Именно поэтому возник принцип сохранения потока. Сетевое представление взаимодействия и циркуляции потоков необходимо, чтобы оценить и вычислить разные характеристики, описывающие условия существования и поведения потоков в таких сетях. Множество возникающих в таких случаях задач может быть решено с помощью теории потоков в сетях. В этой теории в качестве основы рассматриваются движения в сетях потоков любой природы от источника s к стоку t. Определение. Потоком в сети S = (N, U) от входа s  N к выходу t  N называется неотрицательная функция , определенная на множестве дуг сети U, со следующими свойствами: 1) величина потока, по каждой дуге не должна превосходить ее пропускной способности 0  (i, j)  c(i, j) (i, y) U ; 2) величина потока, входящего в каждую вершину сети, за исключением входа и выхода, равна величине потока, выходящего из этой вершины. , где - множество вершин, инцидентных дугам, направленных от вершины i; Ni - множество вершин, инцидентных дугам, направленным к вершине с. Из определения потока следует, что величина потока не исчезает и не накапливается в вершинах сети, и, следовательно, количество потока из входа s равно количеству потока, заходящему в выход t. Это значение называется величиной потока V. Таким образом, поток в сети сохраняется, а величина потока равняется сумме значений потоков, выходящих из вершины s или входящих в вершину t: На рис. 2.1 изображена сеть автомобильных потоков. Рис. 2.1. Сеть автомобильных потоков Представленная ориентированная сеть S = (N, U) имеет множество вершин N = {l, 2, 3, 4} и множество дуг U = {(1, 2) (2, 3) (2, 4), (1, З),(З, 4)}. Количественные характеристики дуг сети, а также взаимосвязь между ее узлами могут быть представлены с помощью матрицы расстояний L = ||lij|| или матрицы стоимостей C = ||cij||, Для ориентированной сети рис. 4.2.1 матрица смежности имеет вид 1 2 3 4 1 1 1 2 1 1 3 1 4 Матрица инциденций ориентированной сети рис. 2.1 имеет вид Вершины N Дуги (i, j) (1,2) (2,3) (2,4) (1.3) (3,4) 1 2 3 4 +1 -1 +1 -1 +1 -1 +1 -1 +1 -1 На рис. 2.1 стрелками показано направление одностороннего разрешенного движения потоков автомобилей. От одного перекрестка i до другого / пропускная способность по дуге по каждой улице c(i, j) ограничена и определяется шириной улиц и максимально допустимой скоростью движения, например 60 км/ч. В связи с этим мощность автомобильного потока (i, j) не может превысить допустимую с(i, j). Таким образом выполняется первое свойство потока, условие существования статического или устойчивого потока для каждой улицы: 0(i,j)c(i,j) (i,j)U. Рассматривая взаимодействие ограничений по каждой улице и в совокупности, вместе по всем перекресткам (вершинам сети), условие сохранения потока в этой сети записывается следующим образом: Для источника сети при i= s нет входящих потоков, следовательно, . Для стока при i = t нет выходящих потоков, следовательно, Рассмотрим пример анализа ориентированной сети S = (N, U), представленной на рис 4.2.1, N = {s, 1,2,3,4, t}; U={(s, l);(s,3); (1, 2); (1, 3); (2, t); (3, 2); (3, 4); (4, t)}. Пропускная способность указана над каждой дугой, где рядом в скобках указано значение потока. Свойства потока в данном случае выполняется. Указанные величины не превышают пропускных способностей дуг. В каждой вершине, отличной от входа и выхода, поток сохраняется. Например, в вершину 2 заходят 4 единицы потока по дугам (1,2) и (3,2) и выходят 4 единицы по дуге (2,t) Величина потока V = 3 + 4 = 7. Теорема о максимальном потоке и минимальном разрезе Пусть в ориентированной сети S = (N, U) от источника к стоку протекает поток, величина которого равна V. Поскольку пропускная способность каждой дуги с (i, j) является величиной конечной, то максимальная величина допустимого потока всей сети тоже ограничена. Максимальный поток сети определяется на основе одного из основных понятий теории сетей — понятия разреза. Введем понятие разреза. Множество вершин N сети S = (N, U) можно разбить на два непересекающихся подмножества Np и , которые соединяются между собой дугами, образующими множество Up. Причем исток s принадлежит множеству узлов Np, а сток t принадлежит множеству узлов . Тогда величина потока из множества Np в множество , протекающего по дугам Up не может быть больше, чем сумма пропускных способностей дуг этого множества, что можно записать таким образом: Этот барьер для потока, отделяющий множество узлов Np от множества узлов , называется разрезом и обозначается (Np, ). Разрез представляет такое множество дуг Up, исключение которых отделяет_вход от выхода сети, и, следовательно, отделяет множество Np от сети S = (N, U) таким образом, что существование потока в таком случае невозможно, и тогда V=0. Причем начало дуги разреза принадлежит множеству Np , а конец — . Таким образом в разрез входят дуги, соединяющие вершины этих множеств. Величина максимального потока от источника s к стоку t ограничена сверху величиной разреза C(Np, ), определяемой суммой пропускных способностей всех входящих в него дуг множества Up и, следовательно, VC(Np, ). Минимальным разрезом сети называется разрез, имеющий минимальную величину. В соответствии с теоремой о максимальном потоке и минимальном разрезе, сформулированной Фордом и Фалкерсоном, величина максимального потока Vmax от входа s (источника) в выход t (сток) равна величине минимального разреза, отделяющего вход и выход сети и, следовательно, . Рассматриваемые сети являются сетями с ограниченной пропускной способностью, что имеет распространение в реальной жизни. Это послужило поводом к появлению и постановке задач о максимальном потоке, связанных с определением максимально допустимой величины Упри соблюдении условий, записанных в виде системы уравнений и неравенств. В сформулированной выше задаче для сохранения потока автомобилей рис 4.2.1, например, через перекресток (3) необходимо, чтобы поступающие потоки автомобилей к этой вершине (3) (1, 3) и (2, 3) равнялись величине потока, вытекающего из этой вершины (3, 4), что можно записать (1,3) + (2,3) = (3,4) или (1,3) + (2,3)-(3,4) = 0. Аналогичные уравнения можно записать для остальных вершин сети. Поскольку задача заключается в определении максимально возможного потока в сети, то необходимо последовательно вычислить потоки через все разрезы и выбрать из них минимальный. Разрез АА на рис. 2.1 отделяет источник (1) от стока (4), вдан-ном случае вершину (4) от остальных вершин (1, 2, 3). Величина разреза определяется пропускной способностью входящих в него дуг (2, 3) и (3, 4) и соответственно равна С(2, 4) + С(3, 4) - 2 + 8 = 10. Затем можно определить все другие возможные варианты разрезов (В, В) и (С, С). Тогда величина максимального потока от источника к стоку равна величине минимального разреза: min[(A, A) (В, B), (С, С)]= min[l0; 19; 5] = 5. Приведенный вариант анализа фрагмента сети автомагистрали указывает на возможность применения приведенного принципа сохранения потока в коммерческой деятельности. Это позволит своевременно принимать оптимальные управленческие решения и облегчить оперативное вмешательство по регулированию не только автомобильных, но финансовых или товарных потоков. Пример. Построим разрезы для сети, представленные на рис. 2.2 для различных множеств Np: 1) Np = {s, 1,4,}, тогда = {2, 3, t}, следовательно, разрез Up = = {(s, 3); (1, 3); (1, 2); (4, t)} (рис. 4.3.2), таким образом, С -= (Np, ) = 10 + 4 + 3 + 9 = 26; 2) Np = {s, 3}, тогда = {1, 2, 4, t}, следовательно, разрез Uр = = {(s, 1); (3,4); (3,2)} (рис. 4.3.3), таким образом, С = (Np , ) = 5 + 7 + 2 = 14. Рис. 2.2 Ориентированная сеть Рис23. Разрез сети, величина разреза 26 Рис. 2.4. Разрез сети, величина разреза 14 На рисунках дуги разрезов выделены. Из рисунков видно, что после удаления дуг разрезов перестают существовать пути от входа сети s к выходу t. Разрезы имеют различные пропускные способности. Минимальным разрезом сети называется разрез, имеющий минимальную пропускную способность. Рассмотренные алгоритм и примеры моделирования позволяют решать аналогичные по своей природе задачи по бесперебойному снабжению потоками электричества, топлива (газа, мазута), воды, продовольственными и непродовольственными товарами населенных пунктов и таким образом предупредить появление критических ситуаций в городах и поселках нашей страны. Тема3 Методы решения сетевых задач 3.1. Построение максимального потока На практике часто возникают задачи определения максимального количества товара, которое может быть перевезено от производителя потребителю. Аналогичными являются задачи определения максимальной пропускной способности системы автомагистралей, определения максимального количества нефти или газа, передаваемых по трубопроводам, информации, пропускаемой по компьютерной или телефонной сети. Формально эти проблемы сводятся к задаче построения максимального потока в сети. Для их решения необходимо ввести несколько понятий. Пусть задана сеть S = (N, U) с множеством вершин N и множеством дуг U. Определение. Дуга ueU, соединяющая вершины i  N,j  N сети S, называется допустимой дугой, если она обладает одним из следующих свойств: 1) направление дуги совпадает с направлением потока, и значение потока по этой дуге меньше ее пропускной способности: и = (i, j), (u) < с(и); 2) направление дуги противоположного направлению потока, и величина потока отлична от нуля: u=(j,i), (u)>0. Дуги, обладающие первым свойством, называют увеличивающими; дуги, обладающие вторым свойством, — уменьшающими. Определение. Увеличивающей цепью, соединяющей вход и выход сети, называется простая цепь, все дуги которой являются допустимыми. Пример. Построим увеличивающую цепь для сети S = (N, U), представленной на рис. 3.1. Рис. 3.1. Построение увеличивающей цепи Над каждой дугой указана ее пропускная способность, в скобках — поток по этой дуге. Цепь (s, 1, 2, 4, t) является увеличивающей, так как все ее дуги — допустимые: - дуга (s, 1) — увеличивающая, так как она проходит по направлению потока, и поток по ней меньше ее пропускной способности: 6 < 9; - дуга (1,2) — также увеличивающая дуга: 3 < 6; - дуга (2,4) — уменьшающая, так как она проходит против потока и поток по ней 2 > 0; - дуга (4, t) — увеличивающая: 4 < 7. Построим увеличивающую цепь для сети, представленной на рис. 3.2. Рис. 3.2. Построение увеличивающей цепи Цепь (s, 3, 2, t) — увеличивающая, так как все ее дуги являются допустимыми увеличивающими дугами. Определение максимального потока основано на увеличении потока вдоль увеличивающей цепи на величину Д<р. Алгоритм построения максимального потока включает следующую последовательность: 1) задание начального значения потока. Удобно задавать нулевое начальное значение; 2) построение увеличивающей цепи от входа к выходу сети. Если такой цепи нет, то максимальный поток построен, и его величина в противном случае переходят к пункту 3; 3) увеличение вдоль построенной цепи значения потока на максимально возможную величину , при этом по каждой увеличивающей дуге поток увеличивается на , а по каждой уменьшающей дуге уменьшается на . Возврат к пункту 2. Пример. Определим максимальный поток для сети (см. рис. 3.1). Начальный поток в сети задан, следовательно, пункт 1 алгоритма выполнен. Увеличим поток вдоль цепи (s,l,2,4,t). Вдоль дуги (s, 1) поток можно увеличить на разницу между пропускной способностью этой дуги 9 и уже проходящим по ней потоком 6 (9 - 6 - 3). Вдоль дуги (1, 2) аналогичным образом поток можно увеличить на 3 (6 - 3). Дуга (2, 4) является уменьшающей. Максимальная величина, на которую можно уменьшить поток по ней, равна 2, т.е. значению уже проходящего потока. По дуге (4, г) поток можно увеличить на 3 (7 - 4). Таким образом, максимальная величина , на которую можно увеличить поток, составляет  = min(3, 3, 2, 3) = 2, при этом на каждой увеличивающей дуге поток увеличивается на эту величину, а по каждой уменьшающей — уменьшается. Новое значение потока записано в скобках над дугой (рис.3.3). Рис. 3.3. Построение максимального потока После такого перераспределения значение потока увеличилось на 2 и стало равным V=11(8 + 3 = 6 + 5), а условие сохранения потока в вершинах сети по-прежнему выполняется. Заметим, что если увеличить поток не на 2, а на 3, то на дуге (4, 2) получим отрицательное значение -1 (2 - 3), что противоречит свойству неотрицательности потока. Рассмотрим теперь цепь (s, 1, 2, t). Эта цепь увеличивающая, так как все дуги — допустимые. Поток вдоль этой цепи можно увеличить на  = min (9 - 8; 6 - 5; 10 - 5) = 1. Новое значение потока указано на рис. 4.6.3. Заметим, что если увеличить поток на 5, то поток по дугам (s, 1) и (1, 2) превзойдет пропускную способность этих дуг. Затем рассмотрим цепь (s, 3, 4, t):  = min (8 - 3; 4 - 3; 7 - 6) = 1. Больше увеличивающих цепей нет, следовательно, максимальный поток построен. Его величина: Vmax =11 + 1 + 1 = 9 + 4 = 6+7 = 13. Минимальный разрез АА, соответствующий этому потоку, содержит дуги: {(1,2); (1,4); (3,4)}, а его пропускная способность 6 + 3 + 4 = 13 соответствует величине максимального потока. Из примера следует, что значение , на которое увеличивается поток вдоль увеличивающей цепи, определяется следующим образом: Специалистам часто приходится изучать возможности сетей с незаданной жестко фиксированной ориентации, например, автомагистралей с двухсторонним движением с отсутствием сплошной разделительной полосы. Использование неориентированных сетей позволяет увеличить значение максимальных потоков по ним. Построить максимальный поток в этом случае можно по следующему алгоритму: 1) заменить каждое ребро сети, не выходящее из источника и не входящее в сток, двумя противоположно направленными дугами, имеющими ту же пропускную способность, что и заменяемое ребро; 2) перейти к алгоритму построения максимального потока для ориентированной сети. Пример. Построим максимальный поток для сети, представленной на рис. 3.4. Рис. 3.4. Построение максимального потока в ориентированной сети Начальное значение потока равно нулю V = 0. Увеличивающие цепи: 1) (s, 1, 2, t).  = min (8,4,10) = 4; 2) (s,1,3,4,t).  = min (8 - 4, 3, 2,9) = 2. Больше увеличивающих цепей построить нельзя. Построим теперь максимальный поток для неориентированной сети с той же структурой рис. 3.5. Рис. 3.5. Неориентированная сеть Заменяя ребра двумя противоположно направленными дугами, получаем следующую сеть рис. 3.6. Рис. 3.6. Построение максимального потока в неориентированной сети Увеличивающие цепи: l)(s, 1,2, t), = 4; 2)(s, 1,3, 5,*), = 3; 3)(s,3,2,t), = 2; 4)(s,3,4,t), = 2. Больше увеличивающих цепей не существует. Максимальный поток Vmax = 7 + 4 = 9 + 2 = 11. Оптимальная ориентация сети показана на рис. 3.7. Рис. 3.7. Оптимальная ориентация сети Метод ветвей и границ Существует достаточно большой класс задач, в которых дл* нахождения оптимального решения необходимо перебрать все возможные варианты решений по какому-либо критерию. Однако такой прямой перебор может занять очень много времени. Например, для выбора оптимальной последовательности проведения маркетинговых исследований группой из т специалистов разного профиля в п объектах рынка необходимо перебрать большое множество вариантов. В задаче коммивояжера для формирования оптимального маршрута объезда п городов необходимо выбрать один лучший из (n -1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтоно-ва цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева — связного графа, не содержащего циклов и петель. Процесс разбиения множества всех маршрутов на непересекающиеся подмножества в виде дерева представлен на рис. 3.8. Корень этого дерева объединяет все множество вариантов, а вершины дерева — это подмно-' жества частично упорядоченных вариантов решений. Рис. 3.8. Дерево ветвления маршрутов Вершина (i, j) соответствует подмножеству всех маршрутов, содержащих дугу (i,j), а вершина — подмножеству всех маршрутов, где эта дуга отсутствует. Процесс разбиения на эти подмножества можно рассматривать как ветвление дерева. Поэтому метод называется методом поиска по дереву решений, или методом ветвей и границ. Метод ветвей и границ представляет собой алгоритм направленного перебора множества вариантов решения задачи. Сущность этого метода состоит в том, что ветвятся от корня дерева не все вершины. В начале проводится оценка каждой вершины первого уровня, а затем ветвится та вершина, которая получает лучшую оценку (минимальную или максимальную) в соответствии с выбранным критерием. Однако вычислить точное значение критерия, не перебрав всех вариантов, невозможно. Чтобы избежать этой рутины, используют не точное значение критерия, а оценку снизу или сверху, которые называют нижней оценкой границы и верхней оценкой границы множества вариантов. При этом оценка вершины должна удовлетворять следующим требованиям: 1) оценка не должна быть больше (при минимизации) или меньше (при максимизации) минимального (максимального) значения функции для рассматриваемого множества; 2) оценка подмножества нижнего уровня не должна быть меньше (при минимизации) или больше (при максимизации) значения оценки подмножества более высокого уровня; 3) оценка единственного варианта решения на последнем уровне точно совпадает со значением критерия целевой функции решения. Цель ветвления заключается в том, что процесс разбиения на подмножества позволяет получить подмножество, содержащее единственный маршрут. Пары городов (звенья) маршрута фиксируются при движении по дереву в обратном направлении к начальной вершине. На каждом шаге итерации на основе сравнения нижних границ подмножеств ветвление выполняется только из вершины, имеющей меньшее значение нижней границы. Следует заметить, что оптимальный маршрут, представляющий собой гамильтонов цикл, можно найти, перебрав все возможные варианты. Однако с увеличением числа городов п количество возможных маршрутов (n - 1)! резко возрастает, поэтому вычислительные процедуры удобнее выполнять по методу ветвей и границ на компьютере. Решим задачу коммивояжера с исходными данными, записанными в табл. 1.1. Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент табл. 4.6.1. Таблица 3.1 i j 1 2 3 4 5 di 1  90 80 40 100 40 2 60  40 50 70 40 3 50 30  60 20 20 4 10 70 20  50 10 5 20 40 50 20  20 Затем вычесть его из элементов рассматриваемой строки. Во вновь полученной матрице табл. 3.2 в каждой строке будет в крайнем случае один ноль. Таблица 3.2 i j 1 2 3 4 5 1  90 80 40 100 2 60  40 50 70 3 50 30  60 20 4 10 70 20  50 5 20 40 50 20  di 10 Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце табл. 4.6.2 находим минимальный элемент Таким образом мы получим полностью редуцированную матрицу табл. 3.3, где величины di и dj называют константами приведения. Таблица 3.3 i j 1 2 3 4 5 di 1  90 80 40 100 40 2 60  40 50 70 40 3 50 30  60 20 20 4 10 70 20  50 10 5 20 40 50 20  20 di 10 140 Сумма констант приведения определяет нижнюю границу: Элемент матрицы dij соответствует расстоянию от пункта i до пункта j. Поскольку в матрице п городов, то D является матрицей пхп с неотрицательными элементами dij  0. Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город. Длина маршрута определяется выражением причем каждая строка и столбец входят в маршрут только один раз элементом dij. Определяем дугу, исключение которой максимально увеличило бы нижнюю границу, и разобьем все множество маршрутов относительно этой дуги на два подмножества (i, j) и рис. 4.6.8. С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на  и определяем для них сумму образовавшихся констант приведения, в табл. 4.6.3 они приведены в скобках. Набольшая сумма констант первого варианта приведения равна (40 + 0) - 40 для дуги (1,4), следовательно, множество разбивается на два подмножества {(1,4)} и {}. Исключение дуги (1,4) проводим путем замены элемента d1,4 = 0 на , после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества {}, в результате получим редуцированную матрицу, табл. 3.4. Таблица 3.4. i j 1 2 3 4 5 di 1   20 40 2 20  10 30 3 30  40 4 50 10  40 5 10 30  di 40 Нижняя граница гамильтоновых циклов этого подмножества H= 140 + 40 = 180. Включение дуги (1,4) проводится путем исключения всех элементов первой строки и четвертого столбца табл. 4.6.4, в которой элемент d4,1 = 0 заменяем на , для исключения образования негамильтонова цикла. В результате получим другую сокращенную матрицу (4x4) табл. 4.6.5, которая подлежит операции приведения. Таблица 3.5 i j 1 2 3 5 di 2 20  30 3 30  4  50 10 40 10 5 10 30  di 10 Сумма констант приведения сокращенной матрицы После операции приведения сокращенная матрица будет иметь вид табл. 3.6. Таблица 3.6 i j 1 2 3 5 2 20  0(20) 30 3 30 0(10)  0(30) 4  40 0(40) 30 5 0(30) 10 30  Нижняя граница длин гамильтоновых циклов подмножества {(1,4)} равна: H(1,4) = 140 + 10 - 150 < 180. Поскольку граница этого подмножества {(1,4)} меньше, чем подмножество {}, то оно и подлежит ветвлению. Затем опять определяем дугу, исключение которой увеличило бы нижнюю границу. С этой целью определяем сумму констант приведения (указаны в скобках) табл. 4.6.6 для нулевых клеток, заменяя их поочередно на . Максимальная сумма принадлежит четвертому варианту расчета констант di + dj = 40 + 0 = 40 к дуге (4,3). Следовательно, разбиваем множество маршрутов {(1,4)} на два подмножества {(l,4),)} и {(1,4); (4,3)}. Затем заменяем соответствующий элемент матрицы а43=0 на  и формируем матрицу приведения. Продолжая дальше операции в соответствии с указанным алгоритмом решения задачи в конечном итоге получаем сокращенную матрицу табл. 3.7а. Таблица 3.7а i j 2 5 3  5  В соответствии с этой матрицей включаем в гамильтонов маршрут дуги (3,5) и (5,2). В соответствии с деревом ветвлений гамильтонов маршрут образуют дуги (1,4), (4,3), (2,1), (3,5), (5,2). Последовательность объезда городов (рис. 3.2) коммивояжером 1-4-3-5-2-1 представлена в табл. 3.76 и на рис. 3.9. Длина маршрута равна F(Mk) = 180 совпадает с нижней границей подмножества. Таблица 3.76 i j 1 2 3 4 5 1 1 2 1 3 1 4 1 5 1 Рис. 3.9. Гамильтонов цикл коммивояжера Алгоритм решения задач методом ветвей и границ включает следующую последовательность. 1. Проводим операцию приведения матрицы расстояний по строкам и столбцам, находим нижнюю границу всего множества маршрутов: Н = 2. Для каждой клетки dij = 0 заменяем поочередно нуль на , находим сумму новых констант приведения: которые записываем в клетке в скобках рядом с нулем. 3. Выбираем дугу исключения (i,j) из множества по максимальной величине суммы констант приведения путем замены элемента матрицы dij = . В результате будет образовано подмножество маршрутов {(i,j)}. 4. Приводим полученную матрицу расстояний и определяем нижнюю границу этого подмножества маршрутов H 5. Включаем дугу (i,y) в маршрут путем исключения i-й строки и j-го столбца из матрицы и замены симметричного элемента матрицы dji = . 6. Приводим сокращенную матрицу и определяем нижнюю границу подмножества H. 7. Сравниваем нижние границы подмножеств {(i,j)} и {} и подвергаем подмножество, имеющее меньшее значение нижней границы, ветвлению. 8. Определяем гамильтонов цикл при получении матрицы 2x2. 4.6.3. Методы сетевого планирования Современное разнообразие, многосвязность и взаимозависимость задач коммерческой деятельности вызывают большие трудности при планировании реальных сроков их выполнения. Традиционные, сложившиеся методы планирования и управления иногда не обеспечивают выполнение операций в коммерческой деятельности в намеченные сроки и не позволяют определить оптимальные объемы ресурсов, а как известно «время - деньги». Необходимым свойством системы планирования и управления работами является способность оценить текущее состояние, учесть возможное состояние в будущем, предсказать дальнейший ход работ и таким образом предупредить от возможных ошибок, заранее оперативно воздействовать на ход комплекса работ в сжатые сроки и с наименьшими затратами. Наиболее эффективны в настоящее время сетевые методы и модели, на базе которых созданы методы сетевого планирования и управления (СПУ). Такие системы предназначены для управления объектами особого типа и сложности, получившими название комплексов взаимосвязанных работ, коммерческих операций, разработок, которые требуют четкой координации взаимодействия множества исполнителей. СПУ позволяет осуществить надежную координацию всех звеньев и подразделений, участвующих в сложном комплексе. В таких случаях СПУ, по существу, является единственно возможным методом научного планирования и управления по выполнению больших масштабов работ с высокой вероятностью соблюдения заданных сроков их реализации, что является их главным достоинством. Особенность СПУ заключается в том, что деятельность всех коллективов исполнителей рассматривается в целом как единый комплекс взаимосвязанных и взаимозависимых операций, направленных на достижение общей конечной цели. Здесь используется информационно-динамическая модель особого вида, так называемая сетевая модель логико-математического описания, позволяющая алгоритмизировать расчеты параметров этого процесса: продолжительности, трудоемкости, стоимости и т.д. Системы рассчитаны на использование компьютерных систем обработки исходных и оперативных данных для расчета контролируемых показателей и получения необходимых аналитических и отчетных сводок. В СПУ применяются графическое изображение или аналитическая запись плана работ, в которых отражается их логическая последовательность, взаимосвязь, продолжительность, стоимость и др. Они создаются с целью оптимизации разработанного плана и текущего управления ходом работ путем периодического сбора информации и соответствующей корректировки плана. Эти системы являются комплексом графических и расчетных методов, организационных мероприятий и контрольных приемов, обеспечивающих моделирование и динамическую перестройку планов в коммерческой деятельности. Причем графические методы дают наиболее наглядно-обозримую информацию о ходе комплекса работ как в целом, так и в деталях. В этом случае системой СПУ осуществляется управление по отклонениям, т.е. сообщаются лишь необходимые сведения только изменившихся, а не плановых состояний работ, поскольку избыточная информация затрудняет процесс управления. В целом система СПУ включает сбор, переработку информации, поступающей от управляемого объекта, выработку решений на ее основе и передачу распоряжений на управляемый объект. СПУ концентрируют внимание руководителей на самых важных работах комплекса, отсеивая второстепенные. Так, при сложившихся методах управления в поле зрения руководителя обычно находится до 70% работ, что, безусловно, затрудняет принятие им эффективных решений. Разработка СПУ позволила установить, что практически лишь около 10% работ от всего комплекса существенно влияют на ход выполнения работ. При этом время, затрачиваемое руководителями на решение вопросов управления, сокращается на 50-60%. Кроме того, все участники работ находятся в объективно равных условиях осведомленности, что оказывает влияние на успех завершения всего комплекса работ в намеченные сроки. Преимущество СПУ заключается в следующем: а) концентрирует внимание руководителей на небольшом числе работ и исполнителей; б) устанавливает четкую взаимосвязь между исполнителями, обеспечивая тесное организационное единство; в) позволяет в любой момент времени располагать исчерпывающей информацией; г) обеспечивает непрерывность управления ходом работ, своевременность принятия решений, оперативность вмешательства; д) позволяет рационально маневрировать выделенными ресурсами; е) дает большую экономию времени, средств, энергии, материалов, и т.д.; ж) дисциплинирует исполнителей, создается объективная картина качества работ, доступная каждому, исключается штурмовщина; з) создается возможность выполнения вычислительных работ на компьютере. В настоящее время методами СПУ решается около 14% задач общего объема применяемых математических методов. Работы по использованию и развитию СПУ получили широкое распространение в разных отраслях народного хозяйства нашей страны и за рубежом, уже накоплен большой опыт и сложилась своя история. Например, в США в конце 50-х годов появилась система CRM - метод критического пути - для управления строительными работами, затем PERT - метод оценки и обзора программ при разработке ракетного вооружения «Поларис». В России работы по применению методов и моделей СПУ начались с 1961 г. В процессе развития появились различные целевые системы: ПУСК-планирование, управление созданием корабля; СУР — система управления разработками; АСОР — автоматизированная система организации работ; ЦПК — централизованное планирование и контроль и др. В зависимости от масштаба комплекса работ различают такие системы: с числом событий в сети 10-12 тыс. — большие разработки, средние — 1,5-10 тыс. и малые — до 1,5 тыс. В случае небольших разработок от нескольких десятков событий до 100 используются ручные методы расчета и анализа, в остальных случаях — по специальным компьютерным программам. Методы и модели СПУ могут с успехом применяться в коммерческой деятельности при выполнении различных комплексов работ: проведение текущего или капитального ремонта; реконструкции коммерческих торговых предприятий; подготовке и проведении оптовых и розничных ярмарок; разработка плана коммерческой деятельности; заготовка, переработка и закладка пло-дово-овощной продукции на длительное хранение; перевод предприятий торговли на самообслуживание; оперативная реконструкция секций супермаркетов; строительство универсальных оптовых предприятий; разработка плана развития торговой сети; планирование торговой деятельности; составление бухгалтерского отчета; поставка товаров покупателям; заключение договоров на поставку; открытие нового торгового предприятия, а также многих комплексов финансово-коммерческих операций. Подготовка задач к решению. На предварительном этапе сетевого моделирования определяется структура комплекса работ, последовательность выполнения отдельных операций, состав и взаимосвязь организаций соисполнителей, ориентировочные сроки поставок, потребность в основных ресурсах и ассигнованиях. Внешние связи плана работ торгового предприятия согласовываются со всеми организациями-соисполнителями. Затем переходят к исходному планированию по одному из трех вариантов. В первом случае проводят расчленение комплекса работ централизованно «сверху вниз» на составляющие элементы, на базе которых ответственным исполнителям выдаются задания. Второй вариант построения сетевой модели «снизу вверх» базируется на сшивании, т.е. соединении нескольких первичных сетевых графиков, полученных от ответственных исполнителей, в одну сеть. Третий, наиболее распространенный способ «сверху вниз»-«снизу вверх» включает поочередное членение комплекса работ и укрупнение с координацией на основе первичных графиков ответственных исполнителей, детально представляющих специфику торговых операций. Ответственные исполнители в системах СПУ — это специалисты, осуществляющие руководство работами по отдельным частям комплекса и несущие за них персональную ответственность. Более наглядное представление о содержании работ в целом и в деталях дает построение дерева комплекса работ. Правила построения сетевых моделей Наиболее распространенным способом изображения СПУ являются сетевые модели в терминах работ и событий, где работы изображаются стрелками, а события — кружками (см. рис. 3.2). При построении сетевых моделей следует придерживаться следующих основных правил: 1. Строится трафарет событий (рис. 3.10). 2. Наносятся на трафарет в соответствии со структурно-временной табл. 3.2 последовательно все работы. 3. Просматриваются возможные варианты следования событий и работ, их табличная запись и формы изображения приведены на рис. 3.11. 4. Всем стрелкам сетевого графика задают общее направление слева направо. 5. Не должно быть стрелок, которые ниоткуда не выходят и никуда не входят. Рис 3.12 6. Между одной парой событий можно изобразить только одну работу. 7. При необходимости изображения двух параллельно выполненных работ между двумя событиями 5 и 7 (рис. 3.12а) вводят дополнительное промежуточное событие 6 и фиктивную работу (6, 7) с нулевой продолжительностью (рис. 3.126). 8. Из сети исключают тупиковые события, от которых не начинается ни одна работа, за исключением завершающего события комплекса. 9. Проводят преобразование геометрии взаимного расположения работ и событий к виду, удобному для восприятия в целом, например устраняют пересечения работ. 10. Нумерацию событий проводят последовательно слева на право и сверху вниз. Построенный по исходным данным табл. 4.5.2 и перечисленным правилам расположения и взаимосвязи работ и событий (рис. 3.13) представляют собой сетевую модель задачи по переводу коммерческого предприятия на самообслуживание. В случае больших комплексов работ сначала строят частные сетевые графики ответственные исполнители, а затем формируют сводную модель комплекса путем их сшивания. Установлено, что на листе бумаги размером 1,5x2 м можно разместить сетевой график, включающий до 1000 событий. Рис. 3.13. Сетевая модель по переводу коммерческого предприятия на самообслуживание Следует учитывать, что сетевые модели большого объема трудно обозримы. В связи с этим проводят укрупнение сетевой модели путем устранения менее важных фрагментов и, следовательно, уменьшения числа изображаемых событий и работ, оставляя только наиболее значимые. Параметры сетевых моделей и методы их расчета Основные параметры сетевых моделей — это критический путь, резервы времени событий, работ и путей. Кроме этих показателей имеется ряд вспомогательных, которые являются исходными для получения дополнительных характеристик по анализу и оптимизации сетевого плана комплекса работ. При расчетах применяют следующие обозначения параметров сетевой модели: tjp — ранний срок свершения j-го события; tjn — поздний срок свершения j-го события; Rj — резерв времени на свершение j-го события; tijP.H — ранний срок начала работы (i,j); tijP.O — ранний срок окончания работы (i,j); tijП.H — поздний срок начала работы (i,j); tijП.О — поздний срок окончания работы (i,j); rijП — полный резерв времени работы (i,j); rijC.B — свободный резерв времени работы (i,j)', kijH — коэффициент напряженности работы (i,j); ТП — продолжительность пути LП; TП = t(LП); TКР — продолжительность критического пути LКР; R(Lп) — полный резерв времени пути Lп. Рассмотрим определения и модели расчета параметров сетевой модели. Ранний срок свершения j-го события tjp — наиболее ранний (минимальный) из возможных моментов наступления данного события при заданной продолжительности работ. Поздний срок свершения j-го события tjn — наиболее поздний (максимальный) из допустимых моментов наступления данного события, при котором еще возможно выполнение всех последующих работ в установленный срок. Резерв времени на свершение j-го события Rj — это промежуток времени, на который может быть отсрочено наступление события j без нарушения сроков завершения всего комплекса, определяется как разность между поздним tjn и ранним tjp сроками наступления события Rj = tjn - tjp. Ранний срок начала работы tijP.H — наиболее ранний (минимальный) из возможных моментов начала данной работы при заданной продолжительности работ. Он совпадает с ранним сроком наступления ее начального события: tijP.H= tjp Ранний срок окончания работы tijP.O — наиболее ранний (минимальный) из возможных моментов окончания данной работы при заданной продолжительности работ. Он превышает ранний срок наступления ее события i на величину продолжительности работы: tijP.O= tiP+tij Поздний срок начала работы tijП.H — наиболее поздний (максимальный) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок: tijП.H= tjП-tij Поздний срок окончания работы tijП.О — наиболее поздний (максимальный) из допустимых моментов окончания данной работы, при котором еще возможно выполнение последующих работ в установленный срок: tijП.О= tjП Полный резерв времени работы (i,j) rijП — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы ttj без изменения общего срока выполнения комплекса: rijП = tjП -tiP-tij Свободный резерв времени работы (i,j) rijC.B — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки: rijC.B= tjP- tiP-tij Полный резерв времени пути R(Lп), — показывает, на сколько могут быть увеличены продолжительности всех работ в сумме пути Ln относительно критического пути LKP: R(Lп)=t(LKP)-t(LП)=TKP-TП Коэффициент напряженности работы (i,j) kijH — характеризует напряженность по срокам выполнения работы (i,j) и определяется по формуле где t(Lmax ) — длительность максимального из некритических путей, проходящих через работу (i,j); t' (Lmax ) — продолжительность части критических работ, входящих в рассматриваемый путь Lmax. Чем ближе коэффициент напряженности к 1,0, тем сложнее выполнять эту работу в установленные сроки. Методы расчета параметров сетевой модели делятся на две группы. В первую группу входят аналитические методы, которые включают вычисления по формулам непосредственно на сетевом графике, табличный и матричный методы. Ко второй группе относятся методы основанные на теории статистического моделирования, которые целесообразно применять при расчете стохастических сетей с очень большим разбросом возможных сроков выполнения работ. В качестве примера рассмотрим из первой аналитической группы табличный метод расчета параметров. В этом случае заполнение табл. 4.6.8 производится последовательно по следующим правилам: а) графы 1 и 3 заполняются на основе исходных данных, представленных в структурно-временной табл. 3.2; Таалица 3.8 Работа (i.j) Количество пред- шеств. работ Продолжи- тель-ность tij Сроки выполнения работ Резервы времени ранние поздние работ событий Ri начала tijP.H окончания tijP.O начала tijП.H окончания tijП.O полный tijП свободный tijС.В 1 2 3 4 5 6 7 8 9 10 (0,1) 15 15 15 (1,2) 1 16 15 31 15 31 (1,3) 1 6 15 21 22 28 7 7 (2,4) 1 6 31 37 31 37 (3,5) 1 5 21 26 28 33 7 7 (4,6) 1 8 37 45 37 45 (5,6) 1 6 26 32 39 45 13 13 (5,8) 1 14 26 40 33 47 7 7 (5,7) 1 8 26 34 35 43 9 9 (6,8) 2 2 45 47 45 47 (7,8) 1 4 34 38 43 47 9 9 (8,9) 3 3 37 50 47 50 б) в графе 2 записывается количество предшествующих работ по сетевому графику или определяется из графы 1 по числу работ, имеющих второй цифрой в коде ту, с которой начинается данная работа. Например, в графе 1 имеются три работы, оканчивающиеся на цифру 8: (5,8); (6,8); (7,8), поэтому работа (8,9) имеет три предшествующие работы; г) в графе 4 раннее начало работ, выходящих из исходного события, равно нулю, а раннее окончание этих работ равно их продолжительности (гр. 5). Раннее начало последующих работ определяется путем выбора максимального из сроков раннего окончания предшествующих работ. Количество сравниваемых сроков равно количеству предшествующих работ графы 2. Раннее начало последующих работ можно определить после того, как найдено раннее окончание предшествующих. В свою очередь, раннее окончание каждой работы находится как сумма величин раннего начала и продолжительности данной работы; г) продолжительность критического пути определяется после заполнения граф 4 и 5 как максимальная величина из сроков раннего окончания работ, которые ведут к завершающему событию 9; д) найденная величина критического пути Tкр = 50 дням заносится в графу 7 для всех работ, ведущих к завершающему событию. Затем заполнение ведется снизу вверх. Находятся все работы, следующие за рассматриваемой, и определяются разности между поздним окончанием этих работ и их продолжительнос-тями. Минимальная из величин заносится в графу 7; е) в графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3); ж) в графе 8 полный резерв времени работы определяется разностью между значениями граф 7 и 5. Если он равен нулю, то работа является критической; з) в графе 10 резерв времени событий j определяется как разность позднего окончания работы, заканчивающегося событием j графы 7, и ранним началом работы, начинающимся событием j; и) значение свободного резерва времени работы определяется как разность значений графы 10 и данных графы 8 и указывают на расположение резервов, необходимых для оптимизации. Пользуясь полученными значениями параметров работ по переводу предприятия торговли на самообслуживание табл. 4.6.8, можно перейти к анализу сетевой модели, а затем провести оптимизацию. Анализ сетевых моделей Анализ сетевой модели проводим с целью выявления резервов и «узких мест». Табличный метод расчета параметров табл. 3.8 позволяет решить эту задачу. Однако, большую наглядность все же дает графический метод анализа. Соединение различных методов сетевого моделирования позволяет объединить их преимущества. Следует помнить, что обнаруженные резервы позволяют более гибко управлять комплексом работ путем их разумного перераспределения с одних работ на другие, не произвольно, а по специальным методам оптимизации. Анализ сетевой модели рис. 3.13 начинаем с определения минимального времени выполнения всего комплекса работ. Для этой цели проследим все возможные пути перехода из одного события (0) к завершающему (9). Таких путей четыре: L1 = [(0,1) (1,2) (2,4) (4,6) (6,8) (8,9)] L2 - [(0,1) (1,3) (3,5) (5,6) (6,8) (8,9)] L3 = [(0,1) (1,3) (3,5) (5,6) (8,9)] L4 - [(0,1) (1,3) (3,5) (5,7) (7,8) (8,9)] Определим длительность этих путей: Т1 = t(L1) = t0,1 + t1,2 + t2,4 + f4,6+ t6,8 + t8,9 = 16 + 16 + 6 + 8 + 2 + 3 = 50 дн. Т2 = t(L2) = t0,1 + t1,3 + t3,5 + f5,6+ t6,8 + t8,9 =15 + 6 + 5 + 6 + 2 + 3=37дн. Т3 = t(L3) = t0,1 + t1,3 + t3,5 + f5,6+ t8,9 = 15 + 6 + 5 + 14 + 3 = 43 дн. Т4 = t(L4) = t0,1 + t1,3 + t3,5 + f5,7+ t7,8 + t8,9 = 15+ 6 + 5 + 8 + 4 + 3 = 41 дн. Поскольку многие из работ, лежащих на этих путях, выполняются параллельно, общий срок перевода коммерческого предприятия на самообслуживание будет определяться путем максимальной продолжительности, называемым критическим: ТКР = max {t(Li)} = 50 дн. Длительность пути L2 составляет t(L2) = 37 дней минимальна, однако не позволяет выполнить все работы комплекса. Длительность пути L2 составляет t(L2) - 50 дней, однако за это время все работы комплекса могут быть выполнены. Следовательно, минимальное время, за которое может быть выполнен весь комплекс работ, составляет 50 дней, следовательно, путь L1 является критическим. Теперь определим полные резервы времени по всем путям: R(L1)=TKP-T1=0 R(L2)=TKP-T2= 13 дн. R(L3)=TKP-T3 = 7дн. R(L4)=TKP-T4=9дн. В пределах имеющихся резервов времени с выполнением некоторых работ можно не спешить, и общий срок выполнения комплекса работ не увеличится. Если же длительность выполнения любой из работ критического пути увеличилась, то общий срок выполнения комплекса неизбежно возрастет. Для наглядного выявления мест расположения резервов времени построим сетевой график работ в масштабе времени рис. 3.13. Построение начинается с критического пути LKP в соответствии с правилами сетевого моделирования по графику событий с учетом изображения длительностей работ tij в масштабе времени по оси абсцисс. По оси ординат длины стрелок выбираются из соображений удобства восприятия топологии сети в целом. Этим объясняется большая длина стрелки работы (6,8) в сравнении с работой (4,6), хотя по масштабу времени длительность t4,6 больше t6,8. Длительность всех остальных путей T2, Т3, Т4 меньше, поэтому вводим фиктивные события 5', 8', 7' и фиктивные работы (5',6), (8',8), (7',8) с нулевой продолжительностью. В результате мы получили полную картину расположения мест свободных резервов времени работ r5,6C.B =13 дням, r5,8C.B = 7 дням r7,8C.B =9 дням. Наиболее напряженными являются Рис. 3.13. Сетевой график работ в масштабе времени работы критического пути L1, которые не имеют резервов и поэтому являются «узкими местами» комплекса работ. Таким образом, в результате анализа сетевой модели мы получили все необходимые данные для проведения оптимизации. Наличие резервов позволит провести оптимизацию сетевого графика путем лучшего перераспределения выделенных ресурсов и построить более экономный план, который даст возможность выполнить весь комплекс работ за меньшее время. Тема 4 Методы сетевого планирования Современное разнообразие, многосвязность и взаимозависимость задач коммерческой деятельности вызывают большие трудности при планировании реальных сроков их выполнения. Традиционные, сложившиеся методы планирования и управления иногда не обеспечивают выполнение операций в коммерческой деятельности в намеченные сроки и не позволяют определить оптимальные объемы ресурсов, а как известно «время - деньги». Необходимым свойством системы планирования и управления работами является способность оценить текущее состояние, учесть возможное состояние в будущем, предсказать дальнейший ход работ и таким образом предупредить от возможных ошибок, заранее оперативно воздействовать на ход комплекса работ в сжатые сроки и с наименьшими затратами. Наиболее эффективны в настоящее время сетевые методы и модели, на базе которых созданы методы сетевого планирования и управления (СПУ). Такие системы предназначены для управления объектами особого типа и сложности, получившими название комплексов взаимосвязанных работ, коммерческих операций, разработок, которые требуют четкой координации взаимодействия множества исполнителей. СПУ позволяет осуществить надежную координацию всех звеньев и подразделений, участвующих в сложном комплексе. В таких случаях СПУ, по существу, является единственно возможным методом научного планирования и управления по выполнению больших масштабов работ с высокой вероятностью соблюдения заданных сроков их реализации, что является их главным достоинством. Особенность СПУ заключается в том, что деятельность всех коллективов исполнителей рассматривается в целом как единый комплекс взаимосвязанных и взаимозависимых операций, направленных на достижение общей конечной цели. Здесь используется информационно-динамическая модель особого вида, так называемая сетевая модель логико-математического описания, позволяющая алгоритмизировать расчеты параметров этого процесса: продолжительности, трудоемкости, стоимости и т.д. Системы рассчитаны на использование компьютерных систем обработки исходных и оперативных данных для расчета контролируемых показателей и получения необходимых аналитических и отчетных сводок. В СПУ применяются графическое изображение или аналитическая запись плана работ, в которых отражается их логическая последовательность, взаимосвязь, продолжительность, стоимость и др. Они создаются с целью оптимизации разработанного плана и текущего управления ходом работ путем периодического сбора информации и соответствующей корректировки плана. Эти системы являются комплексом графических и расчетных методов, организационных мероприятий и контрольных приемов, обеспечивающих моделирование и динамическую перестройку планов в коммерческой деятельности. Причем графические методы дают наиболее наглядно-обозримую информацию о ходе комплекса работ как в целом, так и в деталях. В этом случае системой СПУ осуществляется управление по отклонениям, т.е. сообщаются лишь необходимые сведения только изменившихся, а не плановых состояний работ, поскольку избыточная информация затрудняет процесс управления. В целом система СПУ включает сбор, переработку информации, поступающей от управляемого объекта, выработку решений на ее основе и передачу распоряжений на управляемый объект. СПУ концентрируют внимание руководителей на самых важных работах комплекса, отсеивая второстепенные. Так, при сложившихся методах управления в поле зрения руководителя обычно находится до 70% работ, что, безусловно, затрудняет принятие им эффективных решений. Разработка СПУ позволила установить, что практически лишь около 10% работ от всего комплекса существенно влияют на ход выполнения работ. При этом время, затрачиваемое руководителями на решение вопросов управления, сокращается на 50-60%. Кроме того, все участники работ находятся в объективно равных условиях осведомленности, что оказывает влияние на успех завершения всего комплекса работ в намеченные сроки. Преимущество СПУ заключается в следующем: а) концентрирует внимание руководителей на небольшом числе работ и исполнителей; б) устанавливает четкую взаимосвязь между исполнителями, обеспечивая тесное организационное единство; в) позволяет в любой момент времени располагать исчерпывающей информацией; г) обеспечивает непрерывность управления ходом работ, своевременность принятия решений, оперативность вмешательства; д) позволяет рационально маневрировать выделенными ресурсами; е) дает большую экономию времени, средств, энергии, материалов, и т.д.; ж) дисциплинирует исполнителей, создается объективная картина качества работ, доступная каждому, исключается штурмовщина; з) создается возможность выполнения вычислительных работ на компьютере. В настоящее время методами СПУ решается около 14% задач общего объема применяемых математических методов. Работы по использованию и развитию СПУ получили широкое распространение в разных отраслях народного хозяйства нашей страны и за рубежом, уже накоплен большой опыт и сложилась своя история. Например, в США в конце 50-х годов появилась система CRM - метод критического пути - для управления строительными работами, затем PERT - метод оценки и обзора программ при разработке ракетного вооружения «Поларис». В России работы по применению методов и моделей СПУ начались с 1961 г. В процессе развития появились различные целевые системы: ПУСК-планирование, управление созданием корабля; СУР — система управления разработками; АСОР — автоматизированная система организации работ; ЦПК — централизованное планирование и контроль и др. В зависимости от масштаба комплекса работ различают такие системы: с числом событий в сети 10-12 тыс. — большие разработки, средние — 1,5-10 тыс. и малые — до 1,5 тыс. В случае небольших разработок от нескольких десятков событий до 100 используются ручные методы расчета и анализа, в остальных случаях — по специальным компьютерным программам. Методы и модели СПУ могут с успехом применяться в коммерческой деятельности при выполнении различных комплексов работ: проведение текущего или капитального ремонта; реконструкции коммерческих торговых предприятий; подготовке и проведении оптовых и розничных ярмарок; разработка плана коммерческой деятельности; заготовка, переработка и закладка пло-дово-овощной продукции на длительное хранение; перевод предприятий торговли на самообслуживание; оперативная реконструкция секций супермаркетов; строительство универсальных оптовых предприятий; разработка плана развития торговой сети; планирование торговой деятельности; составление бухгалтерского отчета; поставка товаров покупателям; заключение договоров на поставку; открытие нового торгового предприятия, а также многих комплексов финансово-коммерческих операций. Подготовка задач к решению. На предварительном этапе сетевого моделирования определяется структура комплекса работ, последовательность выполнения отдельных операций, состав и взаимосвязь организаций соисполнителей, ориентировочные сроки поставок, потребность в основных ресурсах и ассигнованиях. Внешние связи плана работ торгового предприятия согласовываются со всеми организациями-соисполнителями. Затем переходят к исходному планированию по одному из трех вариантов. В первом случае проводят расчленение комплекса работ централизованно «сверху вниз» на составляющие элементы, на базе которых ответственным исполнителям выдаются задания. Второй вариант построения сетевой модели «снизу вверх» базируется на сшивании, т.е. соединении нескольких первичных сетевых графиков, полученных от ответственных исполнителей, в одну сеть. Третий, наиболее распространенный способ «сверху вниз»-«снизу вверх» включает поочередное членение комплекса работ и укрупнение с координацией на основе первичных графиков ответственных исполнителей, детально представляющих специфику торговых операций. Ответственные исполнители в системах СПУ — это специалисты, осуществляющие руководство работами по отдельным частям комплекса и несущие за них персональную ответственность. Более наглядное представление о содержании работ в целом и в деталях дает построение дерева комплекса работ. Правила построения сетевых моделей Наиболее распространенным способом изображения СПУ являются сетевые модели в терминах работ и событий, где работы изображаются стрелками, асобытия — кружками (см. рис. 3.2). При построении сетевых моделей следует придерживаться следующих основных правил: 1. Строится трафарет событий (рис. 4.1). 2. Наносятся на трафарет в соответствии со структурно-временной табл. 4.5.2 последовательно все работы. 3. Просматриваются возможные варианты следования событий и работ, их табличная запись и формы изображения приведены на рис. 4.6.11. 4. Всем стрелкам сетевого графика задают общее направление слева направо. 5. Не должно быть стрелок, которые ниоткуда не выходят и никуда не входят. 6. Между одной парой событий можно изобразить только одну работу. 7. При необходимости изображения двух параллельно выполненных работ между двумя событиями 5 и 7 (рис. 4.6.12а) вводят дополнительное промежуточное событие 6 и фиктивную работу (6, 7) с нулевой продолжительностью 8. Из сети исключают тупиковые события, от которых не начинается ни одна работа, за исключением завершающего события комплекса. 9. Проводят преобразование геометрии взаимного расположения работ и событий к виду, удобному для восприятия в целом, например устраняют пересечения работ. 10. Нумерацию событий проводят последовательно слева на право и сверху вниз. Построенный по исходным данным табл. 4..2 и перечисленным правилам расположения и взаимосвязи работ и событий (рис. 4.3) представляют собой сетевую модель задачи по переводу коммерческого предприятия на самообслуживание. В случае больших комплексов работ сначала строят частные сетевые графики ответственные исполнители, а затем формируют сводную модель комплекса путем их сшивания. Установлено, что на листе бумаги размером 1,5x2 м можно разместить сетевой график, включающий до 1000 событий. Рис. 4.3. Сетевая модель по переводу коммерческого предприятия на самообслуживание Следует учитывать, что сетевые модели большого объема трудно обозримы. В связи с этим проводят укрупнение сетевой модели путем устранения менее важных фрагментов и, следовательно, уменьшения числа изображаемых событий и работ, оставляя только наиболее значимые. Параметры сетевых моделей и методы их расчета Основные параметры сетевых моделей — это критический путь, резервы времени событий, работ и путей. Кроме этих показателей имеется ряд вспомогательных, которые являются исходными для получения дополнительных характеристик по анализу и оптимизации сетевого плана комплекса работ. При расчетах применяют следующие обозначения параметров сетевой модели: tjp — ранний срок свершения j-го события; tjn — поздний срок свершения j-го события; Rj — резерв времени на свершение j-го события; tijP.H — ранний срок начала работы (i,j); tijP.O — ранний срок окончания работы (i,j); tijП.H — поздний срок начала работы (i,j); tijП.О — поздний срок окончания работы (i,j); rijП — полный резерв времени работы (i,j); rijC.B — свободный резерв времени работы (i,j)', kijH — коэффициент напряженности работы (i,j); ТП — продолжительность пути LП; TП = t(LП); TКР — продолжительность критического пути LКР; R(Lп) — полный резерв времени пути Lп. Рассмотрим определения и модели расчета параметров сетевой модели. Ранний срок свершения j-го события tjp — наиболее ранний (минимальный) из возможных моментов наступления данного события при заданной продолжительности работ. Поздний срок свершения j-го события tjn — наиболее поздний (максимальный) из допустимых моментов наступления данного события, при котором еще возможно выполнение всех последующих работ в установленный срок. Резерв времени на свершение j-го события Rj — это промежуток времени, на который может быть отсрочено наступление события j без нарушения сроков завершения всего комплекса, определяется как разность между поздним tjn и ранним tjp сроками наступления события Rj = tjn - tjp. Ранний срок начала работы tijP.H — наиболее ранний (минимальный) из возможных моментов начала данной работы при заданной продолжительности работ. Он совпадает с ранним сроком наступления ее начального события: tijP.H= tjp Ранний срок окончания работы tijP.O — наиболее ранний (минимальный) из возможных моментов окончания данной работы при заданной продолжительности работ. Он превышает ранний срок наступления ее события i на величину продолжительности работы: tijP.O= tiP+tij Поздний срок начала работы tijП.H — наиболее поздний (максимальный) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок: tijП.H= tjП-tij Поздний срок окончания работы tijП.О — наиболее поздний (максимальный) из допустимых моментов окончания данной работы, при котором еще возможно выполнение последующих работ в установленный срок: tijП.О= tjП Полный резерв времени работы (i,j) rijП — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы ttj без изменения общего срока выполнения комплекса: rijП = tjП -tiP-tij Свободный резерв времени работы (i,j) rijC.B — максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы при условии, что все события сети наступают в свои ранние сроки: rijC.B= tjP- tiP-tij Полный резерв времени пути R(Lп), — показывает, на сколько могут быть увеличены продолжительности всех работ в сумме пути Ln относительно критического пути LKP: R(Lп)=t(LKP)-t(LП)=TKP-TП Коэффициент напряженности работы (i,j) kijH — характеризует напряженность по срокам выполнения работы (i,j) и определяется по формуле где t(Lmax ) — длительность максимального из некритических путей, проходящих через работу (i,j); t' (Lmax ) — продолжительность части критических работ, входящих в рассматриваемый путь Lmax. Чем ближе коэффициент напряженности к 1,0, тем сложнее выполнять эту работу в установленные сроки. Методы расчета параметров сетевой модели делятся на две группы. В первую группу входят аналитические методы, которые включают вычисления по формулам непосредственно на сетевом графике, табличный и матричный методы. Ко второй группе относятся методы основанные на теории статистического моделирования, которые целесообразно применять при расчете стохастических сетей с очень большим разбросом возможных сроков выполнения работ. В качестве примера рассмотрим из первой аналитической группы табличный метод расчета параметров. В этом случае заполнение табл. 4.6.8 производится последовательно по следующим правилам: а) графы 1 и 3 заполняются на основе исходных данных, представленных в структурно-временной табл. 4.1; Таалица 4.1 Работа (i.j) Количество пред- шеств. работ Продолжи- тель-ность tij Сроки выполнения работ Резервы времени ранние поздние работ событий Ri начала tijP.H окончания tijP.O начала tijП.H окончания tijП.O полный tijП свободный tijС.В 1 2 3 4 5 6 7 8 9 10 (0,1) 15 15 15 (1,2) 1 16 15 31 15 31 (1,3) 1 6 15 21 22 28 7 7 (2,4) 1 6 31 37 31 37 (3,5) 1 5 21 26 28 33 7 7 (4,6) 1 8 37 45 37 45 (5,6) 1 6 26 32 39 45 13 13 (5,8) 1 14 26 40 33 47 7 7 (5,7) 1 8 26 34 35 43 9 9 (6,8) 2 2 45 47 45 47 (7,8) 1 4 34 38 43 47 9 9 (8,9) 3 3 37 50 47 50 б) в графе 2 записывается количество предшествующих работ по сетевому графику или определяется из графы 1 по числу работ, имеющих второй цифрой в коде ту, с которой начинается данная работа. Например, в графе 1 имеются три работы, оканчивающиеся на цифру 8: (5,8); (6,8); (7,8), поэтому работа (8,9) имеет три предшествующие работы; г) в графе 4 раннее начало работ, выходящих из исходного события, равно нулю, а раннее окончание этих работ равно их продолжительности (гр. 5). Раннее начало последующих работ определяется путем выбора максимального из сроков раннего окончания предшествующих работ. Количество сравниваемых сроков равно количеству предшествующих работ графы 2. Раннее начало последующих работ можно определить после того, как найдено раннее окончание предшествующих. В свою очередь, раннее окончание каждой работы находится как сумма величин раннего начала и продолжительности данной работы; г) продолжительность критического пути определяется после заполнения граф 4 и 5 как максимальная величина из сроков раннего окончания работ, которые ведут к завершающему событию 9; д) найденная величина критического пути Tкр = 50 дням заносится в графу 7 для всех работ, ведущих к завершающему событию. Затем заполнение ведется снизу вверх. Находятся все работы, следующие за рассматриваемой, и определяются разности между поздним окончанием этих работ и их продолжительнос-тями. Минимальная из величин заносится в графу 7; е) в графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3); ж) в графе 8 полный резерв времени работы определяется разностью между значениями граф 7 и 5. Если он равен нулю, то работа является критической; з) в графе 10 резерв времени событий j определяется как разность позднего окончания работы, заканчивающегося событием j графы 7, и ранним началом работы, начинающимся событием j; и) значение свободного резерва времени работы определяется как разность значений графы 10 и данных графы 8 и указывают на расположение резервов, необходимых для оптимизации. Пользуясь полученными значениями параметров работ по переводу предприятия торговли на самообслуживание табл. 4.6.8, можно перейти к анализу сетевой модели, а затем провести оптимизацию. Анализ сетевых моделей Анализ сетевой модели проводим с целью выявления резервов и «узких мест». Табличный метод расчета параметров табл. 4.6.8 позволяет решить эту задачу. Однако, большую наглядность все же дает графический метод анализа. Соединение различных методов сетевого моделирования позволяет объединить их преимущества. Следует помнить, что обнаруженные резервы позволяют более гибко управлять комплексом работ путем их разумного перераспределения с одних работ на другие, не произвольно, а по специальным методам оптимизации. Анализ сетевой модели рис. 4.3 начинаем с определения минимального времени выполнения всего комплекса работ. Для этой цели проследим все возможные пути перехода из одного события (0) к завершающему (9). Таких путей четыре: L1 = [(0,1) (1,2) (2,4) (4,6) (6,8) (8,9)] L2 - [(0,1) (1,3) (3,5) (5,6) (6,8) (8,9)] L3 = [(0,1) (1,3) (3,5) (5,6) (8,9)] L4 - [(0,1) (1,3) (3,5) (5,7) (7,8) (8,9)] Определим длительность этих путей: Т1 = t(L1) = t0,1 + t1,2 + t2,4 + f4,6+ t6,8 + t8,9 = 16 + 16 + 6 + 8 + 2 + 3 = 50 дн. Т2 = t(L2) = t0,1 + t1,3 + t3,5 + f5,6+ t6,8 + t8,9 =15 + 6 + 5 + 6 + 2 + 3=37дн. Т3 = t(L3) = t0,1 + t1,3 + t3,5 + f5,6+ t8,9 = 15 + 6 + 5 + 14 + 3 = 43 дн. Т4 = t(L4) = t0,1 + t1,3 + t3,5 + f5,7+ t7,8 + t8,9 = 15+ 6 + 5 + 8 + 4 + 3 = 41 дн. Поскольку многие из работ, лежащих на этих путях, выполняются параллельно, общий срок перевода коммерческого предприятия на самообслуживание будет определяться путем максимальной продолжительности, называемым критическим: ТКР = max {t(Li)} = 50 дн. Длительность пути L2 составляет t(L2) = 37 дней минимальна, однако не позволяет выполнить все работы комплекса. Длительность пути L2 составляет t(L2) - 50 дней, однако за это время все работы комплекса могут быть выполнены. Следовательно, минимальное время, за которое может быть выполнен весь комплекс работ, составляет 50 дней, следовательно, путь L1 является критическим. Теперь определим полные резервы времени по всем путям: R(L1)=TKP-T1=0 R(L2)=TKP-T2= 13 дн. R(L3)=TKP-T3 = 7дн. R(L4)=TKP-T4=9дн. В пределах имеющихся резервов времени с выполнением некоторых работ можно не спешить, и общий срок выполнения комплекса работ не увеличится. Если же длительность выполнения любой из работ критического пути увеличилась, то общий срок выполнения комплекса неизбежно возрастет. Для наглядного выявления мест расположения резервов времени построим сетевой график работ в масштабе времени рис. 4.4. Построение начинается с критического пути LKP в соответствии с правилами сетевого моделирования по графику событий с учетом изображения длительностей работ tij в масштабе времени по оси абсцисс. По оси ординат длины стрелок выбираются из соображений удобства восприятия топологии сети в целом. Этим объясняется большая длина стрелки работы (6,8) в сравнении с работой (4,6), хотя по масштабу времени длительность t4,6 больше t6,8. Длительность всех остальных путей T2, Т3, Т4 меньше, поэтому вводим фиктивные события 5', 8', 7' и фиктивные работы (5',6), (8',8), (7',8) с нулевой продолжительностью. В результате мы получили полную картину расположения мест свободных резервов времени табл. 4.1 работ r5,6C.B =13 дням, r5,8C.B = 7 дням r7,8C.B =9 дням. Наиболее напряженными являются Рис. 4.4. Сетевой график работ в масштабе времени работы критического пути L1, которые не имеют резервов и поэтому являются «узкими местами» комплекса работ. Таким образом, в результате анализа сетевой модели мы получили все необходимые данные для проведения оптимизации. Наличие резервов позволит провести оптимизацию сетевого графика путем лучшего перераспределения выделенных ресурсов и построить более экономный план, который даст возможность выполнить весь комплекс работ за меньшее время. Тема 5 МЕТОДЫ И МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объем частных прикладных задач решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкий круг задач коммерческой деятельности, таких, как планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров (транспортная задача); распределение работников торговли по должностям (задача о назначении); организация рациональных закупок продуктов питания (задача о диете); распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы. В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны. Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования. Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными. Использование методов математического программирования в коммерческой деятельности связано со сбором необходимой информации коммерсантом, экономистом, финансистом, затем постановкой задачи вместе с математиком. Поскольку методы математического программирования уже реализованы на компьютере в виде пакета стандартных программ, то доступ к ним обычно прост, автоматизирован и не составляет особых трудностей. Общая задача линейного программирования Постановка задачи коммерческой деятельности может быть представлена в виде математической модели линейного программирования, если целевая функция может быть представлена в виде линейной формы, а связь с ограниченными ресурсами описать посредством линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение - значения переменных должны быть неотрицательны, поскольку они представляют такие величины, как товарооборот, время работы, затраты и другие экономические показатели. В целом экономико-математическая формулировка и модель общей задачи линейного программирования имеют следующий вид: найти максимальное (минимальное) значение линейной целевой функции (5.1) при условиях-ограничениях: где aij, bi, cj, - заданные постоянные величины. Стандартной задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (5.1) при выполнении условий (5.2) и (5.4). Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения целевой функции (5.1) при выполнении условий (5.3) и (5.4).. Совокупность чисел , удовлетворяющих ограничениям задачи, называется допустимым решением (или планом). План , при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным. В случае когда требуется найти минимум функции , можно перейти к нахождению максимума функции , так как . Ограничение-неравенство исходной задачи линейного программирования, имеющее вид «», преобразуется в ограничение-равенство с добавлением к левой части дополнительной неотрицательной переменной, а ограничение - неравенство вида «» -преобразуется в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной. Если ограничения задачи отражают наличие и расход производственных ресурсов, тогда значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса. Запишем в основной задаче линейного программирования ограничение (1.3) в векторной форме , (5.5) где - m-мерные векторы-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи. План называется опорным планом основной задачи линейного программирования, если система векторов, входящих в разложение (5.5) с положительными коэффициентами xj, линейно независима. Так как векторы являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать т. Опорный план называется невырожденным, если он содержит ровно т положительных компонент. Если в опорном плане число положительных компонент меньше т, то план является вырожденным. Контрольные вопросы 1. Каковы особенности задач линейного программирования? 2. Какое решение системы линейных уравнений является планом? 3. Что называют планом ОЗЛП, опорным планом, оптимальным планом? 4. Какой опорный план называется вырожденным, невырожденным? 5. Как привести к канонической форме ОЗПЛ: а) если требуется найти минимум линейной формы; б) если функциональные ограничения заданы в виде неравенств? Постановка задач коммерческой деятельности Рассмотрим примеры преобразования задач коммерческой деятельности к общей задаче линейного программирования и построения экономико-математических моделей. Коммерческая деятельность предприятия Коммерческому отделу поручили проанализировать совместную деятельность подразделений фабрики по изготовлению и продаже двух видов краски для внутренних (В) и наружных (Н) работ, которая поступает в продажу по цене 3 тыс. руб. и 2 тыс. руб. за 1 т. Для производства красок используют два вида сырья А и В, максимально возможные суточные запасы которых составляют 3 т и 4 т. Расходы сырья на производство 1 т красок приведены в табл. 2.2.1. Изучение конъюнктуры спроса на рынке сбыта показало, что суточный спрос на краску для внутренних работ никогда не превышал спроса на краску для наружных работ более чем на 1,5 т, а спрос на краску для внутренних работ никогда не превышал 2 т в сутки. Какое количество краски каждого вида необходимо производить фабрике, чтобы доход от ее реализации был максимальным? Таблица 5.1 Сырье Расход сырья на 1 т краски, т Запасы сырья, т наружных работ, Н внутренних работ, В А 0,5 1,0 3 В 1,0 0,5 4 Цена 1 т, тыс. руб. 2 3 Построение экономико-математической модели задачи Поскольку в задаче необходимо определить объемы производства для продажи краски, то суточные объемы производства красок для наружных и внутренних работ обозначим хп и хь тонн соответственно. Критерием, по которому определяется степень достижения поставленной цели, является доход от продажи краски, который должен быть максимально возможным. На этом основании целевую функцию можно записать таким образом: Решение любой задачи осуществляется в рамках ограниченных ресурсов. В данном случае необходимо учесть ограничения на расход сырья, запасы которого на фабрике не бесконечны, а также ограничения на спрос краски. Математически эти ограничения можно записать следующим образом: 0,5хн + xв 3 запасы сырья А, хн + 0,5хв  4 запасы сырья В, хв - хн  1, 5 соотношение спроса на краски, хв  2 максимальная величина спроса на краску В. Объемы производства и соответственно продажи краски не могут принимать отрицательных значений. В связи с этим необходимо записать условие неотрицательности переменных: xн  0; xb  0. Кроме того, известно, что план фабрики предусматривает обязательный выпуск красок указанных видов, производство которых за всю историю не опускалось ниже, чем хн  0,25 т, хв  0,5 т. Таким образом, в целом экономико-математическую модель задачи можно представить в таком виде. Определить суточные объемы производства красок - вектор , который при заданных условиях-ограничениях обеспечивает максимальный доход от продажи краски в соответствии с целевой функцией: Полученная модель является задачей линейного программирования, так как все входящие в нее функции линейны. Решение данной задачи возможно с использованием геометрического метода или алгебраического симплексного метода, рассмотренных ниже в п. 2.3.1 и 2.3.2. Планирование товарооборота Коммерческое предприятие реализует товары нескольких групп: . Для реализации этих товаров используются ресурсы с ограниченным объемом: b1 — рабочее время (чел.-ч); b2 - площадь залов (м2); b3 - издержки обращения (руб.). Известны нормы расхода каждого вида ресурса на реализацию единицы j-й группы товара - aij, . Доход от продажи в расчете на единицу товара составляет cj. Необходимо составить оптимальный план товарооборота по критерию максимума дохода (или по другому критерию - минимум издержек обращения). Построение экономико-математической модели задачи Известно, что величина дохода линейно связана с объемом продажи товаров jc;-. В связи с этим целевую функцию можно записать в виде Очевидно, что объем продажи товаров не может быть отрицательной величиной. Поэтому Учитывая нормы затрат ресурсов и их объемы, запишем ограничения в виде системы: Решение задачи можно получить с помощью симплексного метода, рассмотренного ниже. Производственная задача Предприятие изготавливает несколько видов продукции, расходуя на это изготовление различные виды сырья. Запасы сырья ограничены. Доход, получаемый от реализации каждого вида продукции, различен. Необходимо составить такой план выпуска продукции, при котором доход предприятия был бы максимальным. Для изготовления п видов продукции Рj(1j n) используется т видов сырья Si(1 im). Запасы сырья составляют . Нормативы затрат сырья на изготовление единицы продукции, составляют aij. Доход, получаемый от реализации единицы продукции, составляет Необходимо составить такой план выпуска продукции, при котором доход от ее реализации будет максимальным. Построение экономико-математической модели задачи Обозначим xj количество единиц продукции j-го вида, , запланированных к производству. Тогда целевая функция будет иметь вид: Для изготовления всей продукции потребуется единиц сырья i-ro вида. Поскольку его количество ограничено величиной bi, получаем неравенство Учитывая нормативы затрат и ограничения на ресурсы, запишем систему неравенств: Решение модели можно получить, например, с помощью симплекс-метода. Пример 1. Построить экономико-математическую модель определения структуры выпуска первых и вторых блюд предприятия общественного питания при заданном квартальном плане товарооборота 270 тыс. руб. и получении максимального дохода на основе данных, приведенных в табл. 5.2. Таблица 5.2 Ресурсы Плановый фонд ресурсов Нормативные затраты ресурсов на 100 блюд 1-е блюда 2-е мясные 2-е рыбные 2-е молочные 2-е прочие Затраты труда на производство, чел.-ч 78 000 3,4 5,0 38,0 2,6 23 Затраты труда на обслуживание, чел.-ч 130 000 2,1 5,2 5,1 2,8 3 Издержки производства и обращения, руб. 16 300 4,3 6,9 6,7 26 4,1 Доход, руб. 1.3 2,0 1,5 0,3 1,7 Товарооборот, руб. 270 000 25 37 23 22 20 Экономико-математическая модель задачи имеет следующий вид. Найти такое количество выпускаемых блюд - вектор которое при заданных ограничениях по использованию ресурсов, представленных в виде системы линейных неравенств обеспечивает максимум дохода в соответствии с целевой функцией вида . Пример 2. Построить экономико-математическую модель определения структуры выпуска блюд на предприятии общественного питания, обеспечивающую максимальный доход на основе заданных объемов, ресурсов и нормативов затрат продуктов на первые и вторые блюда, представленных в табл, 5.3. Таблица 5.3 Ресурсы Плановый фонд ресурсов Нормативные затраты ресурсов на 100 блюд 1-е блюда 2-е мясные 2-е рыбные 2-е молочные 2-е прочие Мясо, кг 40 000 4,0 8,0 - - 3,8 Рыба, кг 25 000 2,5 - 10 - - Овощи, кг 27 000 3,2 2,0 3,0 - 4,6 Мука, крупа, кг 20 000 2,1 2,6 2,3 - 2,8 Молоко, л 50 000 6,5 - - 21 - Доход, руб. 1.3 2,0 1,5 0,3 1.7 Экономико-математическая модель задачи имеет следующий вид. Найти такое количество выпускаемых блюд - вектор которое при заданных ограничениях обеспечивает максимум дохода в соответствии с целевой функцией Тема 6 Методы решения задач коммерческой деятельности Геометрический метод Свойства основной задачи линейного программирования связаны со свойствами выпуклых множеств. Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его произвольными точками полностью принадлежит и прямолинейный отрезок, их соединяющий. Примерами выпуклых множеств являются прямолинейный отрезок, полуплоскость, круг, шар, куб, полупространство и др. Угловыми точками выпуклого множества называются точки, не являющиеся выпуклой комбинацией двух произвольных точек множества. Например, угловыми точками треугольника являются его вершины, круга - точки окружности, которые его ограничивают. Множество планов основной задачи линейного программирования является выпуклым (если оно не пусто). Непустое множество планов называется многогранником решений, а всякая угловая точка многогранника решений - вершиной. Если основная задача линейного программирования имеет оптимальный план, то целевая функция задачи принимает максимальное значение в одной из вершин многогранника решений. Если максимальное значение достигается более чем в одной вершине, то целевая функция принимает его во всякой точке, являющейся выпуклой линейной комбинацией этих вершин. Непустое множество планов основной задачи линейного программирования образует выпуклый многогранник, каждая вершина которого определяет опорный план. Для одного из опорных планов (т. е. в одной из вершин многогранника решений) значение целевой функции является максимальным (при условии, что функция ограничена сверху на множестве планов). Вершину многогранника решений, в которой целевая функция принимает максимальное значение, можно найти достаточно просто, если задача в стандартной форме содержит не более двух переменных: при условиях Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость допустимых значений переменных соответственно с граничными прямыми . Если система неравенств совместна, то областью допустимых решений задачи являются выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств. Решение задачи линейного программирования геометрическим методом включает следующие этапы. 1. На плоскости Х1ОХ2 строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств. 2. Находят полуплоскости, определяемые каждым из ограничений задачи. 3. Строят многоугольник решений. 4. Строят вектор , который указывает направление возрастания целевой функции. 5. Строят начальную прямую целевой функции с1х1+с2х2=0 и затем передвигают ее в направлении вектора до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов . 6. Определяют координаты точки максимум функции и вычисляют значение целевой функции в этой точке. Минимальное значение линейной функции цели находится путем передвижения начальной прямой с1х1 + с2х2 = 0 в направлении, противоположном вектору . Пример 1. Найдите максимум и минимум линейной функции при условиях-ограничениях: Решение. Построим на плоскости Х1ОХ2 многоугольник решений (рис. 6.1). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств. Построив прямые системы, найдем соответствующие полуплоскости и их пересечение. Рис. 6.1. Построение многоугольника решений Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи. Для нахождения точек экстремума построим начальную прямую и вектор . Передвигая прямую в направлении вектора , найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значениеs. Так как точка С получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых: Решив систему уравнений, получим: х1 =3,4; х2 = 4,2; откуда найдем максимальное значение целевой функции . По условию задачи начальная прямая параллельна прямой (2), так как коэффициенты при переменных х1, х2 пропорциональны: -2/-1 = 4/2 = 2. Следовательно, начальная прямая займет положение опорной прямой в точках В, С и в любой точке отрезка ВС, в которых принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений: Максимальное значение целевой функции в точке В равно: . Запишем множество оптимальных решений как линейную выпуклую комбинацию углов точек отрезка ВС: где 0  а  1. Подставив координаты угловых точек, получим: Тогда , где 0a1. Подставляя любые значения а от 0 до 1, получим координаты множества точек отрезка ВС, в каждой из которых целевая функция принимает максимальное значение, равное 10. Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору . Начальная прямая займет положение опорной прямой в вершине Д, где х1 = 2, х2 = 0, а минимальное значение целевой функции равно: Пример 2. Геометрический метод решения задачи линейного программирования рассмотрим на примере поставленной задачи и построенной модели коммерческой деятельности предприятия, представленной в разделе 2.1. Так как модель имеет только две переменные, то данную задачу можно решить геометрическим методом. Построим на плоскости Х1ОХ2 (рис. 6.2) многоугольник допустимых решений задачи. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств Построив полученные граничные прямые, найдем соответствующие полуплоскости допустимых значений переменных и их пересечение (рис. 2.3.2). Рис. 6.2. Построение области допустимых решений Направление стрелок от каждой граничной прямой определяется путем непосредственной подстановки в неравенство координат произвольно взятой точки, например (0,0), и при удовлетворении данного неравенства направляем стрелки в сторону контрольной точки, в противном случае - наоборот. Полученное пространство решений есть многоугольник ABCDEF. Угловые точки многоугольника решений имеют следующие координаты: А(0,25; 0,5), В(0,25; 1,75), С(0,5; 2), D(2; 2), E(3,(3); l,(3)). F(3,75; 0,5). Для нахождения минимума и максимума целевой функции строим начальную прямую и вектор-градиент (рис. 2.3.3). Координатами вектора являются коэффициенты целевой функции при переменных хн и хв. Для построения графика целевой функции задаем произвольное значение . Если , то прямая проходит через начало координат. Для ее построения, полагая хн =1, получим xв= -0,(6), а при хв = 1, получим хн = -1,5 (рис. 2.3.3). Полагая F(X=6), таким же образом построим линию целевой функции. Затем для хн = 0,25 и хв = 0,5 определяем минимальное значение . Таким образом построим на графике ряд параллельных прямых, рис. 3.3, где вектор-градиент показывает направление возрастания целевой функции. Максимальное значение будет в точке Е. Так как точка Е получена в результате пересечения прямых (1) и (2), то для определения ее координат решим систему уравнений: Максимальное значение целевой функции Целевая функция 2хн + Зхв = 102/3 пересекает ось хв в точке хв = 35/9, а ось хн в точке хн = 51/3. Таким образом, суточный объем производства краски для наружных работ должен быть равен 31/3 т, а для внутренних работ – 11/3 т. Доход от продажи в этом случае будет максимальным и составит 102/3 тыс. руб. Вполне реально предположить, что полученное статическое решение устареет еще до момента его реализации. Поэтому следует предусмотреть динамический характер условий производства и продажи красок. Например, важно знать, как повлияет на оптимальное решение увеличение или уменьшение спроса, изменение рыночных цен или запасов исходного сырья. Следовательно, после определения оптимального решения с целью учета фактической картины необходимо провести анализ модели на чувствительность, позволяющий определить зоны устойчивого функционирования предприятия на рынке сбыта продукции, что и рассмотрено ниже Контрольные вопросы 1. Какие задачи решаются геометрическим методом? 2. Что показывает направление вектора-градиента Л? и в каких точках области допустимых решений находятся максимум и минимум целевой функции? 3. В каком случае оптимальный план не является единственным? Тема 7. Алгебраический симплексный метод Для решения задач линейного программирования предложено немало различных алгоритмов. Наиболее эффективным среди них является алгоритм, известный под названием симплексный метод, или метод последовательного улучшения плана. Впервые симплексный метод был предложен американским ученым Дж. Данцингом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским математиком Л.В. Канторовичем. Симплексный метод - это итерационный процесс, который начинается с одного решения и в поисках лучшего варианта движется по угловым точкам области возможных решений до тех пор, пока не достигнет оптимального значения, в частности по угловым точкам многоугольника решений, полученного геометрическим методом. В тех случаях, когда модель содержит т уравнений, для построения пробных решений используются т переменных, принимающих некоторые положительные значения при нулевых значениях остальных переменных. Вначале допустим, что решение существует, причем оптимальное значение целевой функции конечно. В этом случае вычислительная процедура может быть представлена в следующей последовательности. 1. Выберем т переменных, задающих допустимое пробное решение, и исключим эти переменные из целевой функции. 2. Проверим, нельзя ли за счет одной из переменных, приравненной вначале к нулю, улучшить значение целевой функции, придавая ей отличные от нуля (причем положительные) значения. Если это возможно, перейдем к третьему этапу, в противном случае прекратим вычисления. 3. Найдем предельное значение переменной, за счет которой можно улучшить значение целевой функции. Увеличение значения этой переменной допустимо до тех пор, пока одна из т переменных, вошедших в пробное решение, не обратится в нуль. Исключим из выражения для целевой функции только что упомянутую переменную и введем в пробное решение ту переменную, за счет которой результат может быть улучшен. 4. Разрешим систему т уравнений относительно переменной, вошедшей в новое пробное решение. Исключим эту переменную из выражения для целевой функции. Вернемся ко второму этапу. Важно отметить, что при однозначном понимании данного предписания предложенный алгоритм действительно приводит к оптимальному решению для любой модели линейного программирования за конечное число итераций, если система ограничений задачи совместна. Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется. Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота. Коммерческое предприятие реализует п товарных групп, располагая т ограниченными материально-денежными ресурсами . Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы А = (аij), и прибыль ct получаемая предприятием от реализации единицы товара j группы (табл. 2.3.1). Надо определить объем и структуру товарооборота , при которых прибыль коммерческого предприятия была бы максимальной. Математическую модель задачи запишем следующим образом. Определить вектор , который удовлетворяет ограничениям вида и обеспечивает максимальное значение целевой функции Алгоритм симплексного метода включает следующие этапы. 1. Составление первого опорного плана. Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств смысла «», правые части которых bi  0. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными: где хп+i - базисные переменные, xj: - свободные переменные, . Решим эту систему относительно базисных переменных: а функцию цели перепишем в виде уравнения Полагая, что основные переменные х1 = х2 = х3 = ... хп = 0, получим первый опорный план = (0, 0, .... 0, b1 b2, ..., bт); , который заносим в симплексную табл. 2.3.2. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком. 2. Проверка плана на оптимальность. Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( 0), то план является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улучшить. В этом случае переходим к следующему этапу алгоритма. 3. Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные. Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+; -/-) ведущего столбца. Результаты заносим в отдельный столбец di которые будут всегда положительные. Строка симплексной таблицы, соответствующая минимальному значению di является ведущей. Она определяет переменную xi, которая на следующей итерации выйдет из базиса и станет свободной. Элемент симплексной таблицы, находящийся на пересечении ведущих столбца и строки, называют разрешающим и выделяют кружком. 4. Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса. Сначала заменим переменные в базисе, т. е. вместо хi в базис войдет переменная хj, соответствующая ведущему столбцу. Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующую введенной в базис переменной хj В результате этого на месте разрешающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника: , РЭ где СТЭ - элемент старого плана, РЭ - разрешающий элемент, А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Далее возвращаемся ко второму этапу аглоритма - проверке плана на оптимальность. При решении задачи линейного программирования на минимум целевой функции признаком оптимальности плана являются отрицательные значения всех коэффициентов индексной строки симплексной таблицы. Если в ведущем столбце все коэффициенты aij  0, то функция цели не ограничена на множестве допустимых планов, т. е. и задача не имеет решения. Если в столбце симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т. е. к многократному повторению процесса вычислений, не позволяющему получить оптимальный план. С целью исключения этого для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения , делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содержащая три равных значения , имеет следующий вид: План Базисные переменные Значения базисных переменных x1 x2 x3 x4 x5 x6 x7 II x4 4 2 3 6 1 2 4/2 = 2 x5 8 4 8 1 1 4 8/4 = 2 x6 10 5 12 -1 1 1 5 10/5 = 2 Допустим, разрешающим столбцом является х7, который вводится в новый план, тогда разрешающим элементом может быть: 2, 4 или 5. Следуя указанному правилу, получится таблица: Значения базисных переменных x1 x2 x3 x4 x5 x6 x7 2 1 1,5 3 0,5 1 2 1 2 0,25 0,25 1 2 1 2,4 -0,2 0,2 0,2 1 Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбцах все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке, следовательно, эта строка и будет разрешающей с разрешающим элементом 2. Если в оптимальный план вошла дополнительная переменная хп+1 , то при реализации такого плана имеются недоиспользованные ресурсы i-ro вида в количестве, полученном в столбце свободных членов симплексной таблицы. Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных. Пример 1. Коммерческое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на 1 тыс. руб. товарооборота, доход от продажи товаров на 1 тыс. руб. товарооборота, а также объем ресурсов заданы в табл. 6.1. Определите плановый объем продажи и структуру товарооборота так, чтобы доход торгового предприятия был максимальный. Таблица 7.1 Виды материально-денежных ресурсов Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота Объем ресурсов группа А группа В группа С Рабочее время продавцов, чел.-ч 0,1 3 0,4 1100 Площадь торговых залов, м2 0,05 0,2 0,02 120 Площадь складских помещений, м 3 0,02 2 8000 Доход, тыс. руб. 3 1 4 max Решение. Запишем математическую модель задачи. Определим вектор который удовлетворяет условиям и обеспечивает максимальное значение целевой функции . Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных x4, x5, x6: Матрица коэффициентов А = (atj) этой системы уравнений имеет следующий вид: Векторы , , - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля. Следовательно, соответствующие этим векторам переменные x4, x5, x6 являются базисными и в этой задаче определяют объемы неиспользованных ресурсов. Решим систему уравнений относительно базисных переменных. Функцию цели запишем в виде уравнения: Полагая, что свободные переменные х1 = 0, x2 = О, x3 = 0, получим первый опорный план = (0, 0, 0, 1100, 120, 8000), , в котором базисные переменные x4 = 1100, x5 = 120, x6 =8000. Следовательно, товары не продаются, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную табл. 6.2. Таблица 7.2 План Базисные переменные Значения базисных переменных Значения коэффициентов при x1 x2 x3 x4 x5 x6 I x4 x5 x6 1100 120 8000 0,1 0,05 3 0,2 0,02 1 0,4 0,02 2 1 0 0 1 0 0 1 5500 6000 8000 Индексная строка F(X1) -3 -5 -4 II x4 x5 x6 5500 10 2500 0,5 0,04 2,5 1 0 0 2 -0,02 5 -0,1 - 5 1 0 0 1 11000 250 1000 Индексная строка F(X2) 27500 -0,5 6 25 III x4 x5 x6 5375 250 1875 0 1 0 1 0 0 2,25 -0,5 1,25 6,25 - 2,5 1,25 -12,5 25 -62,5 0 0 1 Индексная строка F(X3) 27625 5,75 23,75 12,5 Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: -3,-5,-4. За ведущий столбец выберем столбец, соответствующий переменной х2, так как, сравнивая по модулю, имеем: |-5|>{|-3|, |-4|}. Вычислим значения di по строкам как частное от деления и из них выберем наименьшее: Следовательно, первая строка является ведущей. Разрешающий элемент равен 0,2 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице. Формируем следующую часть симплексной таблицы. Вместо переменной х4 в план II войдет переменная х2. Строка, соответствующая переменной х2 в плане II, получена в результате деления всех элементов строки x4 плана I на разрешающий элемент РЭ = 0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х2 плана II записываем нули. Таким образом, в новом плане II заполнены строки х2 и столбец х2. Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ = 0,2. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(K1)=0 =СЭ, которое указывает на место расположения нового НЭ в новом плане II. Третий элемент A = 1100 и четвертый элемент В = -5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения: Элементы строки определяются аналогично: Все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны 0. Аналогично проводятся расчеты по всем строкам таблицы, включая индексную. Выполняя последовательно все этапы алгоритма, формулируем план II. На третьей итерации табл. 4.2 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке  0. Оптимальный план можно записать так: = (250, 5375, 0, 0, 0,1875), = 27 625 тыс. руб. Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В - 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27 625 тыс. руб. Товары группы С не реализуются. В оптимальном плане среди базисных переменных находится дополнительная переменная х6. Это указывает на то, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м2, так как переменная х6 была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса. В индексной строке оптимального плана в столбцах переменных х3, х4, х5, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным. Пример 2. Рассмотрим применение симплексного метода на примере поставленной задачи анализа коммерческой деятельности предприятия в разделе 2.2.1 и уже полученного решения в теме 5 геометрическим методом. Для упрощения процедуры решения оставим условия неотрицательности переменных хн  0; хв  0. Для построения первого опорного плана систему неравенств преобразуем к системе уравнений путем введения дополнительных переменных х1, х2, х3, х4, определяющих объемы неиспользованных ресурсов: а целевую функцию представим в виде уравнения . Полагая, что основные переменные хн = хd = 0, получим первый опорный план: =(0; 0; 3; 4; 1,5; 2) , в котором базисные переменные равны: Первый опорный план заносим в симплексную табл. 7.3, который не является оптимальным, поскольку в индексной строке находятся отрицательные коэффициенты -2 и -3. Затем, действуя в соответствии с изложенными выше правилами, переходим последовательно от одного плана к другому, пока не построим оптимальный план V, в котором в индексной строке отсутствуют отрицательные элементы. Следовательно. запишем оптимальный план: =(3,(3); l,(3); О; О; 3,5; 0,(6)) =102/з тыс. руб. Таким образом, для получения максимального дохода от дневной продажи краски 102/3 тыс. руб. предприятию необходимо выпускать в сутки 31/3 т краски наружных работ и 11/3 т краски для внутренних работ. В оптимальный план вошли дополнительные переменные х3 = 3,5 и х4 = 2/3, что свидетельствует о величине недоиспользованных ресурсов третьего и четвертого вида. Следует заметить, что остальные ресурсы использованы полностью, поскольку х1 = 0 и х2 = 0. Полученный оптимальный план является невырожденным, так как при расчете столбца di не получены одинаковые минимальные значения отношений и все значения базисных переменных в оптимальном плане отличны от нуля. Кроме того, поскольку в индексной строке в столбцах переменных х1 и х2, не вошедших в состав базисных, получены не нулевые элементы, то оптимальный план является единственным. Таблица 7.3 План Базисные переменные Значения базисных переменных хн хв х1 х2 х3 х4 , min I х1 3 0,5 1 1 3 х2 4 1 0,5 1 8 х3 1,5 -1 1 1 1,5 х4 2 1 1 2 F(X1) -2 -3 II х1 1.5 1.5 1 -1 1 х2 3,25 1,5 1 -0,5 2,(15) хв 1.5 -1 1 1 - х4 0,5 1 -1 1 0,5 F(X2) 4,5 -5 3 III х1 0,75 1 0,5 -1,5 1,5 х2 2.5 1 1 -1,5 2.5 хв 2 1 1 - хн 0,5 1 -1 1 - F(X3) 7 -2 5 IV х3 1.5 2 1 -3 - х2 1 -2 1 1,5 2/з хв 2 1 1 2 хн 2 1 2 -2 - F(X4) 10 4 -1 V х3 3,5 -2 2 1 х4 2/з -4/з 2/з 1 хв 11/з. 1 4/з -2/з хн З1/з 1 -2/з 4/з F(X5) 102/з 22/з 2/з Тема 8 Другие методы решения задачи линейного программирования Метод искусственного базиса Симплексный метод решения задач базируется на введении дополнительных переменных, позволяющих образовать единичную матрицу, в которую не допускаются отрицательные и другие числа, кроме нуля и единицы. Наличие единичной матрицы является необходимым условием при решении задач симплексным методом. Если же ограничения задачи заданы в виде неравенств вида  или уравнений и(или) то невозможно сразу получить начальное базисное решение, если матрица, составленная из коэффициентов при неизвестных системы ограничений, не позволяет образовать единичную матрицу. Причем уравнения отражают жесткие условия ограничений по ресурсам, не допускающие никаких отклонений. Для соблюдения равенств вводятся искусственные переменные yi равные нулю. Векторы искусственных переменных образуют необходимую для решения единичную матрицу. Такой базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Рассмотрим примеры постановки задач такого рода. Преобразование ограничений, заданных в виде уравнений, рассмотрим на примере: В систему равенств вводим искусственные переменные у1, у2, у3 с коэффициентами, равными единице, позволяющими образовать искусственный базис решения: Целевая функция имеет вид: при решении задачи на максимум - ; при решении задачи на минимум - . За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый «штраф» величиной М, очень большое положительное число, которое обычно не задается (М). Преобразования ограничений в виде неравенств вида i рассмотрим на примере: Для получения системы уравнений вводим дополнительные переменные x4, x5, x6. Поскольку на главной диагонали единичной матрицы не могут находиться (-1), то в систему вводим искусственные переменные y1, y2, у3 с коэффициентами (+1), которые образуют искусственный базис решения Целевая функция имеет вид: при решении задачи на максимум - при решении задачи на минимум - Преобразование разнородных ограничений, представляющих собой смесь уравнений и неравенств разного вида, заключается в образовании базиса решения путем одновременного введения свободных и искусственных переменных, что придает симплексному методу большую гибкость. Например, ограничения заданы в виде системы: Сначала образуем систему уравнений, для чего вводим в первое неравенство дополнительную переменную x4, а в третье неравенство - дополнительную переменную x5: Для образования единичной матрицы вводим недостающие элементы: во второе уравнение искусственную переменную –у1, а в третье - у2: Целевая функция имеет вид: при решении задачи на максимум - при решении задачи на минимум - Поставленные таким образом задачи можно решать симплексным методом. Пример 4. Определим минимальное и максимальное значения целевой функции при следующих смешанных условиях-ограничениях: Запишем систему ограничений в виде равенств, для чего введем дополнительные переменные x3 и x4, в результате получим следующую систему: Затем введем искусственные переменные у1 и у2 в первое и второе уравнения: Для постановки задачи на минимум целевую функцию запишем так: С целью формулировки задачи для решения ее в табличной форме воспользуемся выражениями из системы уравнений для искусственных переменных: которые подставим в целевую функцию: Таким образом, стартовая точка решения определяется следовательно, уравнение целевой функции для симплексной таблицы будет иметь такой вид: Поскольку задача решается на минимум, то ведущий столбец выбирают по максимальному положительному числу в индексной строке в плане I (9М - 3), а все остальные преобразования проводятся по стандартной схеме до тех пор, пока не получатся в индексной строке только неположительные числа ( 0), а в оптимальном решении должны отсутствовать положительные значения искусственных переменных у1 и у2. Оптимальному решению соответствует точка с координатами х1 = 11/3 и х2 = 11/3 где , а у1 = 0 и y2 =0. Следует заметить, что геометрический метод решения позволяет получить такой же результат. Для решения этой же задачи на максимум целевую функцию следует записать иначе: Затем, подставив выражения для искусственных переменных, получим: Преобразуем это выражение в удобную форму для записи в симплексную таблицу: Преобразования проводим до тех пор, пока все значения в индексной строке не будут неотрицательными. В плане IV получили х1 = 1/3, х2 = 21/3 ,a совпадает с решением задачи, полученным геометрическим методом. Метод Гомори. Целочисленное решение Значительная часть задач коммерческой деятельности требует целочисленного решения. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции, например распределение товаров между коммерческими предприятиями, раскрой материалов, число станков при загрузке оборудования, распределение транспортных средств по рейсам, распределение коммерческих заказов между оптовыми предприятиями, продажа автомобилей, распределение самолетов по авиалиниям, количество вычислительных машин в управляющем комплексе и др. Линейные задачи, решение которых должно быть получено в целых числах, называют задачами целочисленного программирования. Задача целочисленного программирования формулируется так же, как и задача линейного программирования, но включает дополнительное требование, состоящее в том, что значения переменных должны быть целыми неотрицательными числами, например, х1 = 30 станков, х2 = 16 самолетов, х3= 7 человек. Методы целочисленной оптимизации можно разделить на три основные группы: а) методы отсечения; б) комбинированные методы; в) приближенные методы. Рассмотрим один из методов отсечения — метод Гомори. Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: а) оно должно быть линейным; б) должно отсекать найденный оптимальный нецелочисленный план; в) не должно отсекать ни одного целочисленного плана. Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением. Алгоритм Гомори, основанный на симплексном методе, имеет простой способ построения правильного отсечения и содержит следующие этапы. 1. Задача линейного программирования решается без учета условия целочисленности симплексным или двойственным симплексным методом. Если все элементы оптимального плана целые числа, то решение заканчивается для задачи целочисленного программирования. 2. Если среди элементов оптимального решения есть нецелые числа, то необходимо выбрать элемент с наибольшей дробной частью и составить дополнительное ограничение (сечение), которое отсекает нецелочисленные решения. Дополнительное ограничение дается в том случае, если значение базисной переменной в оптимальном плане xi=bi — дробное число. Тогда некоторые элементы аij в i-й строке симплексной таблицы также дробные числа. Обозначим [bi] и [аij] целые части чисел bi и аij, т.е. наибольшие целые числа, не превышающие bi и aij. Величины дробных частей qi и qij определяются как разности следующим образом: qi = bi - [bi]; qij =аij - [aij] и являются положительными числами. Тогда неравенство qi-qi1 x1 - qi2x2 - ... - qimxn  0, сформированное по i-й строке симплексной таблицы обладает всеми свойствами правильного отсечения. 3. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу. 4. Полученная расширенная задача решается двойным симплексным методом. Если новый оптимальный план будет целочисленным, то задача решена. В противном случае необходимо вернуться к п. 2 алгоритма. Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членом bi и целыми коэффициентами aij, то данная задача не имеет целочисленного оптимального решения. Пример. Маркетинговые исследования указали на необходимость освоения выпуска новой продукции. Поэтому на предприятии решено установить новое технологическое оборудование на освободившейся площади 10 м2. На приобретение оборудования двух видов выделено 6 млн. руб. Комплект первого вида оборудования стоимостью 1 млн руб. устанавливается на площади 5 м2 и позволяет увеличить доход предприятия на 8 млн руб. Комплект второго вида оборудования занимает площадь 2 м2, стоит 1 млн руб. и обеспечивает увеличение дохода предприятия на 5 млн руб. Определите, какое количество технологического оборудования каждого вида следует закупить, чтобы обеспечить максимальное увеличение дохода предприятия от продажи выпускаемой продукции. Решение. Обозначим через x1 х2 количество комплектов технологического оборудования соответственно первого и второго видов, через F(x) — доход предприятия от продажи продукции. Тогда математическая модель задачи имеет вид: , при ограничениях: где х1,х2 — целые числа. Приведем задачу к каноническому виду, для чего введем дополнительные неотрицательные переменные х3, х4 и решаем ее симплексным методом, а результаты записываем в табл. 7.1. Таблица 7.1 Базисные переменные Звачевия базисных перемевных x1 x2 x3 x4 x3 x4 F(x) 20 6 5 1 -8 2 1 -5 1 1 4 6 max x1 x4 F(x) 4 2 32 1 2/5 3/5 -9/5 1/5 -1/5 8/5 1 10 10/3 max x1 x2 F(x) 8/3 10/3 114/3 1 1 1/3 -1/3 1 -2/3 5/3 3 В табл. 7.1 на третьей итерации получен оптимальный план х* = (8/3,10/3) . По первому уравнению с переменной х1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью (2/3), составляем дополнительное ограничение: Дополнительное ограничение имеет вид: Преобразуем полученное неравенство в уравнение: , коэффициенты которого введем дополнительной строкой в оптимальную симплексную табл. 7.1; тогда получим продолжение табл. 7.2. Таблица 7.2 Базисные переменные Звачевия базисных перемевных x1 x2 x3 x4 x5 x3 x4 x4 F(x) 8/3 10/3 -2/3 114/3 1 1 1/3 -1/3 -1/3 1 -2/3 5/3 -1/3 3 1 max - - 3 9 - x1 x2 x4 F(x) 8/3 10/3 114/3 1 1 1 -1 2 1 2 1 -1 -3 3 Применяя алгоритм двойственного симплексного метода, проводим одну итерацию, в результате которой получаем оптимальное целочисленное решение: х* = (2,4,2); = 36 млн руб. Таким образом, предприятию необходимо установить два комплекта оборудования первого вида и четыре комплекта второго вида. Это позволит максимально увеличить доход предприятия. Контрольные вопросы 1. Какие задачи линейного программирования можно решать симплексным методом? 2. Каков признак оптимальности в симплексном методе? 3. Как строится опорный план? 4. Как определяется ведущий столбец и ведущая строка симплексной таблицы? 5. Как осуществляется перерасчет элементов симплексной таблицы? 6. Каковы основные случаи при реализации симплексного метода? 7. В каких вариантах постановки задач следует пользоваться для их решения методом искусственного базиса? 8. Какие задачи следует решать методом Гомори. Тема 9 Метод потенциалов Ранее сформулирована задача по перевозке грузов, которая называется транспортной задачей и заключается в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления A1 A2, ..., Ат в n пунктов потребления В1 В2, ...., Вn. Рассмотрим транспортную задачу, где критерием оптимальности является стоимость перевозок всех грузов, которая должна быть минимальной. Экономико-математическая модель транспортной задачи содержит системы линейных уравнений (2.2.1) и (2.2.2), условие неотрицательности переменных xij и целевую функцию . Следует иметь в виду, что: 1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей ; называется допустимым планом транспортной задачи. 2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т. е. равен (m + п - 1). Следовательно, число линейно независимых уравнений равно (m + n - 1), они образуют базис, а соответствующие им (m + n - 1) переменных будут являться базисными. 3. Допустимый план транспортной задачи, имеющий не более (m + n - 1) отличных от нуля величин xij, называется опорным. 4. Если в опорном плане число отличных от нуля компонент равно в точности (т + п - 1), то план является невырожденным, если меньше, то план называется вырожденным. 5. План , при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи. 6. Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения: (9.1) 7. Модель транспортной задачи, удовлетворяющая условию (7.1), называется закрытой. Если же указанное условие не выполняется, то модель называется открытой. В случае превышения запаса над заявками вводится фиктивный (n + 1) пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: . При , вводится фиктивный (m + 1) пункт отправления с запасом груза и соответствующие тарифы принимаются равными нулю: . 8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф - если задача поставлена на максимум целевой функции. Рассмотрим один из методов построения первого опорного плана - метод наименьших тарифов (стоимости). Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы: а) среди тарифов находится наименьший; б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркивается и в дальнейшем распределении не участвует; в) из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз. Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю. 9. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов, который основан на теории двойственности. План X = (xij) транспортной задачи будет являться оптимальным, если существует система т + п чисел ai bj, называемых потенциалами, удовлетворяющая условиям: I. (9.2) II. Потенциалы аi и bj являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу аi + bj = cij, а условия (2.6.2), (2.6.3) получены на основании второй теоремы двойственности. Введем обозначение оценки свободной клетки таблицы ij = аi + bj-сij. Если среди оценок ij нет положительных (задача поставлена на минимум), то опорный план является оптимальным. Алгоритм оценки оптимальности плана методом потенциалов включает следующие этапы. а. Построение первого опорного плана. б. Проверка вырожденности плана. Потенциалы аi и bj могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (т + п- 1), то не хватит количества уравнений для определения потенциалов, поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m + n - 1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы. в. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клетками таблицы. г. Проверка условия оптимальности. Определяем потенциалы аi и bj. Для каждой занятой клетки таблицы записываем уравнение . Получим систему (т + п - 1) уравнений с (m + п) переменными. Так как число переменных больше числа уравнений (m + п > т + п - 1), то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов аi, bj задают произвольное значение, например, для простоты вычислений полагаем а1 = 0. Тогда остальные потенциалы определяются из приведенных соотношений. В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы. Определяем оценки свободных клеток ij. Если все ij  0 (задача решается на минимум целевой функции) либо все ij  0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки ij > 0 (задача поставлена на минимум) или ij < 0 (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза. д. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных - наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т. е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом. Циклом, или прямоугольным контуром, в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл. Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-». Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его . Перераспределяем величину  по циклу, прибавляя у к соответствующим объемам груза, стоящим в плюсовых клетках и вычитая  из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной. Полученный новый опорный план проверяется на оптимальность, т. е. возвращаемся к четвертому этапу алгоритма. Примечания: 1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения xij, то при перераспределении объемов груза освобождаются две (или несколько) клеток, и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наилучшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (т + п - 1). 2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю (ij = 0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции. 3. Значение целевой функции на каждой итерации можно рассчитать следующим образом: (задача поставлена на минимум и максимум), где  величина перемещаемого по циклу объема груза; ij - оценка свободной клетки, в которую направляется груз при переходе к новому плану; - значение целевой функции на А-й итерации; - значение целевой функции на предыдущей итерации. Пример 1. На три базы А1, А2, А3 поступил однородный груз в количествах, соответственно равных 6, 8, 10 ед. Этот груз требуется перевезти в четыре магазина Bl B2, В3, В4 соответственно в количествах 4, 6, 8, 8 ед. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (тыс. руб. за ед. груза): i=1,2,3; j=1,2,3,4 Надо составить план перевозок однородного груза с минимальными транспортными издержками. Проверим необходимое и достаточное условие разрешимости задачи. Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу А4 с запасом груза, равным 2 ед. (26-24). Тарифы перевозки единицы груза из базы А4 во все магазины полагаем равны нулю. Занесем исходные данные в распределительную табл. 9.1. Таблица 9.1 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Среди тарифов из всей таблицы наименьшим является с11 = 1, поэтому в клетку А1В1 направляем максимально возможный груз. Он равен min{6,4} = 4. Тогда х11 = 4 и из базы А1 не вывезен груз в размере 2 ед., а потребность магазина B1 удовлетворена полностью. Столбец таблицы В1 выходит из рассмотрения. Из оставшихся тарифов строки наименьший с12 = 2. В клетку А1В2 направляем максимально возможный груз, равный min{2,6} = 2. Тогда строка А1 выходит из рассмотрения, поскольку из базы A1 вывезен весь груз, а потребность второго магазина не удовлетворена на 4 единицы. Из оставшихся тарифов наилучший с22 = 3 и с34 = 3. В клетку А2В2 направляем груз, равный min{8,4} = 4. При этом вычеркивается столбец В2 из рассмотрения. Из оставшихся тарифов наименьший с34 = 3. В клетку А3В1 направляем груз, равный min{10,8} - 8. При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезены 2 ед. Этот нераспределенный груз направляем в клетку А3В3, х33 = 2. Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика - базы A4 - 2 ед. в клетку А4В3 т.е. x43=2 В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть т + п- 1=4 + 4-1 = 7. Следовательно, опорный план является невырожденным. 3. Определяем значение целевой функции первого опорного плана. = 41 + 2-2 + 4-3 + 4-8 + 2-6 + 8-3 + 20 = 88 тыс. руб. 4. Проверим оптимальность опорного плана. Найдем потенциалы аi,bj- по занятым клеткам таблицы, в которых аi + bj = сij , полагая, что а1 = 0, решим систему уравнений: Занесем найденные значения потенциалов в таблицу 2.6.1 и вычислим оценки свободных клеток ij = (bj + ai) – сij: 13 = 7 + 0 - 4 = 3; 14 = 4 + 0 - 3 = 1; 21 = 1 + 1 - 4 = -2; 24 = 4 + 1 - 5 - 0; 31 = 1 + (-1) - 2 = -2; 32 = 2 + (-1) - 7 = -6; 41= 1 + (-7) -0 = -6; 42= 2 + (-7) - 0 = -5; 44= 4 + (-7) - 0 = -3. Первый опорный план не является оптимальным, так как 13 > 0 и 14 > 0, поэтому переходим к его улучшению. 5. Выбираем максимальную оценку свободной клетки - 13 = 3. Для клетки А1В3 построим цикл перераспределения груза. Для этого в перспективную клетку AtBa поставим знак «+»,- а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в табл. 2.6.1. Из чисел xij, стоящих в минусовых клетках, выбираем наименьшее, т. е.  = min{2,4} = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 2 из xij, стоящих в минусовых клетках. В результате получим новый опорный план II, приведенный в табл. 9.2. 6. Определяем значение целевой функции: 88-2-6-82 (тыс. руб.) 7. Количество занятых клеток в плане II - 7, следовательно, план невырожденный. Таблица 9.2 8. Проверяем оптимальность плана методом потенциалов, для этого находим потенциалы ai, bj; по занятым клеткам, где а1 + bj = cij, полагая что а1 = 0; Затем рассчитываем оценки свободных клеток: 12 = 0 + (-1) - 2 = -3; 14 = 0 + 1 - 3 = -2; 21 = 4 + 1 - 4 - 1; 24 = 4 + 1 - 5 - 0; 31 = 2 + 1 - 2 - 1; 32 = 2 - 1 - 7 = -6; 41 = -4 + 1 - 0 = -3; 42 = -4 - 1 - 0 = -5; 44 = - 4 + 1 - 0 = -3. План, полученный в табл. 2.6.2, не оптимальный, так как 21 > 0 и 31 > 0. 9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем А3В1 в которую записываем +, затем строим цикл перераспределения, приведенный в табл. 2.6.2. В построенном цикле определяем величину  = min(4,2) = 2. Перераспределив груз, получаем новый план III, приведенный в табл. 9.3. Таблица 9.3 10.Количество занятых клеток 7, а должно быть т + п - 1 = 7, следовательно, план III невырожденный. 11. Вычислим значение целевой функции: F(Х3) = F(X2) -  31 = 82 - 2 1 = 80 тыс. руб. 12. Проверяем оптимальность плана III методом потенциалов. Находим потенциалы по занятым клеткам: Рассчитываем оценки свободных клеток: 12 = - 1 + 0 - 2 = -3; 14 - 2 + 0 - 3 = -1; 21 = 1 + 4 - 4 - 1; 24 = 2 + 4 - 5 = 1; 32 = - 1 + 1 - 7 = -7; 33 = 4 + 1 - 6 = -1; 41 = 1 +(-4) - 0 = -3; 42 = - 1 + (-4) - 0 = -5; 44 - 2 + (-4) - 0 = -2. План не оптимальный, так как 21 > 0 и 24 > 0. 13. Проводим улучшение плана III перераспределения груза. В качестве перспективной клетки для загрузки выбираем А2В1, в которую записываем +, затем строки цикл перераспределения в табл. 2.6.3. Определяем величину  = min(2; 2) = 2. После проведения операции перераспределения получаем план IV, приведенный в табл. 2.6.4. 14. План получается вырожденный, поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза, равные 2. При перераспределении две клетки А1В1 и А2В2 оказались свободными, поэтому число занятых клеток (6) будет меньше, чем т + п - 1 = 7. Для продолжения решения в одну из освободившихся клеток - в клетку А1В1 записываем нуль, так как тариф с11 меньше с23. 15. Вычисляем значение целевой функции: -  21 = 80 - 2 • 1 = 78 тыс. руб. Таблица 9.4 16. Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам: Рассчитаем оценки свободных клеток: 12 = 0 + 0 - 2 = -2; 14 = 2 + 0 - 3 = -1; 23 = 4 + 3 - 8 = - 1;24 = 2 + 3-5 = 0;32 = 0 + 1-7 = - 6; 33 = 4 + 1-6 = - 1; 41 = 1 + (-4) - 0 = -3; 42 = 0 + (-4) - 0 = -4; 44 = 2 + (-4) - 0 = -2. Поскольку все оценки неположительны, меньше или равны нулю, то, план IV является оптимальным, что можно представить в виде следующей матрицы: Анализ плана. С первой базы необходимо весь груз направить в третий магазин, со второй базы направить в первый и второй магазины в количестве 2 ед. и 6 ед., а груз с третьей базы следует вывозить в первый и четвертый магазины в количестве 2 и 8 ед. соответственно. При этом потребность третьего магазина В3 остается неудовлетворенной в объеме 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составляет 78 тыс. руб. Так как оценка свободной клетки 24 = 0, то задача имеет множество оптимальных планов. Контрольные вопросы 1. Как формулируется транспортная задача? 2. Как составляется первый опорный план в транспортной задаче? 3. В чем сущность метода потенциалов? Как с его помощью проверяется опорный план транспортной задачи на оптимальность? 4. Как решаются транспортные задачи с нарушенным балансом между спросом и предложением? 5. Как разрешается проблема вырождения в транспортной задаче? ГЛАВА 10. МЕТОДЫ И МОДЕЛИ ТЕОРИИ ИГР В коммерческой деятельности приходится принимать решения, учитывая множество факторов различной природы. Причем специфика коммерческой деятельности такова, что учитываемые при принятии решений факторы нередко обладают так называемым свойством неопределенности, поскольку нельзя заранее определить точно, каково будет значение того или иного фактора или показателя. Отсюда следует, что и результат принятия решения также будет обладать свойством неопределенности. Например, объем продажи в значительной степени зависит от спроса населения на тот или иной товар. Спрос, как известно, является величиной случайной, и, следовательно, его значение имеет некоторый разброс, и является точно неопределенным. Неопределенность значений управляемых факторов приводит к тому, что рекомендации по решению проблемы не могут быть столь же четкими и однозначными, как в случаях полной определенности. В процессе принятия решений появляются возможные варианты решений. Поэтому можно считать, что принятие решения состоит в выборе наилучшего варианта из имеющихся. Конечно, фактическое принятие решения является процессом. Но итогом этого процесса является выбор одной возможности из имеющихся в наличии. Для решения любой проблемы, независимо от ее характера, существенным является вопрос: кто должен быть поставлен перед проблемой? Другими словами, должно существовать некое лицо, принимающее решение. Это может быть или какое-либо ответственное лицо: директор, бухгалтер, коммерсант, заведующий секцией, продавец и т.д., или некоторая группа лиц: комиссия, совет директоров, бригада и т.д. Лицо, принимающее решение, — это некий реально существующий индивидуум (или группа), которого не устраивает состояние дел или перспектива их будущего состояния и который имеет полномочия действовать так, чтобы это состояние изменилось. В настоящее время многие решения в коммерческой деятельности - заказ на поставку того или иного вида товаров, заключение договоров с поставщиками, распределение людей в учреждениях по должностям или операциям, управление движением товаров, не оптимальны. Принятие решений в этом случае является искусством и в сильной степени зависит от субъективных качеств лица, принимающего решение. Однако в условиях широкого развития кооперации, усложнения производственных связей с поставщиками товаров народного потребления и, наконец, решения задач увеличения ассортимента и качества товаров в торговой сети и стремления к более полному удовлетворению потребностей населения приводят к тому, что ответственность человека за последствия принимаемых решений многократно возросла. Поэтому при отсутствии полной определенности необходимо проводить количественный анализ и на основе его принимать то или иное обоснованное решение. Разработаны специальные математические методы, предназначенные для обоснования решений в условиях неопределенности. В некоторых, наиболее простых, случаях эти методы позволяют найти множество решений и выбрать из них оптимальное. В более сложных случаях эти методы дают вспомогательный материал, позволяющий глубже разобраться в сущности явлений и оценить каждое из возможных решений с различных точек зрения, взвесить его преимущества и недостатки и в конечном счете принять, если не единственно правильное, то по крайней мере близкое к оптимальному, решение. Следует заметить, что при выборе решения в условиях неопределенности всегда неизбежен элемент произвола, а следовательно, и риска. Недостаточность информации всегда опасна, и за нее приходится платить. Поэтому в условиях сложной ситуации необходимо представить варианты решения и их последствий в такой форме, чтобы сделать произвол выбора менее сильным, а риск — минимальным. Задачами о принятии решений в условиях полной или частичной неопределенности занимается теория игр и статистических решений. Понятие об игровых моделях В коммерческой деятельности приходится принимать решения в условиях противодействия другой стороны, которая может преследовать противоположные или иные цели, добиваться других путей достижения цели, препятствовать теми или иными действиями или состояниями внешней среды достижению намеченной цели. Причем эти противодействия противоположной стороны могут носить пассивный или активный характер. В таких случаях приходится учитывать возможные варианты поведения противоположной стороны, ответные действия, возможную реакцию. Возможные варианты поведения обеих сторон и их исходов для каждого сочетания альтернатив и состояний можно представить в виде математической модели, которая называется игрой. Если в качестве противоположности выступает неактивная, пассивная сторона, которая явно активно не противодействует достижению намеченной цели, то такие игры называются играми с «природой». В качестве такой стороны в коммерции являются неизвестность поведения клиентов, реакция населения на новые виды товаров, неясность погодных условий при перевозке товаров или проведении ярмарки, недостаточная информированность о коммерческих операциях, закупках, сделках и т.п. В других ситуациях противоположная сторона активно, сознательно может противостоять достижению намеченной цели. В подобных случаях происходит столкновение противоположных интересов, мнений, целей. Такие ситуации называются конфликтными, а принятие решений в конфликтной ситуации затрудняется из-за неопределенности поведения противника. Известно, что противник сознательно стремится предпринять наименее выгодные для вас действия, чтобы обеспечить себе наибольший успех. Неизвестно, в какой мере противник умеет оценить обстановку и возможные последствия, как он оценивает ваши возможности и намерения. Обе стороны конфликта не могут точно предсказать взаимные действия. Несмотря на такую неопределенность, принимать решения приходится каждой стороне конфликта. Необходимость обоснования оптимальных решений в конфликтных ситуациях привела к возникновению теории игр. Теория игр — это математическая теория конфликтных ситуаций. Основными ограничениями этой теории являются предположение о полной (« идеальной ») разумности противника и принятие при разрешении конфликта наиболее осторожного «перестраховочного» решения. Основные понятия теории игр Конфликтующие стороны называются игроками, одна реализация игры — партией, исход игры — выигрышем или проигрышем. Развитие игры во времени происходит последовательно, по этапам или ходам. Ходом в теории игр называют выбор одного из предусмотренных правилами игры действия и его реализацию. Ходы бывают личные и случайные. Личным ходом называют сознательный выбор игроком одного из возможных вариантов действия и его осуществление. Случайным ходом называют выбор, осуществляемый не волевым решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, пасовка, сдача карт и т.п.). Одним из основных понятий теории игр является стратегия. Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры. Оптимальной стратегией игрока называется такая стратегия, которая при многократном повторении игры, содержащей личные и случайные ходы, обеспечивает игроку максимально возможный средний выигрыш (или, что то же самое, минимально возможный средний проигрыш). В большинстве конфликтных ситуаций при выборе разумной стратегии приходится принимать во внимание не один, а несколько показателей. Причем стратегия, оптимальная по одному показателю, необязательно будет оптимальной и по другим. В зависимости от причин, вызывающих неопределенность исходов, игры можно разделить на следующие основные группы: комбинаторные игры, в которых правила дают в принципе возможность каждому игроку проанализировать все разнообразные варианты своего поведения и, сравнив эти варианты, избрать тот из них, который ведет к наилучшему для этого игрока исходу. Неопределенность исхода связана обычно с тем, что количество возможных вариантов поведения (ходов) слишком велико и практически игрок не в состоянии их всех перебрать и проанализировать; азартные игры, в которых исход оказывается неопределенным в силу влияния различных случайных факторов. Азартные игры состоят только из случайных ходов, при анализе которых применяется теория вероятностей. Азартными играми теория игр не занимается; стратегические игры, в которых неопределенность исхода вызвана тем, что каждый из игроков, принимая решение о выборе предстоящего хода, не знает, какой стратегии будут придерживаться другие участники игры, причем незнание игрока о поведении и намерениях партнеров носит принципиальный характер, так как отсутствует информация о последующих действиях противника (партнера). Существуют игры, сочетающие в себе свойства комбинаторных и азартных игр, стратегичность игр может сочетаться с комбинаторностью и т.д. В игре могут сталкиваться интересы двух или более игроков. Если в игре участвуют два игрока, игра называется парной, если число игроков больше двух — множественной. Участники множественной игры могут образовывать коалиции (постоянные или временные). Множественная игра с двумя постоянными коалициями превращается в парную. Парные игры получили наибольшее распространение в практике анализа игровых ситуаций. Различают игры и по сумме выигрыша. Игра называется игрой с нулевой суммой, если каждый игрок выигрывает за счет других, а сумма выигрыша и проигрыша одной стороны равны другой. В парной игре с нулевой суммой интересы игроков прямо противоположны. Парная игра с нулевой суммой называется антагонистической игрой. Наиболее полно исследованы в теории игр антагонистические игры. Игры, в которых выигрыш одного игрока и проигрыш другого не равны между собой, называются играми с ненулевой суммой. В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные. Игра называется конечной, если у каждого игрока имеется только конечное число стратегий. Игра называется бесконечной, если хотя бы у одного игрока имеется бесконечное число стратегий. По количеству ходов, которые делают игроки для достижения своих целей, игры бывают одношаговые и многошаговые. Одношаговые игры заключаются в том, что игрок выбирает одну из доступных ему стратегий и делает всего один-единственный ход. В многошаговых играх игроки для достижения своих целей делают последовательно ряд ходов, которые могут ограничиваться правилами игры либо могут продолжаться до тех пор, пока у одного из игроков не останется ресурсов для продолжения игры. В последнее время получили большое распространение так называемые деловые игры. Деловая игра имитирует взаимодействие людей и проявляется как упражнение в последовательном принятии множества решений, основанное на некоторой модели коммерческой деятельности и на исполнении участниками игры конкретных ролей-должностей. Деловые игры предназначены для воспроизведения и согласования коммерческих интересов. В основе конструкции игры лежат взаимосвязь ресурсов и использование знаний об их возможностях. Деловые игры имитируют организационно-экономические взаимодействия в различных звеньях коммерческих организаций и предприятий. Элементами игровой модели являются: участники игры; правила игры; информационный массив, отражающий состояние и движение ресурсов моделируемой хозяйственной системы. Преимущества игровой имитации перед реальным объектом таковы: наглядность последствий принимаемых решений, переменный масштаб времени; повторение имеющегося опыта с изменением установок; переменный масштаб охвата коммерческих явлений и объектов. Основными направлениями использования деловых игр являются следующие: учебный процесс, например обучение моделированию коммерческих операций; аттестация персонала, проверка их компетентности; научные исследования; разработка бизнес-планов. В деловых играх игрокам обычно задаются начальные условия, в которых они находятся, сообщаются правила проведения игры, представляются варианты возможных решений и оценка их последствий. В игре обязательно присутствует «ведущий», который руководит игрой, оценивает принятые игроками решения, состояния, в которых они могут находиться в процессе игры, и определяет выигрыши и проигрыши по исходам игры. Приведенный перечень существующих в настоящее время игр далеко не исчерпан. Проведение классификации и группировки игр позволяет для однотипных игр найти общие методы поиска альтернатив в принятии решения, выработать рекомендации по наиболее рациональному образу действий в ходе развития конфликтных ситуаций в коммерческой деятельности. Основными вопросами теории игр, которые возникают в коммерческой деятельности, являются: 1) в чем состоит оптимальность поведения каждого из игроков в игре, какие свойства стратегий следует считать признаками оптимальности; 2) существуют ли стратегии игроков, которые обладали бы атрибутами оптимальности; 3) если существуют оптимальные стратегии, то как их найти? Заметим, что на практике, если у игрока нет точного представления о том, какое решение является оптимальным, то вопрос о его поисках оказывается беспредметным, и все усилия по его нахождению могут оказаться напрасной тратой времени. Постановка игровых задач Решения, принимаемые в коммерческой деятельности, направлены, как правило, на удовлетворение определенных потребностей населения и связаны обычно с распределением ресурсов предприятия: товаров, денег, людей и т.д. Рассмотрим систему управления коммерческого предприятия, структуру которого можно представить как орган управления (дирекция) и некоторое количество производственных единиц (товарных секций или отделов). Каждый отдел реализует некоторый набор товаров. В зависимости от организации и правового положения руководство может иметь те или иные возможности управления работой отделов. Предполагается, что в данном случае наиболее действенной формой управления является оптимальное распределение ресурсов. Отдел самостоятельно может выбрать программу выполнения товарооборота. Целью коммерческого предприятия является максимизация доходов или минимизация затрат, связанных с продажей товара. Сведем данную задачу к игровой модели. Обозначим через п число отделов; т — число различных товарных ресурсов; хi — вариант выполнения товарооборота, принимаемый i-м отделом, , yj — вид товарного ресурса, выделяемый коммерческим директором, , aij — набор товаров, реализуемый i-м отделом при выделении j-го вида товарного ресурса, , ,Y — суммарный объем ресурсов, которыми распоряжается коммерческий директор, С — доход или потери, связанные с реализацией товара. В терминах игровой модели можно дать следующую интерпретацию введенных обозначений: п — число стратегий отдела; т — число состояний среды xi — i-я стратегия, , уj — j-е состояние среды, , aij — исход, получаемый при стратегии xi, и состояние среды yj , , . Математическая модель сформулированной задачи имеет следующий вид: максимизировать (минимизировать) величину при ограничениях Продажа товаров коммерческим предприятием может быть описана соотношением где ri — фактор, значение которого хорошо известно руководству i-гo товарного отдела, но руководство коммерческого предприятия достаточной информации о нем не имеет. Это может быть отбраковка товаров, колебания спроса, неравномерность потока покупателей и т.д. Таким образом, выделенный ресурс уj и выбранная технология работы товарного отдела xi не дает руководству коммерческого предприятия полной информации о том, какая будет реализована продукция аij — это знает только i-й отдел. Очевидно, что существует зависимость хi = (уij, ri), в которой есть неопределенные факторы riMi конкретные значения которых в момент распределения ресурсов yi между товарными отделами неизвестны руководству коммерческого предприятия. В этих случаях разумно воспользоваться принципом гарантированного результата, т.е. поставить задачу: найти такое распределение ресурса yj, чтобы при этом достигался , следовательно, руководство магазина так распределяет ресурсы, чтобы минимизировать потери при наихудшем возможном значении неопределенного фактора или , следовательно, руководство коммерческого предприятия так распределяет ресурсы между товарным отделом, чтобы максимизировать доходы при наихудшем возможном значении неопределенного фактора. Пример 1. Рассмотрим постановку и решение следующей задачи. Коммерческое предприятие заключило договор на централизованную поставку овощей из теплиц на сумму 10 000 руб. ежедневно. Если в течение дня овощи не поступают, магазин имеет убытки в размере 20 000 руб. от невыполнения плана товарооборота. Магазин может осуществить самовывоз овощей фермера. Для этого он может сделать заказ в транспортном предприятии, что вызовет дополнительные расходы в размере 500 руб. Однако опыт показывает, что в половине случаев посланные машины возвращаются без овощей. Можно увеличить вероятность получения овощей от фермера до 80%, если предварительно посылать туда своего представителя, что требует дополнительных расходов в размере 400 руб. Существует возможность заказать дневную норму овощей у другого надежного поставщика — плодоовощной базы, по повышенной на 50% цене. Однако в этом случае, кроме расходов на транспорт (500 руб.) возможны дополнительные издержки в размере 300 руб., связанные с трудностями реализации товара, если в тот же день поступит и централизованная поставка от фермера. Какой стратегии надлежит придерживаться магазину, если заранее неизвестно, поступит или не поступит централизованная поставка. Составим игровую модель данной задачи. Игроками в данной задаче являются соответственно магазин и поставщик. Перечислим стратегии первого игрока — поставщика. П1 — поставка своевременная, П2 — поставки нет. У магазина имеются четыре стратегии поведения: М1 — ожидать поставку, не принимая дополнительных мер; М2 — послать к поставщику свой транспорт; М3 — послать к поставщику представителя и транспорт; М4 — заказать поставку у плодоовощной базы. Всего возможны 8 совместных ситуаций, которые представлены в табл. 10.1. Таблица 10.1 Затраты магазина, руб. Ситуации Стоимость овощей Убытки от непоставки Транспортные издержки Командировочные издержки Издержки от реализации Всего за день 1 10 000 10 000 2 20 000 20 000 3 10 000 500 10 500 4 5 000 10 000 500 15 500 5 юооо 500 400 10 900 6 8 000 4 000 500 400 12 900 7 25 000 500 300 25 800 8 15 000 500 15 500 Для того чтобы легче было разобраться в сложившихся ситуациях и по возможности оценить их, составляют платежную матрицу. Матрица имеет т строк — по числу стратегий первого игрока и n столбцов — по числу стратегий второго игрока. На пересечении i-й строки и j-го столбца ставится платеж второго игрока первому, в ситуации когда применены i-я и j-я стратегии игроков. Если в данной ситуации выигрывает второй игрок, то платеж будет иметь знак «минус». Платежная матрица данной задачи представлена в табл. 10.2. Таблица 10.2 Стратегия магазина Стратегия фермера п1 п2 м1 -10 000 -20 000 м2 -10 500 -15 500 м3 -10 900 -12 900 м4 -25 800 -15 500 Выбор стратегии магазина зависит от надежности фермера как поставщика продукции, которую можно оценить величиной вероятности р1. Тогда величина р2=1 – p1 представляет величину ненадежности поставщика. По данным табл. 10.2 можно составить уравнения затрат магазина Е от надежности поставщика для каждой стратегии магазина. М,: E(p1) - 10000 p1 + 20000 (1- p1); М2: E(p1) = 10500 p1 + 15500 (1- p1); M3: E(p1) = 10900 p1 + 12900 (1- p1); M4: E(p1) = 25800 p1 + 15500 (1- p1). Если своевременная поставка осуществляется с вероятностью 0,4, тогда ожидаемые затраты магазина составят соответственно: М1: Е(0, 4) - 10000 • 0,4 + 20000 • 0,6 - 16000 руб.; М2: Е(0, 4) = 10500 • 0,4 + 15500 • 0,6 = 13500 руб.; М3: Е(0, 4) = 10900 • 0,4 + 12900 • 0,6 = 12100 руб.; М4: Е(0, 4) - 15800 • 0,4 + 15500 • 0,6 = 19620 руб. Таким образом, минимальные расходы магазин понесет в том случае, если примет стратегию М3, т.е. не только пошлет фермеру автотранспорт, но и отправит туда своего представителя. Пример 2. Формирование платежной матрицы рассмотрим на примере задачи о взаиморасчетах. Известно, что для того, чтобы начать какое-либо дело в торговле, по производству продукции или оказанию услуг, необходимы средства, которые могут быть собственными и/или заемными. Предприятие создается с целью получать прибыль (доход) от своей деятельности, а для этого необходимо вложить (инвестировать) капитал в основные средства (в помещение, оборудование и т.п.), в оборотные средства (в материалы, товары и т.п.), в рабочую силу. В процессе деятельности предприятия происходит изменение средств и источников этих средств, т.е. происходит движение средств и их источников. При этом на любой момент времени (дату) будет выполняться закон «сохранения»: средства — источники этих средств. Поскольку источники средств подразделяются на два вида, собственные (капитал) и заемные (обязательства), тогда может быть записано уравнение в виде: средства = капитал + обязательства. Обязательства могут иметь различную форму: кредиты банков, акции, облигации, векселя, товары, отданные предприятию на реализацию или на консигнацию (товарный кредит). Все эти юридические или физические лица являются кредиторами предприятия и вправе рассчитывать на получение доходов (дивидендов) от совместной деятельности. Описание деятельности предприятия проводится на языке бухгалтерского учета, понятном всем предпринимателям независимо от области их деятельности: промышленность, строительство, сельское хозяйство, машиностроение, торговля, образование и др. Бухгалтерский учет позволят выявить финансовый результат — прибыль предприятия путем подсчета разности доходов и расходов за определенный период. Предприниматели А, В и С заключили договор для совместного проведения цепочки посреднических операций на май на условиях самостоятельного финансирования своей части. Взаимное переплетение трех вариантов коммерческих операций послужило поводом к образованию взаимозадолженностей, зарегистрированных бухгалтером в хронологическом порядке за май, которые представлены в таблице 10.3. Таблица 10.3 Журнал регистрации взаимных задолженностей участников игры А, В, С за май №п/п Дата Долг Сумма, у.е. к получению к оплате 1 6 А В 1000 2 6 А В 2000 3 11 А С 500 4 13 В А 800 5 17 В С 400 6 21 С А 1500 7 26 С В 700 8 31 В С 400 Итого 7300 Всего вариантов взаимозадолженностей при трех участниках шесть: 1) АВ; 2) АС; 3) ВА; 4) ВС; 5) СА; 6) СВ. Просуммируем одноименные варианты, например, Е(А, D) = Е1(А, В) + Е2(А, В) = 1000 + 2000 = 3000 у.е. и т.д., а результаты запишем в сводный журнал взаимных задолженностей.(табл. 10.4) Таблица 10.4 Матрица взаимных задолженностей № п/п Долг Сумма, у.е. к получению к оплате 1 А В 3000 2 А С 500 3 В А 800 4 В С 800 5 С А 1500 6 С В 700 Итого 7300 Задача заключается в том, чтобы к концу расчетного периода (в данном случае к концу месяца) произвести окончательные расчеты между участниками игры. Это можно сделать двояким образом: а) произвести все шесть расчетов между участниками в соответствии с данными таблицы по принципу «Каждый сам за себя»; б) сделать необходимые расчеты и произвести взаимозачеты долгов. При втором варианте число платежей сократится вдвое, соответственно для расчетов потребуется меньше наличных денег. При расчетах между клиентами А и В Е(А, В) = 3000 — это сумма долга, которую А должен получить от В, а Е(В, А) = 800 — сумма к получению В от А. Сальдо Е(А, В) = Е(А, В) - Е(В, А) = 3000 - 800 = +2200 означает сумму долга, которую А должен получить от В при окончательном расчете. При расчетах между А и С получим Е(А, С) = Е(А, С) - Е(С, А) = 500 - 1500 = -1000, а этот результат означает прямо противоположное — сумму к оплате задолженности господина А перед господином С, что то же самое, Е(С, А) = - Е(А, С) = +1000 представляет собой сумму к получению С долга от А. И наконец, расчет сальдо Е(В, С) = Е(В, С) - Е(С, В) - 800 - 700 = + 100 является заключительным во взаиморасчетах между тремя участниками коммерческой операции. При этом варианте расчетов следует провести всего три платежа для погашения взаимных задолженностей, для чего потребуется 2200 + 1000 + + 100 = 3300 у.е. — меньшая сумма в сравнении с общей суммой 7300. В общем случае при числе участников m количество возможных (неповторяющихся) корреспонденции равно m • (n - 1), при m = 10 число корреспонденции равно 10 • (10-1) = 90. Для систематизации таких расчетов записать данные сводного журнала в виде матрицы выигрышей. Таблица 10.5 Матрица выигрышей взаимных задолженностей Выигрыш - счета к получению Проигрыш - счета к оплате, у.е. Итого к получению, у.е. А В С А 3000 500 3500 В 800 800 1600 С 1500 700 2200 Итого к оплате 2300 3700 1300 7300 Таблица 10.6 Матрица проигрышей Проигрыш - счета к оплате Выигрыш - счета к получению, у.е. Итого к оплате, у.е. А В С А 800 1500 2300 В 3000 700 3700 С 500 800 1300 Итого к получению 3500 1600 2200 7300 Транспонированная матрица Ет есть матрица проигрышей. Если из матрицы выигрышей Е вычесть матрицу Ет, то получим матрицу сальдо окончательных расчетов как разность Е = Е - Ет. Таблица 10.7 Платежная матрица — сальдо расчетов участников игры на 31 мая Выигрыш - счета к получению Проигрыш - счета к оплате, у.е. Итого к получению, у.е. А В С А +2 200 -1000 +1200 В -2 200 +100 -2 100 С +1000 -100 +900 Итого к оплате -1200 +2 100 -900 Полученная таблица Е обладает следующими свойствами: а) сумма всех ее элементов равна нулю; б) элементы таблицы зеркально симметричны относительно главной диагонали, т.е. всегда Е(Х, Y) = - E(Y, X) для любых X, Y = А, В, С. Таблица Е, т.е. таблица сальдо окончательных задолженностей и способ ее получения, описанный выше, составляет основу компьютерной технологии бухгалтерского учета. Используя введенные выше обозначения, можно записать основное уравнение взаимных расчетов для любого количества участников в матричной форме: E(t) = E(t - 1) + E(Dt) - ET(t), где E(t), E(t - 1) - матрицы, в которых со знаком «+» или «-» записаны окончательные сальдо взаимных задолженностей, собственно, на конец t и начало t - 1. Матрица E(t) — таблица, в которой записаны суммы выигрышей («счета к получению») за рассматриваемый период, а транспортированная матрица ЕT(t) — это таблица, в которой записаны просуммированные за тот же период суммы проигрышей («счета к оплате») тех же участников игры. Причем все матрицы E(t), E(t - 1), E(t), ET(t) квадратные, определяемые числом участников игры. Тема 11 Методы и модели решения игровых задач Принцип минимакса Рассмотрим конечную парную игру с нулевой суммой. Игрок I имеет m стратегий (Al, А2,.... Аm), а игрок II — п стратегий (В1,В2, ..., Вn). Такая игра называется игрой размерностью т x п. Пусть каждая сторона выбрала определенную стратегию: игрок I — Аi(i = 1, 2,.... т), игрок II — Вj(j = 1, 2,.... п). Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой. Пусть aij — выигрыш игрока А в ситуации, когда игрок А выбрал стратегию Ai, а игрок В выбрал стратегию Вj. Выигрыш игрока В в данной ситуации обозначим через bij. Рассматриваем игру с нулевой суммой, следовательно, aij = -bij для любых i и j и для проведения анализа достаточно знать выигрыш только одного из игроков, допустим А. Если игра состоит только из личных ходов, то выбор стратегии (Аi, Bj) однозначно определяет исход игры, т.е. выигрыш игрока I. Обозначим его aij. Если игра содержит также случайные ходы, то выигрыш при паре стратегий (Ai, Вj) есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае ожидаемый выигрыш — это среднее значение (математическое ожидание). Предположим, что значения aij известны для каждой пары стратегий (Аi, Bj). Составим прямоугольную таблицу, строки которой соответствуют стратегиям игрока I, а столбцы — стратегиям игрока II. Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой. Эта таблица называется платежной матрицей. Каждый элемент (аij > 0) матрицы определяет величину выигрыша игрока I и проигрыш игрока II при применении соответствующих стратегий (Аi, Bj). Цель игрока I — максимизировать свой выигрыш, а игрока II — минимизировать свой проигрыш. Будем считать, что все aij > 0. Этого всегда можно добиться прибавлением достаточно большого положительного числа ко всем строкам и столбцам матрицы. Такое изменение матрицы не повлияет на результат. Задача состоит в определении: 1) наилучшей (оптимальной) стратегии игрока I из стратегий (Al, А2,.... Аm) 2) наилучшей (оптимальной) стратегии игрока II из стратегий (В1,В2, ..., Вn). Для решения задачи применяется принцип, согласно которому участники игры одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Проанализируем последовательно каждую стратегию игрока I. Если игрок I выбирает стратегию A1, то игрок II может выбрать такую стратегию Вj при которой выигрыш игрока I будет равен наименьшему из чисел а1j. Обозначим его a1: (11.1) т.е. a1 — минимальное значение из всех чисел первой строки. Если игрок I выбирает стратегию Аi то его выигрыш будет равен наименьшему из чисел aij т.е. (11.2) Выбирая стратегию Аi игрок I должен рассчитывать на то, что в результате разумных действий игрока II он не выиграет больше, чем ai. Поэтому игрок I должен выбрать ту стратегию, для которой число ai — максимально. Обозначим это максимальное значение ai через а: (11.3) т.е. а — максимальное значение из всех чисел ai(1,2,..., т). Подставив вместо аi выражение (2), получим: (11.4) Величина a — гарантированный выигрыш, который может обеспечить себе игрок I при любом поведении игрока II. Величина а называется нижней ценой игры, или максимином, а стратегия Ai игрока I, обеспечивающая получение нижней цены игры, называется максиминной чистой стратегией, при этом игрок I при любом поведении игрока II обеспечивает себе выигрыш, не меньше а: aia(i = 1, 2,..., т). Игрок II заинтересован в том, чтобы уменьшить свой проигрыш, т.е. обратить выигрыш игрока I в минимум. Для выбора оптимальной стратегии он должен найти максимальное значение выигрыша в каждом столбце и среди этих значений выбрать наименьшее. Обозначим через bj максимальное значение в каждом столбце: (11.5) Наименьшее значение Bj обозначим через B: . (11.6) С учетом (11.5), получим: (11.7) Р называется верхней ценой игры, или минимаксом. Стратегия игрока II, обеспечивающая получение верхней цены игры, называется минимаксной чистой стратегией. Применяя ее, игрок II проиграет не больше 6 при любых действиях игрока I: . Справедливо неравенство а  B. Таким образом, придерживаясь максиминной стратегии Ai, игрок I желает получить выигрыш не менее а независимо от действий игрока II, а игрок II, придерживаясь минимаксной стратегии Вj, гарантирует себе проигрыш не больше В. Принцип, диктующий игрокам выбор соответствующих стратегий (максиминной и минимаксной), в теории игр называется принципом минимакса. Этот принцип был впервые сформулирован Дж. фон Нейманом в 1928 г. Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. а = B. Такие игры называются играми с седловой точкой, в этом случае  = а = B называется чистой ценой игры, а стратегии игроков Аi и Вj, позволяющие достичь этого значения, — оптимальными. Пара (Аi, Вj ) называется седловой точкой матрицы, так как элемент aij =  одновременно является минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии Аi и Вj и чистая цена являются решением игры в чистых стратегиях, т.е. без привлечения механизма случайного выбора. Пример 1. Пусть дана платежная матрица. Найти решение игры, т.е. определить нижнюю и верхнюю цены игры и минимаксные стратегии. Таким образом, нижней цене игры (а = 4) соответствует стратегия А3 игрока I. Выбирая эту стратегию, игрок I достигнет выигрыша не меньше 4 при любом поведении игрока II. Верхней цене игры (B = 6) соответствует стратегия игрока II — В2. Эти стратегии являются минимаксными. Если обе стороны будут придерживаться этих стратегий, выигрыш будет равен 4 (а33). Решения игр в смешанных стратегиях Как мы отмечали выше, если матричная игра содержит седловую точку, то ее решение находится по принципу минимакса. Если же платежная матрица не имеет седловой точки, то применение минимаксных стратегий каждым из игроков показывает, что игрок I обеспечит себе выигрыш не меньше а, а игрок II обеспечит себе проигрыш не больше B. Так как а < B, то игрок I стремится увеличить выигрыш, а игрок II — уменьшить проигрыш. Если информация о действиях противной стороны будет отсутствовать, то игроки будут многократно применять чистые стратегии случайным образом с определенной вероятностью. Такая стратегия в теории игр называется смешанной стратегией. Из сказанного следует, что смешанная стратегия игрока — это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Для применения смешанных стратегий требуются следующие условия: 1) в игре отсутствует седловая точка; 2) игроками используется случайная смесь чистых стратегий с соответствующими вероятностями; 3) игра многократно повторяется в одних и тех же условиях; 4) при каждом из ходов один игрок не информирован о выборе стратегии другим игроком; 5) допускается усреднение результатов игр. В теории игр доказано, что любая парная конечная игра с нулевой суммой имеет по крайней мере одно решение в смешанных стратегиях. Отсюда следует, что каждая конечная игра имеет цену 2 — средний выигрыш, приходящийся на одну партию, удовлетворяющий условию а    B. Каждый игрок при многократном повторении игры, придерживаясь смешанных стратегий, получает более выгодный для себя результат. Оптимальное решение игры в смешанных стратегиях обладает следующим свойством: каждый из игроков не заинтересован в отходе от своей оптимальной смешанной стратегии, если его противник применяет оптимальную смешанную стратегию, так как это ему невыгодно. Стратегии игроков в их оптимальных смешанных стратегиях называются активными. В теории игр доказывается следующая теорема об активных стратегиях. Теорема. Применение оптимальной смешанной стратегии обеспечивает игроку максимальный средний выигрыш (или минимальный средний проигрыш), равный цене игры у, независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий. Смешанные стратегии игроков I и II, применяющих соответственно стратегии А1,А2,.., Аm и B1,B2,.., Bn обозначим через SI =(p1,p2,.., pm) и SII =(q1,q2,.., qn) где pi  0, qi  0, , p1,p2,.., pm вероятности использования первым игроком стратегий А1, А2, .... Ат, ql q2, ..., qn — вероятности использования вторым игроком стратегий Bl B2.....Вn. Также смешанную стратегию игрока I — SI можно записать, как (11.8) Соответственно для игрока II: (11.9) Зная платежную матрицу А, можно определить средний выигрыш (математическое ожидание) : (11.10) где и —векторы, с компонентами p1,p2,.., pm , ql q2, ..., qn соответственно. Игрок I, применяя свои смешанные стратегии, стремится увеличить свой средний выигрыш, достигая (11.11) Игрок II добивается: (11.12) Обозначим через рA и qB векторы, соответствующие оптимальным смешанным стратегиям игроков I и II, при которых выполняется равенство: (11.13) При этом выполняется условие: (11.14) Решить игру — это означает найти цену игры и оптимальные стратегии. Рассмотрим наиболее простой случай конечных игр 2x2 без седловой точки с матрицами: , (11.15) т.е. имеется платежная матрица (11.16) Требуется найти оптимальные смешанные стратегии игроков SI = (р1, p2) (p1 + р2 = 1), SII = (q1, q2) (q1 + q2 = l) и цену игры . Каковы бы ни были действия противника, выигрыш будет равен цене игры . Это означает, что если игрок I придерживается своей оптимальной стратегии SI(р1, р2 )» то игроку II нет смысла отступать от своей оптимальной стратегии SII = (q1, q2). В игре 2 х 2, не имеющей седловой точки, обе стратегии являются активными. Для игрока I имеем систему уравнений: (11.17) Для игрока II аналогично: (11.18) Если  <> 0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы не равен нулю, следовательно, системы (11.17) и (11.18) имеют единственное решение. Решая систему уравнений (11.17) и (11.18) находим оптимальные решения SI = (р1, p2, SII = (q1, q2) и : (11.19) (11.20) Пример. Дана платежная матрица: Найти решение. Решение. Так как а = 3,B=5, то a<>B (3, и игра не имеет седловой точки, то решение ищем в смешанных стратегиях. Системы уравнений имеют вид: для игрока I — (11.21) для игрока II — (11.22) Решая системы (3.3.21) и (3.3.22), находим: p1=1/5, p2=4/5, q1=7/10, , q2=3/10, =18/5 Следовательно, оптимальные стратегии игроков имеют вид: SI=(1/5,4/5), SII=(7/10,3/10) Геометрический метод Решение игры в смешанных стратегиях допускает геометрическую интерпретацию, т.е. задачу можно решить графически. Геометрический метод решения игры состоит в следующих шагах. 1. В системе координат X0Y по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A1, правый — стратегии А2. Промежуточные точки х соответствуют некоторым смешанным стратегиям S1 = (p1,p2). 2. По оси ординат откладываются выигрыши при стратегии А2. 3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии А2 (рис. 11.1). Рис. 11.1. Графическая интерпретация решения игры Пусть имеется игра с платежной матрицей: Если игрок II применяет стратегию В1, то выигрыш игрока I при использовании чистых стратегий A1 и А2 составляет соответственно а11 и а21. Соединим эти точки прямой В1В1 (см. рис. 11.1). Бели игрок I при стратегии В1 применяет смешанную стратегию , то срерний выигрыш, равный а11р1 + а21р2, изображается точкой N на прямой В1В1, абсцисса этой точки равна р2. Прямая В1B1 называется стратегией В1. Ордината любой точки отрезка В1B1 равна величине выигрыша игрока I при применении им стратегии А1 и А2 с соответствующими вероятностями p2 и р2. На том же графике откладываются точки а12 и а22 на оси ординат и на параллельной прямой в точке 1 (см. рис. 11.1). В2В2 соответствует стратегии игрока II — В2. Точка пересечения B1B1 и В2В2 определяет цену игры g. Ординаты точек отрезка В2В2 равны среднему стратегий A1 и А2 с вероятностями р1 и р2. Ломаная B1NB2 — это нижняя граница выигрыша, получаемая игроком I. В точке N он максимален (). Пример. Найти оптимальную смешанную стратегию руководителя предприятия и гарантированный средний выигрыш у при выборе из двух новых технологий А1 и А2- Известны выигрыши каждого вида технологий по сравнению со старой технологией. Матрица игры имеет вид: ИгрокII B1 B2 a1 Игрок I А, 0,4 0,9 0,4 А2 0,6 0,5 0,5 bj 0,6 0,9 Максимальная стратегия руководителя предприятия А2. Для этой стратегии гарантированный выигрыш равен a = 0,5 (50%) по сравнению со старой технологией. Решение: (p1 р2) и  определим графически: p1 = 0,375, р2 = 0,625, рис. 11.2. Рис.11.2. Геометрический метод решения игры Оптимальная стратегия:  = 0,55. По сравнению с прежней технологией выигрыш составляет 55%. Метод линейного программирования Антагонистическую матричную игру тхп (где т > 3, п > 3) с конечными значениями тип можно свести к паре двойственных задач линейного программирования. Рассмотрим игру т х п, заданную платежной матрицей А: (11.23) Допустим, что все элементы (выигрыши) платежной матрицы положительны (аij- > 0). Этого всегда можно добиться, если все аij  0, то  > 0. Пусть платежная матрица не содержит седловой точки, т.е. игра решается в смешанных стратегиях: SI =(p1,p2,.., pm) и SII =(q1,q2,.., qn) (11.24) Применение игроком I оптимальной смешанной стратегии SI гарантирует ему средний выигрыш не меньше цены игры  независимо от поведения игрока II. Игрок II, применяя оптимальную смешанную стратегию SII гарантирует для себя минимальный проигрыш (не больше ). Если игрок II применяет свою чистую стратегию Bj, а игрок I — свою оптимальную стратегию SI. то средний выигрыш игрока I равен: j=a1j p1 +a2j p2+... + aij pi +... + amj pm (j=1,2,...,n) (11.25) Если игрок I применяет свою чистую стратегию Аi а игрок II — свою оптимальную смешанную стратегию SII ,то средний выигрыш игрока II составит i=ai1 q1 +a2i q2+... + ain qn (i=1,2,...,m) Учитывая, что j не может быть меньше  для игрока I, a i не может быть больше  для игрока II, двойственную задачу линейного программирования можно записать следующим образом: 1) для игрока I — (11.26) 2) для игрока II — (11.27) Смысл этих систем уравнений заключается в следующем: игрок I стремится увеличить цену игры (  max), т.е. он действует так, чтобы его средний выигрыш при использовании его стратегий с вероятностями рi, для любой j-й стратегии игрока II был не меньше величины , которую он стремится увеличить. Игрок II стремится уменьшить свой проигрыш (  min), т.е. он действует так, чтобы его средний проигрыш при использовании его стратегий с вероятностями qj при любой i-й стратегии игрока I не превышал величину , которую он стремится уменьшить. Задача состоит в нахождении двух оптимальных смешанных стратегий SI =(p1,p2,.., pm) и SII =(q1,q2,.., qn), которые дают для игрока I максимально возможный для него средний выигрыш, а для игрока II минимально возможный для него средний проигрыш. Разделив левую и правую части неравенств (11.26) и (11.27) на цену игры  > 0, получим: (11.28) (11.29) Введем обозначения: (11.30) (11.31) Тогда уравнения (11.28) и (11.29) примут вид: (1132) (11.33) Из равенств и и выражений (11.30) и (11.31) следует, что переменные (хi) и (yj) удовлетворяют условиям: (11.34) (11.35) Учитывая, что игрок I стремится максимизировать , а игрок II стремится минимизировать , переменные (xi) и (yj) должны быть выбраны так, чтобы целевая функция достигала минимума, а целевая функция — максимума. Таким образом, задача решения игры сводится к задаче линейного программирования. Оптимальные стратегии SI = (р1, р2,..., рm) и SII = (q1 q2, ..., qn) игры с платежной матрицей [A]m x n могут быть найдены путем решения симметричной пары двойственных задач линейного программирования: (11.36) (11.37) Решая их, находим значения xi, уj цену игры у и, следовательно, оптимальные стратегии SI =(p1,p2,.., pm) и SII =(q1,q2,.., qn) или (11.38) (11.39) (11.40) Задача. Найти решение игры с платежной матрицей: (11.41) Решение. Математические модели пары двойственных задач линейного программирования будут выглядеть так: найти минимум функции F(x) = х1 + х2 + х3 при ограничениях: (11.42) Найти максимум функции Ф(у) = у1 + у2 + у3 при ограничениях: (11.43) Из условий угловой точки следует: (11.44) Решая систему уравнений (11.44), находим: x1=2/9, x2=2/9, x3=1/9, F(x)=x1+x2 + x3=5/9 Из , находим =9/5, p1= x1=2/5, p2= x2=2/5, p3= x3=1/5. Таким образом, оптимальная стратегия игрока I будет: SI=(2/5,2/5,1/5) Зная цену игры  = 9/5 т, задачу нахождения оптимальной стратегии игрока II можно упростить. Для этого воспользуемся любыми двумя стратегиями системы (11.43): (11.45) так как yj=qj/ , то систему можно переписать так: (11.46s) или (11.47) Решая систему (11.47), находим: q1=2/5, q2=2/5, q3=1/5; y1=2/9, y2=2/9, y3=1/9; Ф(y)=5/9. Таким образом, оптимальная стратегия игрока II будет: SII=(2/5,2/5,1/5). Тема 12 Игровые модели в условиях коммерческого риска Риск определяется возможностью отклонения от желаемого результата в худшую сторону или выхода за пределы допустимого интервала, то есть тем, что фактически происходит с негативными последствиями. Для принятия решений в условиях риска используют методы теории вероятностей если это возможно по причине массовости явления. В таком случае факторы, например, состояния среды представляют собой либо случайные величины, либо случайные функции. Они описываются определенными статистическими характеристиками, например, математическим ожиданием и дисперсией и обладают статистической устойчивостью. Принимающий решение ориентируется на средние, наиболее вероятные результаты, однако при этом не исключен риск получения не того результата, на который была рассчитана коммерческая стратегия, тогда мерой риска следует считать среднее квадратическое отклонение, например, дохода, что позволяет найти решение, оптимальное по Парето. Ситуации, в которых риск связан не с сознательным противодействием противоположной стороны (среды), а с недостаточной осведомленностью о ее поведении или состоянии лица, принимающего решение, называются «играми с природой». В таких играх человек старается действовать осмотрительно, например используя стратегию, позволяющую получить наименьший проигрыш. Второй игрок (природа) действует незлонамеренно, совершенно случайно, возможные стратегии его известны (стратегии природы). Такие ситуации исследуются с помощью теории статистических решений. Рассмотрим «игру с природой» в условиях частичной неопределенности. Пусть у игрока I имеется т возможных стратегий А1, А2,..., Аm и можно сделать п предположений о состояниях природы (среды) П1 ,П2,..., Пn с известными вероятностями их появления рj. Пусть известен выигрыш ,, который получает игрок I при выборе стратегии Аi для каждого состояния природы Пj Тогда можно составить платежную матрицу А следующего вида: Таблица 12.1 В этом случае и можно найти величину математики ческого ожидания выигрыша, для каждой стратегии Аi: Оптимальной будет считаться та стратегия, для которой эта величина принимает максимальное значение При этом следует заметить, что оптимизация в среднем не исключает полностью влияние фактора случайности. Пример. Для доставки свежих фруктов из Кишинева в Москву можно использовать три вида транспорта: Т1 — воздушный, Т2 — автомобильный, Т3 — железнодорожный. Ожидаемые величины дохода aij с учетом затрат на транспортировку, погрузочно-разгрузочные работы и сроков доставки фруктов и потерь и вместе с условными вероятностями их получения pij представлены в виде матрицы в табл. 12.2. Таблица 12.2 ai1 pi1 ai2 pi2 ai3 pi3 Т1 300 0,6 200 0,3 -300 0,1 Т2 450 0,2 300 0,7 -200 0,1 Т3 B 600 600 0,1 450 450 0,8 -100 -100 0,1 Для выбора наиболее оптимального варианта доставки свежих фруктов сначала находим для каждого вида транспорта математическое ожидание выигрыша: М(T1) = 300 • 0,6 + 200 • 0,3 + (-300) • 0,1 - 210, М(Т2) = 450 • 0,2 + 300 • 0,7 + (-200) • 0,1 = 280, М(Т3) = 600 • 0,1 + 450 • 0,8 + (-100) • 0,1 = 410, а затем определяем максимальное значение этого показателя, которое и указывает на оптимальное решение: следовательно, наиболее выгодно доставлять свежие фрукты в Москву из Кишинева железнодорожным транспортом. При исследовании «игры с природой» вводится показатель, позволяющий оценить, насколько то или иное состояние «природы» влияет на исход. Этот показатель называется риском. При пользовании стратегией Аi и состоянием среды Пj разность между максимально возможным выигрышем Bj при данном состоянии «природы» Пj- и выигрышем аij- при выбранной стратегии Aj называется риском rij: rij=bj-aij где , т.е. максимальное число в столбце состояния среды Пj. Очевидно, что риск всегда положительное число, т.е. rij  0. Пользуясь этими положениями, найдем для задачи табл. 3.3.5 все значения Bj и построим матрицу рисков R (табл. 12.3). Таблица 12.3 rij pij Ti ri1 pi1 ri1 pi1 ri1 pi1 M(ri­) T1 300 0,6 250 0,3 200 0,1 275 T2 150 0,2 150 0,7 100 0,1 145 T3 0 0,1 0 0,8 0 0,1 0 Для решения задачи можно пользоваться значениями среднего риска: Оптимальным в этом случае будет та стратегия, для которой средний риск будет минимальным В связи с этим для каждого решения находим средний риск: = 300 • 0,6 + 250 • 0,3 + 200 • 0,1 = 275, = 150 • 0,2 + 150 • 0,7 + 100 • 0,1 = 145, = 0 • 0,1 + 0 • 0,8 + 0 • 0,1 = 0, который следует стремиться сделать минимальным, т.е. выбрать такую стратегию Тк, для которой величина минимальна: следовательно, наиболее целесообразно доставлять свежие фрукты из Кишинева в Москву железнодорожным транспортом. Заметим, что максимум среднего выигрыша и минимум среднего риска достается при выборе одной и той же стратегии, в данном случае Т3. Мы рассмотрели вариант выбора только одной вполне определенной стратегии, которая называется чистой. В коммерческой практике встречаются такие ситуации, в которых выгоднее применять или случайное чередование чистых стратегий, что увеличивает размер гарантированного выигрыша, или одновременное использование всех стратегий с некоторыми вероятностями. В таких играх необходимо найти оптимальную смешанную стратегию S(p1, р2,..., рn) и найти цену игры при известной платежной матрице. Предположим, что на предприятии оптовой торговли имеется n-типов товаров какой-либо товарной группы. В магазин необходимо завести Q = 1000 ед. всего ассортиментного набора данной группы товара. Требуется определить объемы товаров каждого типа, которые целесообразно завести в магазин, и гарантированный уровень дохода. При этом известно, что если товар типа j (1 j  n) будет пользоваться спросом, то магазин от его реализации получит прибыль dj, в противном случае издержки, связанные с его хранением, порчей и т.п., составят убыток сj. Моделью такого экономического конфликта является игра, в которой в качестве одной стороны выступает магазин (игрок М), а в качестве другой — «природа» — спрос населения, причем он неизвестен. Каждая из сторон имеет по n-стратегий: Мi — стратегия игрока М по завозу i-гo товара объемом QI; а Пj — стратегий игрока П — спрос на j-й товар. Полезностью магазина, очевидно, будет его доход Д. В таком случае конечная игра задается матрицей выигрышей табл. 12.4. Таблица 12.4 Допустим, что доходы от продажи по каждому виду товаров равны, т.е. d1 = d2 = ... = dn = d. Для упрощения матрицы вычтем из всех ее элементов число d, что не изменит множество оптимальных смешанных стратегий, а только значение игры уменьшается на d, в результате чего (-сi - d) = -hi матрица выигрышей примет другой вид: Для решения задачи воспользуемся данными табл. 12.5. Таблица 12.5 Показатели Тип товара 1 2 3 4 5 Доход от реализации усл. ед., dj Издержки, усл. ед., сj 32 16 32 8 32 4 32 4 32 2 С учетом этих данных матрица выигрышей будет иметь следующий вид: Преобразуем эту матрицу путем вычитания из каждого элемента d = 32 к виду: Определим при неизвестном спросе рентабельность завоза товаров рассматриваемой группы, для чего необходимо проверить выполнение следующего неравенства: . Поскольку в нашем случае это условие выполняется, то товар завозить в магазин целесообразно. Очевидно, правильная торговая политика наблюдается при использовании смешанной стратегии SM - (р1, p2, р3, ..., рi, ..., рn), где вероятности pi показывают доли от всего объема Q =1000 ед. каждого типа товаров, которые следует завозить в магазин и определяются по формуле Например, для стратегии М3 находим: Аналогично определяем остальные доли завозимых объемов товаров, после чего записываем оптимальную смешанную стратегию: SM= (0,16; 0,19; 0,21; 0,21; 0,23), согласно которой следует завозить в магазин товаров по каждому типу соответственно в следующих объемах: Q1 = 160 ед., Q2 = 190 ед., Q3 = Q4 = 210 ед., Q5 - 230 ед. В этом варианте снабжения товарами доход магазина будет равен значению игры, которое определяется по формуле При использовании смешанной стратегии, т.е. завоза товаров разного типа, доход гарантируется лишь в среднем, является ожидаемым и не может совпадать точно с реальным выигрышем, что и является характерным в условиях риска. Игровые модели в условиях полной коммерческой неопределенности Рассмотрим игру с природой т х п. У игрока имеется т стратегий А1, А2, ..., Аm. Возможно п состояний природы П1, П2, ..., Пn. Известен выигрыш игрока для каждой его стратегии и каждого состояния природы . Но, к сожалению, ничего нельзя сказать о том, с какими вероятностями природа принимает эти состояния. Другими словами, ничего конкретного нельзя сказать о состояниях среды, в которой протекает коммерческий процесс. В этом случае решение будет приниматься в условиях полной коммерческой неопределенности. Запишем платежную матрицу и матрицу рисков «игры с природой». Таблица 12.6 Таблица 12.7 Где Рассмотрим варианты определения наилучшей стратегии в условиях неопределенности на следующих примерах. Пример 1. В Северном округе Москвы планируется строительство овощехранилища. Имеются три возможных проекта создания такого хранилища площадью S1 = 200 кв. м, S2 = 300 кв. м и S3 = 400 кв. м. В зависимости от эффективности использования выделенных площадей рассчитаны варианты ежегодного дохода bij (тыс. руб.), которые представлены в виде платежной табл. 12.8. Таблица 12.8 si Доход от занимаемой площади W 100 200 300 400 S1 = 200 м2 S2 = 300 м2 S3 = 400 м2 130 60 -140 130 350 410 290 410 350 520 560 560 350 520 670 670 130 60 -140 130 350 520 670 Надо определить наиболее целесообразный вариант строительства овощехранилища. Анализ игры начнем с позиций принципа максимина. Он основан на том предположении, что принимающий решение действует осторожно и избирает чистую стратегию, гарантирующую ему наибольший (максимальный) из всех наихудших (минимальных) возможных исходов действия по каждой стратегии. В таком случае, если мы изберем стратегию Sl то наихудшее из того, что может случиться, состоит в том, что мы получим чистую выгоду в размере: Аналогично находим для остальных стратегий наихудшие исходы и записываем их в табл. 12.8. Это уровни безопасности каждой стратегии, поскольку можно быть уверенным, что ничего более худшего не произойдет. Лучшим решением Soпт будет такое, которое гарантирует наилучший из множества наихудших исходов, и определяется в соответствии с изложенным принципом по формуле Такая стратегия S1 является максиминной, поскольку чтобы не произошло, т.е. при любом состоянии среды результат не может быть хуже, чем а. Это нижняя цена игры. В силу этого принцип максимина называют также принципом наибольшего гарантированного результата. Максиминная оценка является единственно абсолютно надежной при принятии решения в условиях неопределенности. Этот принцип является основой критерия Вальда, в соответствии с которой оптимальной стратегией при любом состоянии среды, позволяющем получить максимальный выигрыш в наихудших условиях, является максиминная стратегия, определяемая выражением Следует заметить, что при наличии возможности получения дополнительной информации в игре каким-либо образом, можно повысить гарантированный уровень выигрыша. Теперь проведем аналогичные рассуждения для второй стороны — состояний среды. Если нам известно точно состояние среды — в данном случае величина занимаемой площади, то мы выберем решение Si максимизирующее наш выигрыш: Очевидно, учитывая все возможное, худший для нас вариант будет определяться выражением Это верхняя цена игры, или минимакс, а соответствующая стратегия — минимаксная. В соответствии с этим вторая сторона «природы» даст возможность нам выиграть не больше, чем B. Составим теперь матрицу рисков для представленной игры (табл. 12.9). Таблица 12.9 ||rij|| 100 200 300 400 max ri S S1 60 210 320 320 S2 70 40 150 150 150 S3 270 120 270 Риск является основой минимаксного критерия Сэвиджа, согласно которому выбирается такая стратегия Ss, при которой величина риска принимает минимальное значение в самой неблагоприятной ситуации: Сущность этого критерия состоит в том, чтобы избежать большого риска при выборе решения. В соответствии с этим критерием (табл. 3.3.12) следует построить овощехранилище площадью S2 = 300 кв. м. При анализе «игры с природой» разумнее придерживаться некоторой промежуточной позиции, граница которой регулируется показателем пессимизма-оптимизма X в критерии Гурвица. В соответствии с этим компромиссным критерием для каждого решения определяется линейная комбинация минимального и максимального выигрыша: и затем выбирается та стратегия Si( для которой эта величина окажется наибольшей: Коэффициент X называют степенью оптимизма. Его значения находятся в диапазоне 0 X  1, при X = 1 он превращается в критерий Вальда, а при X = 0, получают критерий «крайнего оптимизма», выбирающий стратегию «ва-банк», которой соответствует самый больший выигрыш. Допустим, в примере табл. 3.3.11, мы придерживаемся ближе к пессимистической оценке и полагаем, что х = 0,8, тогда для каждой стратегии получим соответственно: G1 = 0,8 • 130 + (1 - 0.8) • 350 = 174 G2 = 0,8 • 60 + (1 - 0.8) • 520 = 152 G3 = 0,8 • (-140) + (1 - 0.8) • 670 = 22 В соответствии с критерием Гурвица наиболее целесообразный вариант строительства овощехранилища определяется следующим образом: Следовательно, наиболее целесообразным вариантом является строительство овощехранилища площадью St - 200 кв. м. Таким образом, приведенные методы и модели позволяют с разных сторон провести анализ хозяйственных решений торговли в условиях неопределенности. Пример 2. Магазин имеет некоторый запас товаров ассортиментного минимума. Если запас товаров недостаточен, то необходимо завести его с базы; если запас превышает спрос, то магазин несет расходы по хранению нереализованного товара. Пусть спрос на товары лежит в пределах S = 5-8 единиц, расходы по хранению одной единицы товара составляют с = 0,1 руб., а расходы по завозу единицы товара k = 0,2 руб. Определить оптимальную стратегию магазина по завозу товаров. Составим платежную матрицу. Игроком является магазин, а «природой» — спрос на товары. Элементы платежной матрицы определяют следующим образом. Если магазин имеет 5 единиц товара и спрос равен S = 5, то магазин расходов не несет и элемент a11 = 0. Если магазин имеет 6 единиц товара, а спрос равен S = 5, то магазин может продать 5 единиц товара, а одну единицу должен хранить, неся при этом расходы, которые определяются элементом а21 = -0,1. Если магазин имеет 5 единиц товара, а спрос равен S = 6, то магазину необходимо завести одну единицу товара, расходуя на эти цели сумму, равную *. Следовательно, элемент а12 = -0,2. Проведя аналогичные рассуждения, можно получить значения всех элементов платежной матрицы: Таблица 12.10 5 6 7 8 5 -0,2 -0,4 -0,6 6 0,1 -0,2 -0,4 7 0,2 -0,1 -0,2 8 0,3 -0,2 -0,1 Определим оптимальную стратегию по максиминяому критерию Вальда: Для этого по каждой строке найдем минимальные значения элементов матрицы . Так как элементами являются расходы магазина, взятые с противоположным знаком, то, следовательно, минимальный выигрыш будет соответствовать минимальному числу. Тогда a1 = -0,6; a2 = -0,4; a3 = -0,2; a4 = -0,3, из которых по критерию Вальда находим максимальное значение: Следовательно, оптимальная стратегия магазина заключается в поставке 7 единиц товара, что позволит ему обеспечить минимум издержек в самой неблагоприятной ситуации. Определим оптимальную стратегию по минимаксному критерию Сэвиджа: Матрица рисков строится следующим образом. По каждой строке (так как оптимальная стратегия находится для магазина, т.е. игрока А) находится элемент с максимальным значением . Каждый элемент в i-й строке находится как разность rij = bj- aij. Следовательно, матрица рисков будет выглядеть следующим образом: Таблица 12.11 5 6 7 8 5 0,2 0,4 0,6 6 0,1 0,2 0,4 7 0,2 0,1 0,2 8 0,3 0,2 0,1 Согласно минимаксному критерию находим максимальное значение риска по каждой строке: 0,6; 0,4; 0,2; 0,3. Минимаксное значение риска r = 0,2. Следовательно, минимаксная стратегия магазина заключается в поставке 7 единиц товара, что позволяет ему гарантировать минимальный риск в самой неблагоприятной ситуации. Таким образом, используя методы и модели принятия решений в условиях неопределенности, можно проводить количественный анализ сложных ситуаций, возникающих в коммерческой практике, учитывать разнообразные социально-экономические факторы, влияющие на деятельность торговых предприятий и принимать обоснованные, близкие к оптимальным решения по управлению. Игровые модели конфликтов В России 17 августа 1998 г. «стартовал» экономический кризис — событие, известное под названием «дефолт». У фирмы был открыт счет в Банке. После кризиса Банк стал неплатежеспособным. У фирмы «зависли» на счете 1,5 млн руб., которые принадлежали не самой фирме, а ее клиентам. Клиенты потребовали возврата своих денег. Но Банк не давал четкого ответа, когда вернет деньги и вернет ли вообще. Это характерный пример конфликта, который в то время коснулся очень многих как юридических, так и физических лиц. Возможность конфликтов заложена в существе самой человеческой жизни. Причины конфликтов коренятся в аномалиях общественной жизни и несовершенстве самого человека. Среди причин, порождающих конфликты, следует назвать прежде всего социально-экономические, политические и нравственные причины. Они являются питательной средой для возникновения различного рода конфликтов. На возникновение конфликтов оказывают влияние психофизические и биологические особенности людей. Во всех сферах человеческой деятельности при решении самых разнообразных задач в быту, на работе или отдыхе приходится наблюдать различные по своему содержанию и силе проявления конфликта. Об этом ежедневно пишут газеты, передает радио, транслирует телевидение. Они занимают значительное место в жизни каждого человека, поскольку последствия некоторых конфликтов бывают слишком ощутимы на протяжении многих лет жизни. Они могут съедать жизненную энергию одного человека или группы людей в течение нескольких дней, недель, месяцев или даже лет. Бывает так, что разрешение конфликтов проходит весьма корректно и профессионально грамотно, а других, что бывает чаще, непрофессионально, безграмотно сплохими исходами чаще для всех участников конфликта, где нет победителей, а есть только побежденные. Очевидно, необходимы рекомендации по рациональному образу действий в конфликтных ситуациях. Часть конфликтов являются надуманными, искусственно раздутыми, созданными для прикрытия профессиональной некомпетентности некоторыми лицами и вредны в коммерческой деятельности. Другие же конфликты, являясь неизбежным спутником жизни любого коллектива, могут быть весьма полезны и служат импульсом для развития коммерческой деятельности в лучшую сторону. Конфликты в настоящее время являются ключевой проблемой жизни как отдельных личностей, так и целых коллективов в коммерческой деятельности. Действия литературных персонажей, героев неизбежно сопровождаются появлением, развитием какого-либо жизненного конфликта, который так или иначе разрешается иногда мирно, иногда драматически или трагически, например на дуэли. Лучшими источниками наших знаний о человеческих конфликтах являются классические трагедии, серьезные и глубокие романы, их экранизация или театральная постановка. Деятельности человека могут противостоять в конфликте интересы других людей или стихийные силы природы. В одних конфликтах противоположной стороной выступает сознательно и целенаправленно действующий активный противник, заинтересованный в нашем поражении, сознательно препятствует успеху, старается сделать все от него зависящее, чтобы добиться своей победы любыми средствами, например с помощью киллера. В других конфликтах такого реального противника нет, а действуют лишь «слепые силы природы»: погодные условия, состояние торгового оборудования на предприятии, болезни сотрудников и т.п. Природа не злонамеренна и выступает пассивно, причем иногда во вред человеку, а иногда к его выгоде, однако ее состояние и проявление влияют на результат коммерческой деятельности. Движущей силой в конфликте является любопытство или стремление человека или победить, или сохранить, или улучшить свое положение, например, безопасность, устойчивость в коллективе или надежда на успех достижения поставленной в явном или не явном виде цели. Как поступить в той или иной ситуации, часто бывает неясно. Характерной особенностью любого конфликта является то, что ни одна из участвующих сторон не знает заранее точно и полностью всех решений, принимаемых другими сторонами, их будущее поведение и, следовательно, каждый вынужден действовать в условиях неопределенности. Неопределенность исхода может быть обусловлена или сознательными действиями активных противников, или несознательными, пассивными проявлениями, например стихийных сил природы: дождя, солнца, ветра, лавины снега и т.п. В таких случаях исключается возможность точного предсказания исхода. Общность всех конфликтов независимо от их природы заключается в столкновении интересов, стремлений, целей, путей достижения целей, отсутствия согласия двух или более сторон — участников конфликта. Сложность конфликтов обусловливается разумными действиями отдельных лиц и коллективов с различными интересами. Неопределенность исхода конфликта, любопытство, интерес и стремление к победе побуждают людей к сознательному вступлению в конфликт, что притягивает к конфликтам и участников, и наблюдателей. Поэтому необходимы рекомендации по рациональному поведению в конфликтах. В последнее время все большее внимание по изучению конфликтных ситуаций начинают уделять математики. Математическая теория игр дает научно обоснованные рекомендации поведения в конфликтных ситуациях, показывая «как играть, чтобы не проиграть». Для применения этой теории необходимо уметь представлять конфликты в виде игр. Основой любого конфликта является наличие противоречия, которое принимает форму разногласий. Конфликт можно определить как отсутствие согласия между двумя или более сторонами — лицами или группами, проявляющиеся при попытке разрешить противоречие, причем часто на фоне острых эмоциональных переживаний. Следует заметить, что вовлечение в конфликт в коммерческой деятельности большого количества людей позволяет резко увеличить и обнаружить множество альтернатив и исходов, что является важной позитивной функцией конфликта, связанной с увеличением кругозора. Конфликты могут выполнять функции, как позитивные, так и негативные: Функции конфликтов Позитивные Разрядка напряженности между конфликтующими сторонами Получение новой информации об оппоненте Сплочение коллектива организации при противоборстве с внешним врагом Стимулирование к изменениям и развитию Снятие синдрома покорности у подчиненных Диагностика возможностей оппонентов Негативные Большие эмоциональные, материальные затраты на участие в конфликте Увольнение сотрудников, снижение дисциплины, ухудшение социально-психологического климата в коллективе Представление о побежденных группах, как о врагах Чрезмерное увлечение процессом конфликтного взаимодействия в ущерб работе После завершения конфликта — уменьшение степени сотрудничества между частью коллектива Сложное восстановление деловых отношений («шлейф конфликта») Причины, вызывающие конфликты, так же разнообразны, как и сами конфликты. Следует различать объективные причины и их восприятие индивидуумами. Объективные причины можно представить в виде нескольких групп: ограниченность ресурсов, подлежащих распределению; различие в целях, ценностях, методах поведения, уровне квалификации, образования; взаимосвязь заданий, неправильное распределение ответственности; плохие коммуникации. Непременно возникает вопрос о цене победы и что представляет собой поражение для другой стороны. Переговоры представляют широкий аспект общения, охватывающий многие сферы деятельности человека и представляют собой набор тактических приемов, направленных на поиск взаимоприемлемых решений для конфликтующих сторон. Для того чтобы переговоры стали возможными, необходимы такие условия: наличие взаимозависимости сторон, участвующих в конфликте; отсутствие значительного различия в возможностях (силе) субъектов конфликта; соответствие стадии развития конфликта возможностям переговоров; участие в переговорах сторон, которые реально могут принимать решения в сложившейся ситуации. Конфликт в своем развитии проходит несколько этапов. Возможности переговоров по этапам развития конфликта таковы: Варианты развития конфликта Проведение переговоров I. Напряженность, Проводить рано, составляющие несогласие конфликта не определены П. Соперничество Уместны III. Агрессивность С участием третьей стороны IV. Насилие, военные действия Невозможны, целесообразны от- ветные агрессивные действия Специалисты считают, что тщательно подготовленные переговоры, на 50% определяют успех всей дальнейшей деятельности. Цели и результаты переговоров Цели Результаты Отражают максимально интересы Наиболее благоприятны Учитывают интересы Допустимы Не учитывают интересы Неприемлемы Ущемляют интересы Совершенно неприемлемы Конфликт представляет собой процесс развивающийся во времени (рис. 12.1), который можно разделить на несколько периодов. Таковыми, например, могут быть предконфликтный период, конфликтное взаимодействие и послеконфликтный период. Напряженность с течением времени в предконфликтный период (t­0 – t1) постепенно (1) или лавинообразно (2) нарастает, а затем достигает наибольшего значения в момент кульминации t2 и затем ниспадает. Следует заметить, что зачастую конфликтное взаимодействие имеет продолжительность (t3 – t`) всего около 1 мин, а послеконф-ликтный период может быть больше его в 600-2000 и более раз. Причем показатели исхода конфликтов для обеих сторон могут совсем не содержать выигрышных показателей, т.е. одни ущербы. Рис. 12.1. Динамическая модель развития конфликта В длительных конфликтах часто доля делового содержания с течением времени уменьшается и начинает доминировать личностная сфера, что и представлено на рис. 12.2. Рис. 12.2.Изменение соотношения деловой и личностной сфер конфликта Игровую модель конфликта можно представить как сочетание отображения (рис. 12.3) возможных позитивных и негативных альтернатив (ходов) участников-игроков К и П и вариантов исходов каждой пары ходов Кi Пi, в виде платежной матрицы В = ||bij||, элемент которой можно определить по формуле: где Pijk и Мk - соответственно характеристика конфликта (в баллах) и его весомость, . Рис. 12.3. Игровая модель конфликта На рис. 12.3 показано, что действия обеих сторон негативными альтернативами (-/-) свидетельствуют о том, что с помощью «войн» понять друг друга нельзя. Позитивные действия с обеих сторон приводят к мирному исходу. Варианты альтернатив (-/+) или (+/-) могут привести к мирному варианту согласия, что определяется цепочкой причинно-следственных альтернатив в многоходовом взаимодействии. Состояние человека во взаимодействии можно интерпретировать графически в виде сочетания степени его активности и уровня настроения (рис. 12.4). Рис. 12.4. Графическая модель оценки состояния партнера Измерение этих показателей можно производить от среднего, нейтрального (0) уровня. Тогда точка состояния определяется вектором с соответствующими координатами, например М(х1,у2)- Состояние, определяемое другим вектором N(x1,y1), отличается меньшей активностью y = (у2 – у1)- Состояние партнера, определяемое вектором (х3, у2), отличается более скверным настроением, чем состояние партнера, определяемое вектором В(x2, у2). На рис. 12.5 представлена модель взаимодействия партнеров, состояния которых зафиксированы векторами А и В, в результате чего образуется конфликт-вектор Е. Эта зона готовности к конфликту из всех квадрантов является самой неблагоприятной. Пользуясь такими графическими моделями развития взаимодействия партнеров, можно заранее подготовиться к возможным исходам. Одной из типичных социально-психологических межличностных конфликтов является несбалансированное ролевое взаимодействие. Теоретическую основу анализа межличностных конфликтов предложил американский психолог Э. Берн, который предложил своеобразную сетевую модель описания взаимодействия партнеров рис. 12.6. Рис. 12.6. Сетевые модели ролевого взаимодействия партнеров Каждый человек в процессе взаимодействия с окружающими вынужден играть более десятка ролей, причем далеко не всегда успешно. В предлагаемой модели каждый партнер может имитировать роль С — старшего, Р — равного или М — младшего. Если ролевое взаимодействие сбалансировано, то общение может развиваться бесконфликтно, иначе при разбалансе ролей возможен конфликт. В процессе коммерческих переговоров приходится искать область взаимных интересов (рис. 3.4.7), позволяющую найти компромиссное решение. Делая большие уступки по менее значимым аспектам для фирмы, но более значимому для оппонента, коммерсант получает больше по другим позициям, которые более значимы и выгодны для фирмы. Эти уступки имеют минимальные и максимальные границы интересов. Это условие получило название «принцип Парето» по имени итальянского ученого В. Парето. Рис. 12.7. Область вариантов компромиссных решений на переговорах