Правильным является определение понятия исследование операций как. Предмет и задачи исследования операций

1. Основные понятия ИО

ИО – науч дисц-на, заним-­ся разработкой и практ применением методов наибо­лее эффективного упр-я различными орг сис-мами.

ИО включает в себя следующие разделы:

1) математическое прогр. (обоснование планов, программ хозяйст­венной деятельности); оно включает в себя разделы: линейное прогр, нелинейное прогр, динамическое прогр

2) теорию массового обслуживания, опирающуюся на теорию случайных процессов;

3) теорию игр, позволяющую обосновывать решения, принимаемые в усл-ях неполноты инф-ции.

При решении конкретной задачи управления применение ме­тодов ИО предполагает:

Построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;

Изучение взаимосвязей, определяющих впоследствии при­нятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного вариан­та действия.

Основные понятия и определения ИО.

Операция – любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе – от выбора некоторых пара­метров. Операция есть всегда управляемое мероприя­тие, т. е. от нас зависит, каким способом выбрать не­которые параметры, характеризующие ее организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяе­мых в операции.

Всякий определенный выбор параметров называется решением . Решения могут быть удачными и неудачными, разумными и неразум­ными. Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.

Модель операции – это достаточно точное описание операции с помощью математического аппарата (различного рода функций, уравнений, систем уравнений и неравенств и т.п.). Составление модели опе­рации требует понимания сущности описываемого явления и зна­ния математического аппарата.

Эффективность операции – степень ее приспособленности к выполнению задачи – количественно выражается в виде кри­терия эффективности – целевой функции. Выбор критерия эффективности опре­деляет практическую ценность исследования. (Неправильно выбранный критерий может принести вред, ибо операции, ор­ганизованные под углом зрения такого критерия эффективно­сти, приводят порой к неоправданным затратам.)

Задачи сетевого планирования и управления рассматривают соот­ношения между сроками окончания крупного комплекса опера­ций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стои­мости и сроков их выполнения.

Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и со­стоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п.

Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особен­ность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.

Задачи распределения ресурсов возникают при определенном на­боре операций (работ), которые необходимо выполнять при огра­ниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.

Задачи ремонта и замены оборудования актуальны в связи с из­носом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.

Задачи составления расписания (календарного планирования) со­стоят в определении оптимальной очередности выполнения опе­раций (например, обработки деталей) на различных видах обо­рудования.

Задачи планировки и размеще ния состоят в определении оп­тимального числа и места размещения новых объектов с уче­том их взаимодействия с существующими объектами и между собой.

Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспор­те и в системе связи и состоят в определении наиболее эконо­мичных маршрутов.

2. Общая задача линейного прогр. Оптим реш-е

Экономико–математическая модель

ЛП–область математики, раз­рабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограниче­ний, т. е. равенств или неравенств, связывающих эти переменные.

Методы ЛП применяют к прак­тическим задачам, в которых: 1) необходимо выбрать наилучшее решение (оптимальный план) из множества возможных; 2) решение можно выразить как набор значений некоторых переменных величии; а) ограничения, накладываемые на до­пустимые решения специфическими условиями задачи, форму­лируются в виде линейных уравнений или неравенств; 4) цель выражается в форме линейной функции основных переменных. Значения целевой функции, позволяя сопоставлять различные решения, служат критерием качества решения.

Для практического решения экономической задачи мате­матическими методами прежде всего ее следует записать с по­мощью экономико-математическую модель. Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Эта модель выра­жает закономерности экономического процесса в абстрактном виде с помощью математических соотношений.

Общая схема формирования модели: I

1) выбор некоторого числа переменных величин, заданием - числовых значений которых однозначно определяется одно из возможных состояний исследуемого явления;

2) выражение взаимосвязей, присущих исследуемому явле­нию, в виде математических соотношений (уравнения, нера­венств). Эти соотношения образуют систему ограничений задачи;

3) количественное выражение выбранного критерия опти­мальности в форме целевой функция; I

4) математическая формулировка задачи, как задачи отыс­кания экстремума целевой функции при условии выполнения ограничений, накладываемых на переменные.

Общая задача линейного программирования имеет вид:

Дана система т линейных уравнений и неравенств с п перемен­ными

и линейная функция

Необходимо найти такое решение системы X=(x1,x2,…,xj,…,xn), где при котором линейная функция F принимает оптимальное (т.е. максимальное или минимальное) значение.

Система (1) называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

при ограничениях:

Оптимальным решением (или оптимальным планом) задачи ЛП называется решение X=(x1,x2,…,xj,…,xn), системы ограничений (1), удовлетворяющее условию (3), при котором линейная функция (2) принимает опти­мальное (максимальное или минимальное) значение.

При условии, что все переменные неотрицательны, система ограничений (1) состоит лишь из одних неравенств, – такая задача линейного программирования называется стандарт­ной (симметричной); если система ограничений состоит из одних уравнений, то зада­ча называется канонической.

Частным случаем канонической задачи является задача в базисной форме, отличающаяся тем, что все коэффициенты вектора ограничений b неотрицательны, и в каждом уравнении имеется переменная с коэффициентом 1, которая не входит ни в одно из остальных уравнений. Переменная с таким свойством называется базисной.

Стандартная и каноническая задачи являются частными случаями общей. Каждая из них используется в своей определенной области. При этом все три формулировки эквивалентны между собой: любая задача линейного программирования может быть сведе­на к канонической, стандартной или общей задаче с помощью несложных математических преобразований.

4 . Элементы линейной алгебры

Система m линейных уравнений с n переменными имеет вид

или в краткой записи

Любые m переменных системы m линейных уравнений с n пере­менными (m < n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Для решения системы (2.1) при условии m < n сформулируем утверждение.

Утверждение 2.1 . Если для системы m линейных уравнений с n пере­менными (m < n ) ранг матрицы коэффициентов при переменных ра­вен т, т.е. существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произ­вольному набору значений неосновных переменных соответствует одно решение системы.

Решение X=(x1,x2,…,xn) системы (2.1) называется допустимым, если оно содержит лишь неотрицательные компоненты, т.е. xj>=0 для любых j=1,n. В противном случае решение назы­вается недопустимым.

Среди бесконечного множества решений системы выделяют так называемые базисные решения.

Базисным решением системы т линейных уравнений с n перемен­ными называется решение, в котором все n–m неосновных перемен­ных равны нулю.

В задачах линейного программирования особый интерес пред­ставляют допустимые базисные решения, или, как их еще называют, опорные планы. Базисное решение, в котором хотя бы одна из основ­ных переменных равна нулю, называется вырожденным.

Выпуклые множества точек

Общим определяющим свойством, которое отличает выпук­лый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить их отрезком, то весь отрезок будет принадлежать этому многоугольнику. Это свойство может быть принято за определение выпуклого множества точек.

Множество точек называется выпуклым , если оно вместе с лю­быми двумя своими точками содержит весь отрезок, соединяющий эти точки.

Выпуклые множества обладают важным свойством : пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.

Точка множества называется внут­ренней , если в некоторой ее окрестности содержатся точки только данного мно­жества.

Точка множества называется граничной , если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.

Особый интерес в задачах линейного программирования пред­ставляют угловые точки. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежаще­го данному множеству.

На рис. 2.4 приведены примеры различных точек многоуголь­ника: внутренней (точки М), граничной (точка N) и угловых (точки А, В, С, D, Е). Точка А – угловая, так как для любого от­резка, целиком принадлежащего многоугольнику, например, от­резка АР, она не является внутренней; точка А – внутренняя для отрезка KL, но этот отрезок не принадлежит целиком много­угольнику.

Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), в то же время для невыпуклого множества это не обязательно. Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограничен­ным , если существует шар (круг) радиуса конечной длины с цен­тром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называет­ся неограниченным.

Выпуклое замкнутое множество точек плоскости, имеющее конечное число угловых точек, называется выпуклым многоугольника), если оно ограниченное, и выпуклой многоугольной областью, если оно неограниченное.

Геометрический смысл решений неравенств, уравнений и их систем

Рассмотрим решения неравенств.

Утверждение 1. Множество решений неравенства с двумя перемен­ными a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Для определения искомой полуплоскости (верхней или ниж­ней) рекомендуется задать произвольную контрольную точку, не лежащую на ее границе – построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется и во всех точках полуплоскости, содержащей контрольную точку, и не вы­полняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке, оно не выполняется во всех точках полуплоскости, содержащей кон­трольную точку, и выполняется во всех точках другой полуплос­кости. В качестве контрольной точки удобно взять начало координат О (0;0), не лежащее на построенной прямой.

Рассмотрим множество решений систем неравенств.

Утверждение 2. Множество решений совместной системы т линей­ных неравенств с двумя переменными является выпуклым многоугольником (или выпуклой многоугольной областью).

Каждое из неравенств в соответствии с утверждением 1 опре­деляет одну из полуплоскостей, являющуюся выпуклым множест­вом точек. Множеством решений совместной системы линейных неравенств служат точки, которые принадлежат полуплоскостям решений всех неравенств, т.е. принадлежат их пересечению. Со­гласно утверждению о пересечении выпуклых множеств это множе­ство является выпуклым и содержит конечное число угловых то­чек, т.е. является выпуклым многоугольником (выпуклой много­угольной областью).

Координаты угловых точек – вершин многоугольника находят как координаты точек пересечения соответствующих пря­мых.

При построении областей решений систем неравенств могут встретиться и другие случаи: множество решений – выпуклая мно­гоугольная область (рис. 2.9, а); одна точка (рис. 2.9, б); пустое мно­жество, когда система неравенств несовместна (рис. 2.9, в).

5 . Геометрический метод решения задач ЛП

оптимальное решение задачи ЛП

Теорема 1. Если задача ЛП имеет оп­тимальное решение, то линейная функция принимает максимальное значение в одной из угловых точек многогранника решений. Если ли­нейная функция принимает максимальное значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.

Теорема указывает принципиальный путь решения задач ЛП. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необхо­димо исследовать лишь конечное число угловых точек много­гранника решений.

Следующая теорема посвящена аналитическому методу нахож­дения угловых точек.

Теорема 2. Каждому допустимому базисному решению задачи ЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Из теорем 1 и 2 непосредственно вытекает важное следст­вие: если задача ЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допусти­мых базисных решений.

Итак, оптимум линейной функции задачи ЛП следует искать среди конечного числа ее допустимых базисных решений.

Итак, множество допустимых решений (многогранник решений) задачи ЛП представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи находит­ся, по крайней мере, в одной из угловых точек многогранника решений.

Рассмотрим задачу в стандартной форме с двумя переменными (п = 2).

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 4.1). Необходимо среди то­чек этого многоугольника найти такую точку, в которой линейная функция F=c1x1+c2x2 принимает максимальное (или мини­мальное) значение.

Рассмотрим так называемую линию уровня линейной функции F , т.е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение а , т.е. F = а, или c1x1+c2x2=a.

На многоугольнике решений следует найти точку, через которую проходит линия уровня функ­ции F с наибольшим (если линейная функция максимизируется) или наименьшим (если она минимизируется) уровнем.

Уравнение линии уровня функции c1x1+c2x2=a есть уравнение прямой линии. При различных уровнях а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением меж­ду коэффициентами c1 и c2 и, следовательно, равны. Таким образом, линии уровня функции F – это своеобразные "параллели", распо­ложенные обычно под углом к осям координат.

Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уро­вень только возрастает, а при смещении в другую сторону – только убывает. Вектор c=(c1,c2), выходящий из начала координат, указывает направление наискорейшего возрастания функции F. Линия уровня линейной функции перпендикулярна вектору c=(c1,c2).

Порядок графического решения задачи ЛП:

1.Построить многоугольник решений.

2.Построить вектор c=(c1,c2), и перп-но ему провести линию уровня линейной функции F , например, F=0.

3.Параллельным перемещением прямой F=0 в направлении вектора c(-c) найти точку Amax(Bmin), в которой F достигает максимума (минимума).

1. Решая совместно уравнения прямых, пересекающихся в точке оптимума, найти ее координаты.

2.Вычислить Fmax(Fmin).

Замечание. Точка минимума – это точка «входа» в многоугольник решений, а точка максимума – это точка «выхода» из многоугольника.

6. Общая идея симплекс–метода. Геометрическая интерпретация

Графический способ применим к весьма узкому классу задач линейного программирования: эффективно им можно решать задачи, содержащие не более двух переменных. Были рассмотрены основные теоремы линейного программи­рования, из которых следует, что если задача линейного програм­мирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений систе­мы ограничений. Был указан путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограни­чений и выбрать среди них то, на котором функция цели прини­мает оптимальное решение. Геометрически это соответствует пе­ребору всех угловых точек многогранника решений. Такой пере­бор в конце концов приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, так как для реальных задач число допус­тимых базисных решений хотя и конечно, но может быть чрезвы­чайно велико.

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума, уменьшение – при отыскании минимума). Такой перебор позволяет сократить число шагов при отыска­нии оптимума. Поясним это на графическом примере.

Пусть область допустимых решений изображается многоуголь­ником ABCDE . Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать пять допустимых базисных решений, соответствующих пяти угловым точкам мно­гоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем – к оптимальной точке С. Вместо пяти перебрали только три вершины, последовательно улучшая линейную функцию.

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирова­ния – симплексного метода или метода последовательного улучшения плана.

Геометрический смысл симплексного метода состоит в последо­вательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.

Симплексный метод, позволяющий решить любую задачу ли­нейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные при­меры с применением симплексного метода можно решать и вручную.

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

способ определения какого-либо первоначального допустимого базисного решения задачи;

правило перехода к лучшему (точнее, не худшему) решению;

критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений.

В литературе достаточно подробно описываются: нахождение начального опорного плана (первоначального допустимого базисного решения), тоже – методом искусственного базиса, нахождение оптимального опорного плана, решение задач с помощью симплексных таблиц.

7 . Алгоритм симплекс–метода.

Рассмотрим решение ЗЛП симплекс-ме­тодом и изложим ее применительно к задаче максимизации.

1. По условию задачи составляется ее математическая мо­дель.

2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.

3. Каноническая модель задачи записывается в форме симп­лекс-таблицы так, чтобы все свободные члены были неотрицатель­ными. Если начальный опорный план выделен, то переходят к пункту 5.

Симплекс таблица: вписывается система ограничительных уравнений и целевая функция в виде выражений, разрешенных относительно начального базиса. Строку, в которую вписаны коэффициенты целевой функции F, называют F–строкой или строкой целевой функции.

4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не при­нимая во внимание знаки элементов F–строки. Если в ходе преоб­разований встретится 0-строка, все элементы которой, кроме сво­бодного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то систе­ма ограничительных уравнений не имеет неотрицательных ре­шений.

Приведение системы (2.55), (2.56) к новому базису будем на­зывать симплексным преобразованием . Если симплексное преобра­зование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входя­щими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот – из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.

5. Найденный начальный опорный план исследуется на опти­мальность:

а) если в F–строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нуле­вых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;

б) если в F–строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то;

в) если в F–строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно пе­рейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.

Столбец коэффициентов при переменной, включаемой в базис, называют разрешаю­щим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному эле­менту F–строки, мы обеспечиваем возрастание функции F.

Немного сложней определяется переменная, подлежащая ис­ключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (та­кие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, ис­ключаемой из базиса (или выбор разрешающей строки), по ми­нимальному симплексному отношению гарантирует, как уже уста­новлено, положительность базисных компонент в новом опорном плане.

В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обя­зательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разре­шающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:

1) просматривают строку, отвечающую какому-либо отрица­тельному свободному члену, например t–строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему стол­бец принимают за разрешающий (предполагаем, что ограничения задачи совместны);

2) составляют отношения элементов столбца свободных чле­нов к соответствующим элементам разрешающего столбца, имею­щим одинаковые знаки (симплексные отношения);

3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р –строка;

4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент y–строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на сле­дующем шаге вновь обращаются к t–строке. Если задача разреши­ма, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.

8. Метод обратной матрицы

Рассмотрим ЛП вида:

A– матрица ограничений;

C=(c1,c2,…,cn)–вектор–строка;

X=(x1,x2,…,xn)– переменные;

– вектор правой части.

Считаем, что все уравнения линейно независимы, т.е. rang(a)=m. В этом случае базис – это минор порядка матрицы A. Т.е. существует по крайней мере одна такая подматрица B порядка m, что |B|<>0. Все неизвестные, соответствующие B, называются базисными. Все остальные свободными.

Пусть B– некоторый базис. Тогда перестановкой столбцов матрицы A всегда можно привести A к виду A=(B|N),

где N – подматрица, состоящая из столбцов матрицы A, не принадлежащих базису. Точно так же возможно разбиение вектора x на – вектор базисных переменных и.

Всякое решение задачи (1) удовлетворяет условию A*x=b, и, следовательно, система приобретает такой вид:

Т.к. |B|<>0, то существует обратная матрица. Умножаем слева на обратную, получаем:

– общее решение.

Базисным решением (относительно базиса B) называется частное решение задачи (2), полученное при условии. Тогда определяется однозначно.

Базисное решение называется реализуемым , если.

Базис, соответствующий реализуемому базисному решению. Называется реализуемым базисом. Базисное решение называется вырожденным, если вектор имеет нулевые компоненты.

В общем решении заложены все решения, которые есть. Вернемся к целевой функции. Вводим Cb– коэффициенты перед базисными переменными, Cn– остальные.

Таким образом, получаем. Подставляем из общего решения:

Утверждение. Критерий оптимальности базисного решения.

Допустим. Тогда базисное решение является оптимальным. Если, то базисное решение не оптимально.

Док-во: Пусть. Рассмотрим базисное решение, .

Следовательно, – значение целевой функции при базисном решении.

Пусть имеется другое решение: (Xb,Xn).

Тогда смотрим

Т.о, базисное решение самое min. Пусть, напротив, не выполняется, т.е. существует.

Тогда существует решение для которого значение целевой функции будет меньше, чем значение целевой функции при базисном решении.

Пусть соответствует свободной переменной Xi:Xj придаем значение и вводим ее в базис, а другую переменную выводим и называем ее свободной.

Как определить? Все свободные переменные, кроме, по-прежнему равны 0, а.

Тогда в общем решении, где.

Вынесем: –необходимое условие.

Базисное решение называется регулярным, если. Переменную выводим из базиса. При новом решении целевая функция уменьшается, т.к.

Алгоритм:

1.Задача ЛП в стандартной форме.

2.Оставляем линейно независимые уравнения.

3.Находим матрицу B, такую что |B|<>0 и базисное решение.

Вычисляем:

если, то оптимальное решение есть – это базисное решение;

если, то находим компоненту, придаем, таким образом найдем другое решение; – при котором одна из базисных переменных =0. Эту переменную выбрасываем из базиса, вводим xi. Получили новый базис B2, сопряженный базису B1. Затем снова вычисляем.

1.Если есть оптимальное решение, то через конечное число шагов мы его получим.

Геометрически процедура интерпретируется как переход от угловой точки до сопряженной угловой точки вдоль границы множества Х – множества решений задачи. Т.к. существует конечное число угловых точек и строгое убывание функции F(x) запрещает дважды проходить через одну и ту же крайнюю точку, то если есть оптимальное решение, то через конечное число шагов мы его получим.

9. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

Задача. Для изготовления двух видов продукции P1 и P2 используют четыре вида ресурсов S1,S2,S3,S4. Даны запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции. Известна прибыль, получаемая от единицы продукции P1 и P2. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Задача I (исходная) :

F=c1x1+c2x2+…+CnXn->max при ограничениях:

и условии неотрицательности x1>=0, x2>=0,…,Xn>=0

Составить такой план выпуска продукции X=(x1,x2,…,Xn), при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов

Задача II (двойственная)

Z=b1y1+b2y2+…+BmYm->min

при ограничениях:

и условии неотрицательности

y1>=0, y2>=0,…,yn>=0.

Найти такой набор цен (оценок) ресурсов Y=(y1,y2,…,yn), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

В приведен­ной модели bi(i=1,2,…,m) обозначает запас ресурса Si; aij – число единиц ресурса Si, потребляемого при производстве едини­цы продукции Pj(j=1,2,…,n); cj– прибыль (выручка) от реали­зации единицы продукции Pj (или цена продукции Pj).

Предположим, что некоторая организация решила закупить ресурсы S1,S2,…,Sm предприятия и необходимо установить оп­тимальные цены на эти ресурсы y1,y2,…,ym. Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b1,b2,…,bm по ценам соответственно y1,y2,…,ym были минимальны, т.е. Z=b1,y1+b2y2+…+bmym->min.

С другой стороны, предприятие, продающее ресурсы, заинте­ресовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию.

На изготовление единицы про­дукции P1 расходуется a11 единиц ресурса S1, a21 единиц ресурса S2,…., aj1 единиц ресурса Si1 ,……, am1 единиц ресурса Sm по цене соответственно y1,y1,…,yi,…,ym. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изго­товлении единицы продукции P1 должны быть не менее ее цены c1, т.е. a11y1+a21y2+…+am1ym>=c1.

Аналогично можно составить ограничения в виде неравенств по каждому виду продукции P1,P2,…Pn. Экономико-математи­ческая модель и содержательная интерпретация полученной та­ким образом двойственной задачи II приведены в правой части таблицы.

Цены ресурсов y1,y1,…,yi,…,ym в экономической литературе полу­чили различные названия: учетные, неявные, теневые . Смысл этих названий состоит в том, что это условные , "ненастоящие" цены. В отличие от "внешних" цен c1,c2,…,cn на продукцию, известных, как правило, до начала производства, цены ресурсов y1,y2,…,ym являются внутренними , ибо они задаются не извне, а определяют­ся непосредственно в результате решения задачи, поэтому их ча­ше называют оценками ресурсов.

10.Взаимно двойственные задачи ЛП и их свойства

Рассмотрим формально две задачи I и II линейного програм­мирования, представленные в таблице, абстрагируясь от содержа­тельной интерпретации параметров, входящих вих экономико-математические модели.

Обе задачи обладают следующими свой­ствами:

1.В одной задаче ищут максимум линейной функции, в другой – минимум.

2.Коэффициенты при переменных в линейной функции одной за­дачи являются свободными членами системы ограничений в другой.

3.Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "<=", а в задаче минимизации – все неравенства вида ">=".

4.Матрицы коэффициентов при переменных в системах ограни­чений обеих задач являются транспонированными друг к другу.

5.Число неравенств в системе ограничений одной задачи совпа­дает с числом переменных в другой задаче.

6.Условия неотрицательности переменных сохраняются в обеих за­дачах.

Замечание. Если на j-ю переменную исходной задачи наложено условие неотрицательности, то j-е ограничение двойственной задачи будет неравенством, если же j-я переменная может принимать как положительные, так и отрицательные значения, то j-е ограничение двойственной задачи будет уравнением; аналогично связаны между собой ограничения исходной задачи и переменные двойственной.

Две задачи I и II линейного программирования, обладающие ука­занными свойствами, называются симметричными взаимно двойст­венными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами.

Каждой задаче ЛП можно поставить в соответствие двойственную ей задачу.

11. Алго­ритм составления двойственной задачи:

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут мак­симум линейной функции, то все неравенства системы ог­раничений привести к виду "<=", а если минимум – к виду ">=". Для этого неравенства, в которых данное требование не выполняется, умножить на –1.

2. Составить расширенную матрицу системы A, в которую включить матрицу коэффициентов при переменных, стол­бец свободных членов системы ограничений и строку ко­эффициентов при переменных в линейной функции.

3. Найти матрицу, транспонированную к матрице A.

4. Формулируют двойственную задачу на основании полученной матрицы и условия неотрицательности переменных: составляют целевую функцию двойственной задачи, взяв за коэффициенты при переменных свободные члены системы ограничений исходной задачи; составляют систему ограничений двойственной задачи, взяв в качестве коэффициентов при переменных элементы матрицы, а в качестве свободных членов – коэффициенты при переменных в целевой функции исходной задачи, и записывают неравенства противоположного смысла; записывают условие неотрицательности переменных двойственной задачи.

12. Первая теорема двойственности

Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности.

Достаточный признак оптимальности.

Если X*=(x1*,x2*,…,xn*) и Y*=(y1*,y2*,…,ym*) – допус­тимые решения взаимно двойственных задач, для которых выполня­ется равенство,

то – оптимальное решение исходной задачи I, а – двойст­венной задачи II.

Кроме достаточного признака оптимальности взаимно двойствен­ных задач существуют и другие важные соотношения междуих ре­шениями. Прежде всего возникают вопросы: всегда ли для каждой пары двойственных задач есть одновременно оптимальные решения; возможна ли ситуация, когда одна из двойственных задач имеет ре­шение, а другая нет. Ответ на эти вопросы дает следующая теорема.

Первая (основная) теорема двойственности. Если одна из вза­имно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны:

Fmax = Zmin или F(X*)=Z(Y*).

Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы (задача не имеет решения).

Замечание. Утверждение, обратное по отношению ко второй части основной теоремы двойственности, в общем случае не­верно, т.е. из того, что условия исходной задачи противоречи­вы, не следует, что линейная функция двойственной задачи не ограничена.

Экономический смысл первой теоремы двойственно­сти.

План производства X*=(x1*,x2*,…,xn*) и набор цен (оценок) ресурсов Y*=(y1*,y2*,…,ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при "внешних" (известных заранее) ценах c1,c2,…,cn, равна затратам на ресурсы по "внутренним " (определяемым только из решения зада­чи) ценам y1,y2,…,ym. Для всех же других планов Х и Y обеих задач прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы.

Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X*=(x1*,x2*,…,xn*) и по­лучить максимальную прибыль (выручку) Fmax либо продавать ресурсы по оптимальным ценам Y*=(y1*,y2*,…,ym*) и возместить от продажи равные ей минимальные затраты на ресурсы Zmin.

13. Вторая теорема двойственности

Пусть даны две взаимно двойственные задачи. Если каждую из этих задач решать сим­плексным методом, то необходимо привести их к каноническому виду, для чего в систему ограничений задачи I (в краткой записи) следует ввести т неотрица­тельных переменных, а в систему ограничений задачи II () – n неотрицательных переменных, где i(j) – номер неравенства, в которое введена дополнительная переменная.

Системы ограничений каждой из взаимно двойственных задач примут вид:

Установим соответствие между первоначальными переменны­ми одной из двойственных задач и дополнительными перемен­ными другой задачи (таблица).

Теорема. Положительным (ненулевым) компонентам оптимально­го решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i=1,2,…,m u j=1,2,…,n: если X*j>0, то; если , то, и аналогично,

если, то ; если, то.

Из данной теоремы следует важный вывод о том, что вве­денное соответствие между переменными взаимно двойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения.

Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффи­циентов при соответствующих переменных линейной функции исход­ной задачи, выраженной через неосновные переменные ее оптимально­го решения.

Замечание. Если в одной из взаимно двойственных задач нару­шается единственность оптимального решения, то оптимальное решение двойственной задачи вырожденное. Это связано с тем, что при нарушении единственности оптимального решения исходной задачи в выражении линейной функции ее опти­мального решения через неосновные переменные отсутствует хотя бы одна из основных переменных.

14. Объективно обусловленные оценки и их смысл

Компоненты оптимального решения двойственной задачи называ­ются оптимальными (двойственными) оценками исходной задачи. Академик Л.В.Канторович назвал их объективно обусловленным» оценкам (в литературе их еще называют скрытыми доходами).

Дополнительные переменные исходной задачи I, представляющие разность между запасами bi ресурсов S1,S2,S3,S4 и их потреблением, вы­ражают остатки ресурсов , а дополнительные переменные двойст­венной задачи II, представляющие разность между затратами на ресурсы для производст­ва из них единицы продукции и ценами cj продукции P1,P2, вы­ражают превышение затрат над ценой.

Т.о, объективно обусловленные оценки ресурсов оп­ределяют степень дефицитности ресурсов: по оптимальному пла­ну производства дефицитные (т.е. полностью используемые) ре­сурсы получают ненулевые оценки, а недефицитные – нулевые оценки. Величина y*i является оценкой i-го ресурса. Чем больше значение оценки y*i, тем выше дефицитность ресурса. Для недефицитного ресурса y*i=0.

Итак, в оптимальный план производства могут попасть толь­ко рентабельные, неубыточные виды продукции (правда, крите­рий рентабельности здесь своеобразный: цена продукции не превышает затраты на потребляемые при ее изготовлении ре­сурсы, а в точности равна им).

Третья теорема двойственности . Компоненты оптимального решения двойственной задачи равны значениям частных производных линейной функции Fmax (b 1, b 2,…, bm ) по соответствующим аргументам, т.е.

Объективно обусловленные оценки ресурсов показывают, на сколько денежных единиц изменится максимальная прибыль (выручка) от реализации продукции при изме­нении запаса соответствующего ресурса на одну единицу.

Двойственные оценки могут служить инструментом анализа и принятия правильных решений в условиях постоянно меняюще­гося производства. Так, например, с помощью объективно обуслов­ленных оценок ресурсов возможно сопоставление оптимальных услов­ных затрат и результатов производства.

Объективно обусловленное оценки ресурсов позволяют судить об эффекте не любых, а лишь сравнительно небольших изменений ресур­сов. При резких изменениях сами оценки могут стать другими, что приведет к невозможности их использования для анализа эф­фективности производства. По соотношениям объективно обусловленных оценок могут быть определены расчетные нормы заменяемости ресурсов, при соблюде­нии которых проводимые замены в пределах устойчивости двой­ственных оценок не влияют на эффективность оптимального плана. Вывод. Двойственные оценки являются:

1. Показателем дефицитности ресурсов и продукции.

2.Показателем влияния ограничений на значение целевой функции.

3.Показателем эффективности производства отдельных видов продукции с позиций критерия оптимальности.

4.Инструментом сопоставления суммарных условных затрат и результатов.

15.Постановка транспортной задачи по критерию стоимости.

ТЗ - задача о наиболее экономном плане перевозок однородного или взаимозаменяемого продукта из пунк­та производства (станций отправления) в пункты потребления (станции назначения) - является важнейшей частной задачей ЛП, имеющей обширные практические при­ложения не только к проблемам транспорта.

ТЗ выделяется в ЛП определенностью экономической характеристики, особенностя­ми математической модели, наличием специфических методов ре­шения.

Простейшая формулировка ТЗ по критерию стоимости следующая: в т пунктах отправления A1,…,Am на­ходится соответственно a1,…,am единиц однородного груза (ре­сурсы), который должен быть доставлен n потребителям B1,…,Bn в количествах b1,…,bn единиц (потребности). Известны транспорт­ные издержки Cij перевозок единицы груза из i-го пункта отправ­ления в j- й пункт потребления.

Требуется составить план перевозок, т. е. найти, сколько еди­ниц груза должно быть отправлено из i-го пункта отправления в j- й пункт потребления так, чтобы полностью удовлетворить по­требности и чтобы суммарные издержки на перевозки были мини­мальными.

Для наглядности условия ТЗ представим в виде таблицы, которая называется распределительной .

Поставщик	Потребитель			Запас груза
Потребность

Здесь количество груза, перевозимого из i-го пункта отправления в j- й пункт назначения, равно xij, запас груза в i-м пункте отправ­ления определяется величиной ai>=0, а потребность j-го пункта назначения в грузе равна bj>=0. Предполагается, что все xij>=0.

Матрица называется матрицей тарифов (издержек или транспортных расходов).

Планом транспортной задачи называется матрица, где каждое число xij обозначает количество единиц груза, которое надо доставить из i-го пункта отправления в j-й пункт назначения. Матрицу xij называют матрицей перевозок.

Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией

Переменные xij должны удовлетворять ограничениям по запа­сам, по потребителям и условиям неотрицательности:

– ограничения по запасам (2);

– ограничения по потребителям (2);

– условия неотрицательности (3).

Таким образом, математически транспортная задача формули­руется следующим образом. Даны система ограничений (2) при условии (3) и целевая функция (1). Требуется среди множества решений системы (2) найти такое неотрицательное решение, ко­торое минимизирует функцию (1).

Система ограничений задачи (1) – (3) содержит m+n уравнений с т n переменными. Предполагается, что суммарные за­пасы равны суммарным потребностям, т. е.

16. Признак разрешимости транспортной задачи

Для того чтобы транспортная задача имела до­пустимые планы, необходимо и достаточно выполнения равен­ства

Различают два типа транспортных задач: закрытые , в кото­рых суммарный объем груза поставщиков равен суммарному спро­су потребителей, и открытые , в которых суммарная производственная мощность по­ставщиков превышает спрос потребителей или спрос потребителей больше фактической суммарной мощности поставщиков, т. е.

Открытую модель можно преобразовать в закрытую. Так, если, то в математическую модель транспортной задачи вводится фиктивный (n+1)-й пункт назначения. Для этого в мат­рице задачи предусматривается дополнительный столбец, для которого потребность равна разности между суммарной мощностью по­ставщиков и фактическим спросом потребителей:

Все тарифы на доставку груза в этот пункт будем считать равны­ми нулю. Этим самым открытая модель задачи преобразуется в закрытую. Для новой задачи целевая функция всегда одна и та же, так как цены на дополнительные перевозки равны нулю. Ины­ми словами, фиктивный потребитель не нарушает совместности системы ограничений.

Если же, то вводится фиктивный (m+1)-й пункт отправления, которому приписывают запас груза, равный.

Тарифы на доставку грузов от этого фиктивного поставщика опять полагаем равными нулю. В матрице добавится одна строка, на целевую функцию это не повлияет, а система ограничений за­дачи станет совместной, т. е. станет возможным отыскание опти­мального плана.

Для транспортной задачи важное значение имеет следующая теорема.

Теорема. Ранг матрицы транспортной задачи на единицу меньше числа уравнений, т. е. r ( a )= m + n -1.

Из теоремы следует, что каждый опорный план должен иметь (m-1)(n-1) свободных пере­менных, равных нулю, и m+n-1 базисных переменных.

План перевозок транспортной задачи будем отыскивать непо­средственно в распределительной таблице. Примем, что если переменная xij принимает значение, то в соот­ветствующую клетку (I,j) будем записывать это значение, если же xij=0, то клетку (I,j) оставим свободной. С учетом теоремы о ранге матрицы в распределительной таблице опорный план должен содержать m+n-1 занятых клеток , а остальные будут свободные.

Указанные требования к опорному плану не являются единст­венными. Опорные планы должны удовлетворять еще одному тре­бованию, связанному с циклами.

Набор клеток матрицы перевозок, в котором две и только две соседние клетки расположены в одной строке или в одном столбце и последняя клетка набора лежит в той же строке или столбце, что и первая, называется замкнутым циклом .

Графически цикл представляет собой замкнутую ломаную линию, вершины которой расположены в занятых клетках таблицы, а звенья расположены только в строках или столбцах. При этом в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое в столбце. Если ломаная линия, образующая цикл, пересекает саму себя, то точки самопересечения не являются вершинами.

С набором клеток цикла связаны следующие важные свойства планов транспортной задачи:

1) допустимый план транспортной задачи является опорным тогда и только тогда, когда из занятых этим планом клеток нельзя образовать ни одного цикла;

2) если имеем опорный план, то для каждой свободной клетки можно об­разовать только один цикл, содержащий данную клет­ку и некоторую часть занятых клеток.

17. Построение исходного опорного плана

Правило «северо-западного угла».

Для составления исходного плана перевозок удобно пользо­ваться правилом «северо-западного угла», которое состоит в сле­дующем.

Будем заполнять, начиная с левого верхнего, услов­но называемого «северо-западным углом», двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1; 1) меньшее из чисел a1 и b1, т. е. . Если, то и первый столбец «закрыт», т. е. спрос первого потребителя удовлетворен полностью. Это означает, что для всех остальных клеток первого столбца количество груза для .

Если, то аналогично «закрывается» пер­вая строка, т. е. , для . Переходим к заполнению соседней клетки (2; 1), в которую заносим.

Заполнив вторую клетку (1; 2) или (2; 1), переходим к за­полнению следующей третьей клетки по второй строке либо по второму столбцу. Будем продолжать этот процесс до тех пор, по­ка на каком-то этапе не исчерпаются ресурсы am и потребности bn. Последняя заполненная клетка окажется лежащей в последнем n-м столбце и в последней m-й строке.

Правило «минимального элемента».

Исходный опорный план, построенный по правилу «северо-западного угла», обычно оказывается весьма далеким от опти­мального, так как при его определении не учитываются величины затрат cij. Поэтому в дальнейших расчетах потребуется много ите­раций для достижения оптимального плана. Число итераций мож­но сократить, если исходный план строить по правилу «минималь­ного элемента». Сущность его состоит в том, что на каждом шаге осуществляется максимально возможное «перемещение» груза в клетку с минимальным тарифом cij. Заполнение таблицы начинаем с клетки, которой соответст­вует наименьший элемент cij матрицы тарифов. В клетку с наи­меньшим тарифом помещают меньшее из чисел ai или bj. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответ­ствующий потребителю, спрос которого полностью удовлетворен. Может оказаться, что следует исключить строку и столбец одно­временно, если полностью израсходованы запасы поставщика и полностью удовлетворен спрос потребителя. Далее из оставших­ся клеток таблицы снова выбирают клетку с наименьшим тарифом и процесс распределения запасов продолжают до тех пор, пока все они не будут распределены, а спрос удовлетворен.

18. Метод потенциалов

Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи ЛП симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.

Сущность метода потенциалов состоит в следующем. После того как найден исходный опорный план перевозок, каждому по­ставщику (каждой строке) ставим в соответствие некоторое число, называемое потенциалом поставщика Ai , а каждо­му потребителю (каждому столбцу) – некоторое число назы­ваемое потенциалом потребителя.

Стоимость тонны груза в пункте равна стоимости тонны груза до перевозки + затраты на ее перевозку: .

Чтобы решить транспортную задачу методом потенциалов, необходимо:

1. Построить опорный план перевозок по одному из изложенных правил. Число заполненных клеток должно быть m+n-1.

2. Вычислить потенциалы и соответственно по­ставщиков и потребителей (для занятых клеток): . Число заполненных клеток – m+n-1, а число уравнений – m+n. Т.к. число уравнений на единицу меньше числа неизвестных, то одно из неизвестных оказывается свободным и может принимать любое числовое значение. Например, . Остальные потенциалы для данного опорного решения определятся однозначно.

3. Проверить на оптимальность, т.е. для свободных клеток вычислить оценки. Если, то перевозка целесообразна и план X оптимален – признак оптимальности. Если хотя бы одна разность, то переходят к новому опорному плану. По своему экономическому смыслу величина характеризует то изменение в суммарных транспортных расходах, которое произойдет из-за осуществления единичной поставки i-м поставщиком j-му потребителю. Если, то единичная поставка приведет к экономии транспортных расходов, если же – к увеличению их. Следовательно, если среди свободных направлений поставок нет экономящих транспортные расходы направлений, то полученный план оптимален.

4. Среди положительных чисел выбирают максимальное, строят для свободной клетки, которой оно соответствует цикл пересчета. После того как для выбранной свободной клетки цикл построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой циклом пересчета.

а) Каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем данной свободной клетке «+», а всем остальным клеткам (вершинам цикла) – поочередно знаки «–» и «+». Будем называть эти клетки минусовыми и плюсовыми.

б) В минусовых клетках цикла находим минимальную поставку, которую обозначим через. В данную свободную клетку переносят меньшее из чисел xij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком «+», и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой и входит в опорный план; а минусовая клетка, в которой стояло минимальное из чисел xij, считается свободной и выходит из опорного плана.

Т.о., определили новый опорный план. Описанный выше переход от одного опорного плана к другому называется сдвигом по циклу пересчета. При сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным m+n-1. При этом если в минусовых клетках имеется два или более одинаковых числа xij, то освобождают лишь одну из таких клеток, а остальные оставляют занятыми с нулевыми поставками.

5. Полученный опорный план проверяют на оптимальность, т.е. повторяют все действия с п.2.

19. Понятие о динамическом программировании.

ДП (планирование) представляет собой математический метод для нахождения оптимальных решений многошаговых (многоэтапных) задач. Некоторые из таких задач естественным образом распадаются на отдельные шаги (этапы), но имеются задачи, в которых разбиение приходится вводить искусственно, для того чтобы их можно было решить методом ДП.

Обычно методами ДП оптимизируют работу некоторых управляемых систем, эффект которой оценивается аддитивной , или мультипликативной , целевой функцией. Аддитивной называется такая функция нескольких переменных f(x1,x2,…,xn), значение которой вычисляется как сумма некоторых функций fj, зависящих только от одной переменной xj: . Слагаемые аддитивной целевой функции соответствуют эффекту решений, принимаемых на отдельных этапах управляемого процесса.

Принцип оптимальности Р. Беллмана.

Смысл подхода, реализуемого в динамическом программировании, заключен в замене решения исходной многомерной задачи последовательностью задач меньшей размерности. Основные требования к задачам:

1. объектом исследования должна служить управляемая сис­тема (объект) с заданными допустимыми состояниями и допустимыми управлениями ;

2. задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия реше­ния о выборе одного из допустимых управлений, приводя­щих к изменению состояния системы;

3. задача не должна зависеть от количества шагов и быть опре­деленной на каждом из них;

4. состояние системы на каждом шаге должно описываться оди­наковым (по составу) набором параметров;

5. последующее состояние, в котором оказывается система пос­ле выбора решения на k-м шаге, зависит только от данного решения и исходного состояния к началу k - го шага. Данное свойство является основным с точки зрения идеологии дина­мического программирования и называется отсутствием последствия .

Рассмотрим вопросы применения модели динамического про­граммирования в обобщенном виде. Пусть стоит задача управ­ления некоторым абстрактным объектом, который может пре­бывать в различных состояниях. Текущее состояние объекта отождествится с некоторым набором параметров, который обознача­ется в дальнейшем S и называется вектором состояния . Пред­полагается, что задано множество S всех возможных состоя­ний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляю­щие воздействия могут осуществляться в дискретные моменты времени, причем управленческое решение заключается в выборе одного из управлений. Планом задачи или стратегией управления называется вектор x=(x1,x2,…,xn-1), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последователь­ными состояниями объекта Sk и Sk+1, существует известная функциональная зависимость, включающая также выбранное управление: . Тем самым задание на­чального состояния объекта и выбор плана х однозначно определяют траекторию поведения объекта.

Эффективность управления на каждом шаге k зависит от текущего состояния Sk, выбранного управления xk и количе­ственно оценивается с помощью функций fk(xk,Sk), являющих­ся слагаемыми аддитивной целевой функции , характеризую­щей общую эффективность управления объектом. (Отметим, что в определение функции fk(xk,Sk) включается область до­пустимых значений xk, и эта область, как правило, зависит от текущего состояния Sk). Оптимальное управление , при задан­ном начальном состоянии S1, сводится к выбору такого опти­мального плана x* , при котором достигается максимум суммы значений fk на соответствующей траектории.

Основной принцип динамического программирования заклю­чается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции fk(xk,Sk), а выбирать оптимальное управление x*k в предположении об оптимально­сти всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шаге k условных оптимальных управлений , обеспечивающих наи­большую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние S.

Обозначим Zk(s) максимальное значение суммы функций fk на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии S. Тогда функции Zk(s) должны удовлетворять рекуррентному соотношению:

Это соотношение называют основным рекуррентным со­отношением (основным функциональным уравнением) динамического программирования. Оно реализу­ет базовый принцип динамического программирования, извест­ный также как принцип оптимальности Беллмана :

Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было начальное состо­яние sk на k-м шаге и выбранное на этом шаге управле­ние xk, последующие управления (управленческие реше­ния) должны быть оптимальными по отношению к cocmo янию , получающемуся в результа­те решения, принятого на шаге k .

Основное соотношение позволяет найти функции Zk(s) только в сочетании с начальным условием, каковым в нашем случае является равенство.

Сформулированный выше принцип оптимальности применим только для управления объектами, у которых выбор оптимального управленияне зави­сит от предыстории управляемого процесса, т. е. от того,какимпутем система пришла в текущее состояние. Именноэто обсто­ятельство позволяет осуществить декомпозицию задачи и сде­лать возможным ее практическое решение.

Для каждой конкретной задачи функциональное уравнение имеет свой специфический вид, но в нем непременно должен сохраняться рекуррентный характер, заложенный в выражении (*) и воплощающий основную идею принципа оптимальности.

20. Понятие об игровых моделях.

Математи­ческая модель конфликтной ситуации называется игрой , стороны, участвующие в конфликте, – игроками, а исход конфликта – выигрышем .

Для каждой формализованной игры вводятся правила , т.е. система условий, определяющая: 1) варианты действий игро­ков; 2) объем информации каждого игрока о поведении партне­ров; 3) выигрыш, к которому приводит каждая совокупность дей­ствий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, выигрыш – единицей, а ничью – 1/2. Количественная оценка результатов игры называется платежом .

Игра называется парной , если в ней участвуют два игрока, и множественной , если число игроков больше двух. Мы будем рас­сматривать только парные игры. В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем пони­мать ряд действий со стороны А и В.

Игра называется игрой с нулевой суммой, или антагонистиче­ ской , если выигрыш одного из игроков равен проигрышу другого, т.е. сумма выигрышей обеих сторон равна нулю. Для полного задания игры достаточно указать величину одно­го изних. Если обозначить а – выигрыш одного из игроков, b – выигрыш другого, то для игры с нулевой суммой b = –а , поэтому достаточно рассматривать, например а.

Выбор и осуществление одного из предусмотренных правила­ми действий называется ходом игрока. Ходы могут быть личными и случайными . Личный ход – это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Набор возможных вариантов при каждом личном ходе регламентирован правилами игры и зависит от всей совокупности предшествующих ходов с обеих сторон.

Случайный ход – это случайно выбранное действие (напри­мер, выбор карты из перетасованной колоды). Чтобы игра была математически определенной, правила игры должны для каждого случайного хода указывать рас­пределение вероятностей возможных исходов.

Некоторые игры могут состоять только из случайных ходов (так называемые чисто азартные игры) или только из личных ходов (шахматы, шашки). Большинство карточных игр принадлежит к играм смешанного типа, т. е. содержит как случайные, так и личные ходы. В дальнейшем мы будем рассматривать только личные ходы игроков.

Игры классифицируются не только по характеру ходов (личные, случайные), но и по характеру и по объему инфор­мации, доступной каждому игроку относительно действий другого. Особый класс игр составляют так называемые «игры с полной информацией». Игрой с полной информацией назы­вается игра, в которой каждый игрок при каждом личном ходе знает результаты всех предыдущих ходов,как личных, так и случайных. Примерами игр с полной информацией могут служить шахматы, шашки, а также известная игра «крестики и нолики». Большинство игр, имеющих практическое значение, не при­надлежит к классу игр с полной информацией, таккак неиз­вестность по поводу действий противника обычно является существенным элементом конфликтных ситуаций.

Одним из основных понятий теории игр является понятие стратегии .

Стратегией игрока называется совокупность правил, опреде­ляющих выбор его действия при каждом личном ходе в зависимо­сти от сложившейся ситуации. Обычно в процессе игры при каж­дом личном ходе игрок делает выбор в зависимости от конкрет­ной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуа­цию). Это означает, что игрок выбрал определенную стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ). Игра называется конечной , если у каждого игрока имеется конечное число страте­гий, и бесконечной .– в противном случае.

Для того чтобы решить игру, или найти решение игры , следует для каждого игрока выбрать стратегию, которая удовле­творяет условию оптимальности , т.е. один из игроков должен по­лучать максимальный выигрыш, когда второй придерживается своей стратегии, В то же время второй игрок должен иметь минимальный проигрыш , если первый придерживается своей стратегии. Такие стратегии называются оптимальными . Оптимальные стратегии должны также удовлетворять условию устойчивости , т.е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.

Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в каждой конкретной пар­тии, а средний выигрыш (проигрыш) во всех партиях.

Целью теории игр является определение оптимальной стратегии для каждого игрока.

21. Платежная матрица. Нижняя и верхняя цена игры

Конечная игра, в которой игрок А имеет т стратегий, а игрок В – п стратегий, называется игрой m×n.

Рассмотрим игру m×n двух игроков А и В («мы» и «противник»).

Пусть игрок А располагает т личными стратегиями, которые обозначим A1,A2,…,Am. Пусть у игрока В имеется n личных стратегий, обозначим их B1,B2,…,Bn.

Пусть каждая сторона выбрала определенную стратегию; для нас это будет Ai, для противника Bj. В результате выбора игроками любой пары стратегий Ai и Bj () однозначно определяется исход игры, т.е. выигрыш aij игрока А (положительный или отрицательный) и проигрыш (-aij) игрока В.

Предположим, что значения aij известны для любой пары страте­гий (Ai,Bj). Матрица P=aij , элементами которой являются выигрыши, соответствующие страте­гиям Ai иBj, называется платежной матрицей или матрицей игры. Строки этой матрицы соот­ветствуют стратегиям игрока А, а столбцы – стратегиям игрока B . Эти стратегии называются чистыми.

Матрица игры m×n имеет вид:

Рассмотрим игру m×n с матрицей и определим наилучшую среди стратегий A1,A2,…,Am. Выбирая стратегию Ai игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj для которой выигрыш для иг­рока А минимален (игрок В стремится "навредить" игроку A ).

Обозначим через наименьший выигрыш игрока А при вы­боре им стратегии Ai для всех возможных стратегий игрока В (наименьшее число в i -й строке платежной матрицы), т.е.

Среди всех чисел () выберем наибольшее: .

Назовем нижней ценой игры, или максимальным выигрышем (максмином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

Стратегия, соответствующая максимину, называется максиминной стратегией . Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А, выбирая стратегию Bj он учитывает макси­мально возможный при этом выигрыш для А. Обозначим

Среди всех чисел выберем наименьшее

и назо­вем верхней ценой игры или минимаксным выигрышем (минимаксом). Эго гарантированный проигрыш игрока В . Следова­тельно,

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

Принцип, диктующий игрокам выбор наиболее "осторожных" минимаксной и максиминной стратегий, называется принципом минимакса . Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.

Теорема. Нижняя цена игры всегда не превосходит верхней цены игры .

Если верхняя и нижняя цены игры совпадают, то общее значе­ние верхней и нижней цены игры называется чистой ценой игры, или ценой игры. Минимакс­ные стратегии, соответствующие цене игры, являются оптимальными стратегиями , а их совокупность – оптимальным решением или решением игры. В этом случае игрок А получает максимальный га­рантированный (не зависящий от поведения игрока В) выигрыш v , а игрок В добивается минимального гарантированного (вне зависи­мости от поведения игрока А) проигрыша v . Говорят, что решение игры обладает устойчивостью , т.е. если один из игроков придержи­вается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.

Если один из игроков (например А) придерживается своей оптимальной стратегии, а другой игрок (В) будет любым способом отклоняться от своей оптимальной стра­тегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным; такое отклонение игрока В может в лучшем случае оставить выигрыш неизменным. а в худшем случае – увеличить его.

Наоборот, если В придерживается своей оптимальной стратегии, а А отклоняется от своей, то это ни в коем случае не может быть выгодным для А.

Пара чистых стратегий и дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент явля­ется одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется силовой точкой. В геометрии точку на поверхности, обладающую свойством: одновременный минимум по одной координате и максимум по другой, называют силовой точкой, по аналогии этот термин применяют в теории игр.

Игра, для которой , называется игрой с силовой точкой. Элемент, обладающий этим свойством, силовой точкой матрицы.

Итак, для каждой игры с силовой точкой существует решение, определяющее пару оптимальных стратегий обеих сторон, отличающуюся следующими свойствами.

1) Если обе стороны придерживаются своих оптимальных стратегий, то средний выигрыш равен чистой цене игры v , одновременно являющейся ее нижней и верхней ценой.

2) Если одна из сторон придерживается своей оптимальной стратегии, а другая отклоняется от своей, то от этого отклоняющаяся сторона может только потерять и ни в коем случае не может увеличить свой выигрыш.

В теории игр доказывается, что, в частности, каждая игра с полной информацией имеет силовую точку, и, сле­довательно, каждая такая игра имеет решение, т. е. суще­ствует пара оптимальных стратегий той и другой стороны, дающая средний выигрыш, равный цене игры. Если игра с полной информацией состоит только из личных ходов, то при применении каждой стороной своей оптимальной стратегии она должна всегда кончаться вполне определенным исходом, а именно, выигрышем, в точности равным цене игры.

22. Решение игры в смешанных стратегиях.

Среди конечных игр, имеющих практическое значение, сравнительно редко встречаются игры с силовой точкой; более типичным является случай, когда нижняя и верхняя цена игры различны. Анализируя матрицы таких игр, приходим к заключению, что если каждому игроку предоставлен выбор одной-единственной стратегии, то в расчете на разумно действующего противника этот выбора должен определяться принципом минимакса. Придерживаясь своей максиминной стратегии, мы при любом поведении противника заведомо гарантируем себе выигрыш, равный нижней цене игры αТакие комбинированные стратегии, состоящие в приме­нении нескольких чистых стратегий, чередующихся по случайному закону с определенным соотношением частот, в теории игр называются смешанными стратегиями

Смешанной стратегией Sa игрока A называется применение чистых стратегий A1,A1,…,Ai,…,Am с вероятностями p1,p2,…pi,…pm, причем сумма вероятностей равна 1: . Смешанные стратегии игрока A записываются в виде матрицы

или в виде строки Sa=(p1,p2,…,pi,…,pm).

Аналогично смешанные стратегии игрока B обозначаются:

Или Sb=(q1,q2,…,qi,…,qn),

где сумма вероятностей появления стратегий равна 1: .

Очевидно, каждая чистая стратегия является частным случаем смешанной, в которой все стратегии, кроме одной, применяются с нулевыми частотами (вероятностями), а данная – с часто­той (вероятностью) 1.

Оказывается, что, применяя не только чистые, но и сме­шанные стратегии, можно для каждой конечной игры полу­чить решение, т. е. пару таких (в общем случае смешан­ных) стратегий, что при применений их обоими игроками выигрыш будет равен цене игры, а при любом односторон­нем отклонении от оптимальной стратегии выигрыш может измениться только в сторону, невыгодную для отклоняюще­гося. Итак, на основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей опти­мальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v . Цена игры удовлетворяет неравенству:

Где α и β – нижняя и верхняя цены игры.

Высказанное утверждение составляет содержание так на­зываемой основной теоремы теории игр. Эта теорема была впервые доказана Джоном фон Нейманом в 1928 г. Известные дока­зательства теоремы сравнительно сложны; поэтому приведем только ее формулировку.

Каждая конечная игра имеет, по крайней мере одно оптимальное решение, возможно среди смешанных стратегий.

Из основной теоремы следует, что каждая ко­нечная игра имеет цену.

Пусть и – пара опти­мальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной (полезной) .

Справедлива теорема об активных стратегиях : если один из игро­ков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

Игрок может пользоваться любой из своих активных стратегий в чистом виде, а также может смешивать их в любых пропорциях.

Эта теорема имеет большое практическое значение – она дает конкретные модели нахождения оптимальных стратегий при от­сутствии седловой точки.

Рассмотрим игру размера 2х2 , которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение – это пара чистых стратегий, соответст­вующих этой точке.

Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий и.

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии , то его средний выигрыш будет равен цене игры v , какой бы активной стратегией ни пользовался игрок В. Для игры 2х2 любая чистая стратегия противника является активной, если отсутствует ссдловая точка. Выигрыш игрока А (проигрыш игрока В) – случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выиг­рыш игрока А (оптимальная стратегия) будет равен v и для 1-й, и для 2-й стратегии противника.

Пусть игра задана платежной матрицей.

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию, а игрок В – чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы Р), равен цене игры v : .

Тот же средний выигрыш получает игрок А , если 2-й игрок применяет стратегию B2, т.е. . Учитывая, что, получаем систему уравнений для определения опти­мальной стратегии и цены игры v :

Решая эту систему, получим оптимальную стратегию

и цену игры.

Применяя теорему об активных стратегиях при отыскании – оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (A 1 или A 2) средний проигрыш игрока В равен цене игры v , т.е.

Тогда оптимальная стратегия определяется формулами: .

Задача решения игры, если ее матрица не содержит седловой точки, тем сложней, чем больше значения m и n . Поэтому в теории матричных игр рассматриваются способы, с помощью которых решение одних игр сводится к решению других, более простых, в частности, с помощью сокращения размерности матрицы. Сократить размерность матрицы можно, исключая дублирующие и заведомо невыгодные стратегии.

Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в платежной матрице, т.е. матрица содержит одинаковые строки (столбцы).

Если все элементы i-ой строки матрицы меньше соответствующих элементов k-ой строки, то i-ая стратегия для игрока А невыгодная (выигрыш меньше).

Если все элементы r-го столбца матрицы больше соответствующих элементов j-го столбца, то для игрока В r-ая стратегия невыгодная (проигрыш больше).

Процедура вычеркивания дублирующих и заведомо невыгодных стратегий всегда должна предшествовать решению игры.

23. Геометрическая интерпретация игры 2×2

Решение игры 2×2 допускает наглядную геометрическую ин­терпретацию.

Пусть игра задана платежной матрицей P=(aij), i, j=1,2.

По оси абсцисс (рис.) отложим единичный отрезок A1A2; точка A1 (х =0) изображает стратегию A1, точка A2 (х =1) изображает стратегию A2, а все промежуточ­ные точки этого отрезка – смешанные стратегии Sa первого иг­рока, причем расстояние от Sa до правого конца отрезка – это вероятность p1 стратегии A1, расстояние до левого конца – веро­ятность p2 стратегии A2.

Проведем через точки A1 и A2 два перпендикуляра к оси абсцисс: ось I-I и ось II-II. На оси I-I будем откладывать выигрыши при стратегии A1; на оси II-II – выигрыши при стратегии A2.

Если игрок A применяет стратегию A1, то его выигрыш при стратегии B1 игрока B равен a11, а при стратегии B2 он равен a12. Числам a11 и a12 на оси I соответствуют точки B1 и B2.

Если игрок A применяет стратегию A2, то его выигрыш при стратегии B1 игрока B равен a21, а при стратегии B2 он равен a22. Числам a21 и a22 соответствуют точки B1 и B2 на оси II.

Соединяем между собой точки B1 (I) и B1 (II) ; B2 (I) и B2 (II). Получили две прямые. Прямая B1B1– если игрок А применяет смешанную стратегию (любое сочетание стратегий A1 и A2 с вероятностями p1 и p2) и игрок В стратегию B1. Выигрышу игрока А соответствует некоторая точка, лежащая на этой прямой. Средний выигрыш, соответствующий смешанной стратегии, определяется по формуле a11p1+a21p2 и изобразится точкой M1 на прямой B1B1.

Аналогично строим отрезок B2B2, соответствующий примене­нию вторым игроком стратегии B2. При этом средний выигрыш определяется по формуле a12p1+a22p2 и изобразится точкой M2 на прямой B2B2.

Нам нужно найти оптимальную стратегию S*a, т. е. такую, для которой минимальный выигрыш (при любом по­ведении В) обращался бы в максимум. Для этого построим нижнюю границу выигрыша при стратегиях B1B2, т. е. ломаную B1NB2 отмеченную на рис. жирной линией. Эта нижняя граница будет выражать минимальный выигрыш игрока А при любых его смешанных стратегиях; точка N , в которой этот минимальный выигрыш достигает максимума, и определяет решение (оптимальную стратегию) и цену игры. Ордината точки N есть цена игры v . Координаты точки N находим как координаты точек пересечения прямых B1B1 и B2B2. В нашем случае решение игры определялось точкой пересечения стратегий. Однако это не всегда будет так.

Геометрически можно оп­ределять оптимальную стратегию как игрока А, так и игрока В; в обоих случаях используется принцип минимакса, но во втором случае строится не нижняя, а верхняя граница выигрыша и на ней определяется не максимум, а минимум.

Если платежная мат­рица содержит отрицательные числа, то для графического реше­ния задачи лучше перейти к новой матрице с неотрицательными элементами; для этого к элементам исходной матрицы достаточно добавить соответствующее положительное число. Решение игры при этом не изменится, а цена игры увеличится на это число. Графический метод можно применять при решении игры 2×n, m×2.

24. Приведение матричной игры к задаче линейного программирования

Игра m×n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших т и n , однако принципиальных трудностей не имеет, посколь­ку может быть сведено к решению задачи линейного программи­рования. Покажем это.

Пусть игра m×n задана платежной мат­рицей . Игрок А обладает стра­тегиями A1,A2,..Ai,..Am, игрок В – стратегиями B 1,B 2,..B i,..B n. Необ­ходимо определить оптимальные стратегии и, где – вероятности применения соот­ветствующих чистых стратегий Ai,Bj,

Оптимальная стратегия удовлетворяет следующему требо­ванию. Она обеспечивает игроку А средний выигрыш, не мень­ший, чем цена игры v , при любой стратегии игрока В и выиг­рыш, равный цене игры v , при оптимальной стратегии игрока В. Без ограничения общности полагаем v > 0; этого можно добиться, сделав все элементы . Если игрок А применяет смешанную стратегию против любой чистой стратегии Bj игрока В, то он получает средний выигрыш , или математическое ожидание выигрыша (т.е. элементы j -г o столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A1,A2,..Ai,..Am и резуль­таты складываются).

Для оптимальной стратегии все средние выигрыши не меньше цены игры v , поэтому получаем систему неравенств:

Каждое из неравенств можно разделить на число. Введем новые переменные: . Тогда система принимает вид

Цель игрока А – максимизировать свой гарантированный вы­игрыш, т.е. цену игры v.

Разделив на равенство, получаем, что переменные удовлетворяют условию: . Максимизация цены игры v эквивалентна мини­мизации величины , поэтому задача может быть сформулиро­вана следующим образом: определить значения переменных , ma к, чтобы они удовлетворяли линейным ограничени­ям (*) и при этом линейная функция (2*) обращалась в минимум.

Это задача линейного программирования. Решая задачу (1*)–(2*), получаем оптимальное решение и оптимальную стратегию .

Для определения оптимальной стратегии следует учесть, что игрок В стремится минимизировать гаранти­рованный выигрыш, т.е. найти max . Переменные удовлетворяют неравенствам

которые следуют из того, что средний проигрыш игрока В не пре­восходит цены игры, какую бы чистую стратегию не применял игрок А .

Если обозначить (4*) , то получим систему неравенств:

Переменные удовлетворяют условию.

Игра свелась к следующей задаче.

Определить значения переменных , которые удовлетворяют системе неравенств (5*) и максимизируют линей­ную функцию

Решение задачи линейного программирования (5*), (6*) определяет оптимальную стратегию. При этом цена игры. (7*)

Составив расширенные матрицы для задач (1*), (2*) и (5*), (6*), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (1*), (2*) и (5*), (6*), являются взаимно-двойственными. Очевид­но, при определении оптимальных стратегий в конкретных зада­чах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с по­мощью теорем двойственности.

При решении произвольной конечной игры размера m×n ре­комендуется придерживаться следующей схемы:

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими страте­гиями для игрока А

1. Предмет и задачи исследования операций в экономике. Основные понятия теории исследования операций.

Предмет исследования операций - системы организационного управления или организации, которые состоят из большого числа взаимодействующих между собой подразделений не всегда согласующихся между собой и могут быть противоположны.

Цель исследования операций - количественное обоснование принимаемых решений по управлению организациями

Решение, которое оказывается наиболее выгодным для всей организации называется оптимальным, а решение наиболее выгодное одному или нескольким подразделениям будет субоптимальным.

Исследование операций - наука, занимающаяся разработкой и практическим применением методов наиболее оптимального управления организационными системами.

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

Цель исследования операций - предварительное количественное обоснование оптимальных решений.

Всякий определенный выбор зависящих от нас параметров называется решением. Оптимальным называются решения, по тем или другим признакам предпочтительные перед другими.

Параметры, совокупность которых образует решение, называются элементами решения.

Множеством допустимых решений называются заданные условия, которые фиксированы и не могут быть нарушены.

Показатель эффективности - количественная мера, позволяющая сравнивать разные решения по эффективности.

2. Понятие о сетевом планировании и управлении. Сетевая модель процесса и ее элементы.

Метод работы с сетевыми графиками - сетевое планирование - базируется на теории графов. В переводе с греческого граф (grafpho - пишу) представляет систему точек, некоторые из них соединены линиями - дугами (или ребрами). Это топологическая (математическая) модель взаимодействующих систем. С помощью графов можно решать не только задачи сетевого планирования, но и другие задачи. Метод сетевого планирования применяется при планировании проведения комплекса взаимосвязанных работ. Он позволяет наглядно представить организационно-технологическую последовательность выполнения работ и установить взаимосвязь между ними. Кроме этого, он позволяет обеспечить координацию операций различной степени сложности и выявить операции, от которых зависит продолжительность всей работы (т.е. организационного мероприятия), а также сосредоточить внимание на своевременном выполнении каждой операции.

Основой сетевого планирования и управления является сетевая модель (СМ), в которой моделируется совокупность взаимосвязанных работ и событий, отображающих процесс достижения определенной цели. Она может быть представлена в виде графика или таблицы.

Основные понятия сетевой модели:

Событие, работа, путь.

Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени.

Путь — это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины.

Продолжительность пути определяется суммой продолжительностей составляющих его работ.

3. Построение и упорядочивание сетевого графика.

В качестве модели, отражающей технологические и организационные взаимосвязи процесса производства строительно-монтажных работ в системах сетевого планирования и управления (СПУ), используется сетевая модель.

Сетевой моделью называется графическое изображение процессов, выполнение которых приводит к достижению одной или нескольких поставленных целей, с указанием установленных взаимосвязей между этими процессами. Сетевой график представляет собой сетевую модель с расчетными временными параметрами.

Структура сетевого графика, определяющая взаимную зависимость работ и событий, называется его топологией.

Работа - это производственный процесс, требующий затрат времени, труда и материальных ресурсов, который при его выполнении приводит к достижению определенных результатов.

Зависимость (фиктивная работа), не требующая затрат времени изображается пунктирной стрелкой. Фиктивная работа используется в сетевом графике для отражения связей между событиями и работами.

В сетевом графике применяются временные, стоимостные и другие характеристики работ.

Продолжительной работы - время выполнения данной работы в рабочих днях или других единицах времени, одинаковых для всех работ сетевого графика. Продолжительность работ может быть как определенной (детерминированной), так и случайной величиной, задаваемой законом ее распределения.

Стоимость работы - это прямые затраты, необходимые для ее выполнения, зависящие от длительности и условий выполнения этой работы.

Ресурсы характеризуются потребностью в физических единицах, необходимых для выполнения данной работы.

Качество, надежность и другие показатели работ служат дополнительными характеристиками работ.

Событие - это факт окончания одной или нескольких работ, необходимый и достаточный для начала одной или нескольких последующих работ. Каждому событию присваивается номер, называемый кодом. Каждая работа определяется двумя событиями: кодом начального события, обозначаемого i и кодом конечного события, обозначаемого буквой j.

События, не имеющие предшествующих работ, называются начальными; события, не имеющие последующих - конечными.

1 Направление построения сети может иметь различный характер. Сетевой график может строиться от начального события к завершающему и от завершающего к исходному (начальному), а также от любого из событий к исходному или конечному.

2 При построении сети решаются вопросы:

Какие работы (работу) необходимо выполнить, чтобы начать данную работу;

Какие работы целесообразно выполнять параллельно с данной работой;

3 Первоначальный сетевой график строится без учета продолжительности работ, составляющих сеть.

4 Форма графика должна быть простой и зрительно легко воспринимаемой.

5 Между двумя событиями может заключаться только одна работа. При строительстве зданий и сооружений работы могут выполняться последовательно, параллельно или одновременно, часть последовательно, а часть параллельно, в результате чего между отдельными работами складываются различные зависимости.

Нумерация (кодирование) событий производится после окончания построения сети, начиная от исходного события до конечного.

4. Критический путь сетевого графика. Резервы времени. Ранние и поздние сроки событий и работ в сетевом графике.

В сетевом графике между начальным и конечным событиями может быть несколько путей. Путь, имеющий наибольшую продолжительность, называется критическим. Критический путь определяет общую продолжительность работ. Все остальные пути имеют меньшую продолжительность, и поэтому в них выполняемое работы имеют резервы времени.

Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).

Особое значение при составлении сетевого графика имеют два понятия:

Раннее начало работы - срок, раньше которого нельзя начать данную работу, не нарушив принятой технологической последовательности. Он определяется наиболее долгим путем от исходного события до начала данной работы

Позднее окончание работы - самый поздний срок окончания работы, при котором не увеличивается общая продолжительность работ. Он определяется самым коротким путем от данного события до завершения всех работ.

Раннее окончание - срок, раньше которого нельзя закончить данную работу. Он равен раннему началу плюс продолжительность данной работы

Позднее начало - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен позднему окончанию минус продолжительность данной работы.

Если событие является окончанием лишь одной работы (т.е. в него направлена только одна стрелка), то раннее окончание этой работы совпадает с ранним началом последующей.

Общий (полный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не увеличивая общую продолжительность работ. Он определяется разностью между поздним и ранним началом (или поздним и ранним окончанием - что то же самое).

Частный (свободный) резерв - это наибольшее время, на которое можно задержать выполнение данной работы, не меняя раннего начала последующей. Этот резерв возможен только тогда, когда в событие входят две или более работы (зависимости), т.е. на него направлены две или более стрелки (сплошные или пунктирные). Тогда лишь у одной из этих работ раннее окончание будет совпадать с ранним началом последующей работы, для остальных же это будут разные значения. Эта разница у каждой работы и будет ее частным резервом.

5. Динамическое программирование. Принцип оптимальности и управления Беллмана.

Динамическое программирование - один из наиболее мощных методов оптимизации. С задачами принятия рациональных решений, выбора наилучших вариантов, оптимального управления имеют дело специалисты разного профиля. Среди методов оптимизации динамическое программирование занимает особое положение. Этот метод исключительно привлекателен благодаря простоте и ясности своего основного принципа - принципа оптимальности. Сфера приложения принципа оптимальности чрезвычайно широка, круг задач, к которым он может быть применен, до настоящего времени еще полностью не очерчен. Динамическое программирование с самого начала выступает как средство практического решения задач оптимизации.

Кроме принципа оптимальности, основного приема исследования, большую роль в аппарате динамического программирования играет идея погружения конкретной задачи оптимизации в семейство аналогичных задач. Третьей его особенностью, выделяющей его среди других методов оптимизации, является форма конечного результата. Применение принципа оптимальности и принципа погружения в многошаговых, дискретных процессах приводят к рекуррентно-функцио-нальным уравнениям относительно оптимального значения критерия качества. Полученные уравнения позволяют последовательно выписать оптимальные управления для исходной задачи. Выигрыш здесь состоит в том, что задача вычисления управления для всего процесса разбивается на ряд более простых задач вычисления управления для отдельных этапов процесса.

Главным недостатком метода является, говоря словами Беллмана, «проклятие размерности» - его сложность катастрофически возрастает с увеличением размерности задачи.

6. Задача о распределении средств между предприятиями.

Можно сказать, что процедурапостроения оптимального управления методом динамического программирования распадается на две стадии:предварительную и окончательную. На предварительной стадии для каждого шага определяется УОУ зависящее от состояния системы (достигнутого в результате предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния. На окончательной стадии определяется (безусловное) оптимальное управление для каждого шага. Предварительная (условная) оптимизация производится по шагам в обратном порядке: от последнего шага к первому; окончательная (безусловная) оптимизация — также по шагам, но в естественном порядке: от первого шага к последнему. Из двух стадий оптимизации несравненно более важной и трудоемкой является первая. После окончания первой стадии выполнение второй трудности не представляет: остается только "прочесть" рекомендации, уже заготовленные на первой стадии.

7. Постановка задачи линейного программирования.

Линейное программирование -- популярный инструмент решения экономических задач, которые характиризуются наличием одного критерия (например, максимизировать доход от производства продукции за счет оптимального выбора производственной программы, или, например, минимизировать транспортные расходы и пр.). Для экономических задач характерны ресурсные ограничения (материальные и / или финансовые). Они записываются в виде системы неравенств, иногда в виде равенств.

С точки зрения прогнозирования допустимых интервалов цен (или объемов продаж) в рамках обобщенного непараметрического метода, применение линейного программирования означает:

Критерием является MAX цена очередного продукта из интересуемой группы f.

Управляемыми переменными величинами являются цены всех продуктов из группы f.

Ограничениями в нашей задаче прогнозирования с использованием обобщенного непараметрического метода, являются:

a) система неравенств (ограничения рациональности поведения потребителя) (см. 4.2. Прогнозирование в рамках обобщенного непараметрического метода);

б) требование неотрицательности управляемых переменных (в нашей задаче прогнозирования мы потребуем, чтобы цены на продукты из группы f не опустились ниже 80% от значений цен в последней временной точке) ;

в) бюджетное ограничение в виде равенства - требование постоянства суммы затрат на покупку продуктов из группы f (с учетом 15% инфляции, например).

8. Графический метод решения задач линейного программирования.

Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного простран6тва, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.

Пусть задача линейного программирования задана в двумерном пространстве, т. е. ограничения содержат две переменные.

Найти минимальное значение функции

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) х1 0, х2 0

Допустим, что система (2.2) при условии (2.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.2) и (2.3), как отмечалось выше, определяет полуплоскость с граничными прямыми: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), х1=0, х2=0. Линейная функция (2.1) при фиксированных значениях Z является уравнением прямой линии: С1х1 + С2х2 = const. Построим многоугольник решений системы ограничений (2.2) и график линейной функции (2.1) при Z = 0 (рис. 2.1). Тогда поставленной задаче линейного прграммирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая С1х1 + С2х2 = const опорная и функция Z при этом достигает минимума.

Значения Z = С1х1 + С2х2 возрастают в направлении вектора N =(С1, С2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора Х. Из рис. 2.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А (х1, х2) находим, решая систему уравнений прямых АВ и АЕ.

Если многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.

Случай 1. Прямая С1х1 + С2х2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.2).

Случай 2. Прямая, пере-двигаясь, все же становится опорной относительно многоу-гольника решений (рис. 2.2, а - 2.2, в). Тогда в зави-симости от вида области ли-нейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.2, а), ограниченной снизу и неограниченной сверху (рис. 2.2, б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).

9. Симплекс- метод.

Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника условий. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

10. Постановка транспортной задачи. Методы определения опорных планов.

Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:

ai - объемы производства i -го поставщика, i = 1, …, m;

вj - спрос j-го потребителя, j= 1,…,n;

сij - стоимость перевозки одной единицы продукции из пункта Ai- i-го поставщика, в пункт Вj - j-го потребителя.

Для наглядности данные удобно представлять в виде таблицы, которую называют таблицей стоимостей перевозок.

Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными.

Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj. Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.

Это условие для решения закрытых и открытых транспортных задач (ЗТЗ).

Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:

Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же , то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):

Условие сбалансированности.

Это условие для решения закрытых транспортных задач (ЗТЗ).

11. Алгоритм решения транспортной задачи.

Применение алгоритма требует соблюдения ряда предпосылок:

1. Должна быть известна стоимость перевозки единицы продукта из каждого пункта производства в каждый пункт назначения.

2. Запас продуктов в каждом пункте производства должен быть известен.

3. Потребности в продуктах в каждом пункте потребления должны быть известны.

4. Общее предложение должно быть равно общему спросу.

Алгоритм решения транспортной задачи состоит из четырех этапов:

Этап I. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения ресурсов. Допустимым называется такое распределение ресурсов, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.

Этап 2. Проверка полученного распределения ресурсов на оптимальность

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

Данный итеративный процесс повторяется до тех пор, пока не будет получено оптимальное решение.

12. Модели управления запасами.

Несмотря на то, что любая модель управления запасами призвана отвечать на два основных вопроса (когда и сколько), имеется значительное число моделей, для построения которых используется разнообразный математический аппарат.

Такая ситуация объясняется различием исходных условий. Главным основанием для классификации моделей управления запасами является характер спроса на хранимую продукцию (напомним, что с точки зрения более общей градации сейчас мы рассматриваем лишь случаи с независимым спросом).

Итак, в зависимости от характера спроса модели управления запасами могут быть

детерминированными;

вероятностными.

В свою очередь детерминированный спрос может быть статическим, когда интенсивность потребления не изменяется во времени, или динамическим, когда достоверный спрос с течением времени может изменяться.

Вероятностный спрос может быть стационарным, когда плотность вероятности спроса не изменяется во времени, и нестационарным, где функция плотности вероятности меняется в зависимости от времени. Приведенную классификацию поясняет рисунок.

Наиболее простым является случай детерминированного статического спроса на продукцию. Однако такой вид потребления на практике встречается достаточно редко. Наиболее сложные модели - модели нестационарного типа.

Кроме характера спроса на продукцию при построении моделей управления запасами приходится учитывать множество других факторов, например:

сроки выполнения заказов. Продолжительность заготовительного периода может быть постоянной либо являться случайной величиной;

процесс пополнения запаса. Может быть мгновенным либо распределенным во времени;

наличие ограничений по оборотным средствам, складской площади т.п.

13. Системы массового обслуживания (СМО) и показатели их эффективности.

Системы массового обслуживания (СМО) представляют собой системы специального вида, реализующие многократное выполнение однотипных задач. Подобные системы играют важную роль во многих областях экономики, финансов, производства и быта. В качестве примеров СМО в финансово-экономической; сфере можно привести банки различных типов (коммерческие, инвестиционные, ипотечные, инновационные, сберегательные), страховые организации, государственные акционерные общества, компании, фирмы, ассоциации, кооперативы, налоговые инспекции, аудиторские службы, различные системы связи (в том числе телефонные станции), погрузочно-разгрузочные комплексы (порты, товарные станции), автозаправочные станции, различные предприятия и организации сферы обслуживания (магазины, справочные бюро, парикмахерские, билетные кассы, пункты по обмену валюты, ремонтные мастерские, больницы). Такие системы, как компьютерные сети, системы сбора, хранения и обработки информации, транспортные системы, автоматизированные производственные участки, поточные линии, различные военные системы, в частности системы противовоздушной или противоракетной обороны, также могут рассматриваться как своеобразные СМО

Каждая СМО включает в свою структуру некоторое число обслуживающих устройств, которые называют каналами (приборами, линиями) обслуживания. Роль каналов могут играть различные приборы, лица, выполняющие те или иные операции (кассиры, операторы, парикмахеры, продавцы), линии связи, автомашины, краны, ремонтные бригады, железнодорожные пути, бензоколонки и т.д.

Системы массового обслуживания могут быть одноканальными или многоканальными.

Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а случайные моменты времени. Обслуживание заявок, в этом случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многиx случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потоказаявок и времени их обслуживания приводит к неравномерной загруженности СМО: в иное время на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, а иногда при свободных каналах на входе СМО заявки не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными.

Показатели эффективности функционирования пары «СМО — потребитель», где под потребителем понимают всю совокупность заявок или некий их источник (например, средний доход, приносимый СМО в единицу времени, и т.п.). Эта группа показателей оказывается полезной в тех случаях, когда некоторый доход, получаемый от обслуживания заявок, и затраты на обслуживание измеряются в одних и тех же единицах. Эти показатели обычно носят вполне конкретный характер и определяются спецификой СМО, обслуживаемых заявок и дисциплиной обслуживания.

14. Уравнения динамики для вероятностных состояний (уравнения Колмогорова). Предельные вероятности состояний.

Формально дифференцируя уравнение Колмогорова—Чепмена по s при s = 0 получаем прямое уравнение Колмогорова:

Формально дифференцируя уравнение Колмогорова — Чепмена по t при t = 0 получаем обратное уравнение Колмогорова

Необходимо подчеркнуть, что для бесконечномерных пространств оператор уже не обязательно непрерывен, и может быть определен не всюду, например, быть дифференциальным оператором в пространстве распределений.

В том случае, если число состояний системы S является конечным и из каждого состояния представляется возможным перейти (за то или иное количество шагов) в каждое другое состояние, то предельные вероятности состояний существуют, а также не зависят от начального состояния системы.

На рис. показаны граф состояния и переходов, удовлетворяющие поставленному условию: из любого состояния система рано или поздно может перейти в любое другое состояние. Условие не будет выполняться при изменении направления стрелки 4—3 на графе рис, а на противоположное.

Допустим, что поставленное условие выполнено, и, следовательно, предельные вероятности существуют:

Предельные вероятности будут обозначаться теми же буквамичто и вероятности состояний, при этом под ними подразумеваются числа, а не переменные величины (функции времени).

Ясно, что предельные вероятности состояний должны давать в сумме единицу: Следовательно, в системе при устанавливается некоторый предельный стационарный режим: пусть система и меняет собственные состояния случайным образом, однако вероятность каждого из этих состояний не зависит от времени и каждое из них осуществляется с некоторой постоянной вероятностью, представляющей собой среднее относительное время пребывания системы в этом состоянии.

15. Процесс гибели и размножения.

Марковским процессом гибели и размножения с непрерывным временем назовем такой с.п., который может принимать только целые неотрицательные значения; изменения этого процесса могут происходить в любой момент времени t, при этом в любой момент времени он может либо увеличиваться на единицу, либо остаться неизменным.

Потоками размножения λi(t) будем называть пуассоновские потоки, ведущие к увеличению функции X(t). Соответственно μi(t) - потоки гибели, ведущие к уменьшению функции X(t).

Составим по графу уравнения Колмогорова:

Если поток с конечным числом состояний:

Система уравнений Колмогорова для процесса гибели и размножения с ограниченным числом состояний имеет вид:

Процессом чистого размножения называется такой процесс гибели и размножения, у которого интенсивности всех потоков гибели равны нулю.

Процессом чистой гибели называется такой процесс гибели и размножения, у которого интенсивности всех потоков размножения равны нулю.

16. Системы массового обслуживания с отказами .

Наиболее простой из рассматриваемых задач в рамках теории массового обслуживания является модель одноканальной СМО с отказами или потерями.

Следует отметить, что в данном случае количество каналов равно 1 (). Этот канал принимает пуассоновский поток заявок, интенсивность которого равняется . Время оказывает влияние на интенсивность:

Если заявка прибыла в канал, который в данный момент не является свободным, она получает отказ и больше не числится в системе. Обслуживание заявок осуществляется в течение случайного времени , распределение которого реализуется в соответствии с показательным законом с параметром :

17. Системы массового обслуживания с ожиданием .

Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Система с ограниченной длиной очереди. Предположим сначала, что количество мест в очереди ограничено числом m, т. е. если заявка пришла в момент, когда в очереди уже стоят m заявок, она покидает систему необслуженной. В дальнейшем, устремив m к бесконечности, мы получим характеристики одноканальной СМО без ограничений длины очереди.

Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):

—канал свободен;

—канал занят, очереди нет;

— канал занят, одна заявка стоит в очереди;

—канал занят, k - 1 заявок стоят в очереди;

— канал занят, т заявок стоят в очереди.

18. Методы принятия решений в условиях конфликта. Матричные игры. Чистые и смешанные стратегии игр.

Матричная игра - это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец - номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.

Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 - свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 - свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij

Каждая стратегия игрока i=; j = часто называется чистой стратегией.

Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x- это набор чисел x = (x1,..., xm) удовлетворяющих соотношениям

xi³ 0 (i= 1,m), =1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y- это набор чисел

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Так как каждый раз применение игроком одной чистой стратегии исключает применение другой, то чистые стратегии являются несовместными событиями. Кроме того, они являются единственными возможными событиями.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

19. Геометрический метод решения матричной игры.

Решение игр размера 2xn или nx2 допускает наглядную геометрическую интерпретацию. Такие игры можно решать графически.

На плоскости XY по оси абсцисс отложим единичный отрезок A1A2 (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u1, u2). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка - это вероятность u1 выбора стратегии A1, расстояние до левого конца - вероятность u2 выбора стратегии A2. Точка А1 соответствует чистой стратегии А1, точка А2 - чистой стратегии А2.

В точках А1 и А2 восстановим перпендикуляры и будем откладывать на них выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем выигрыш игрока А при использовании стратегии А1, на втором - при использовании стратегии A2. Если игрок А применяет стратегию A1, то его выигрыш при стратегии B1 игрока B равен 2, а при стратегии B2 он равен 5. Числам 2 и 5 на оси OY соответствуют точки B1 и B2. Аналогично на втором перпендикуляре найдем точки B"1 и B"2 (выигрыши 6 и 4).

Соединяя между собой точки B1 и B"1, B2 и B"2, получим две прямые, расстояние от которых до оси OX определяет средний выигрыш при любом сочетании соответствующих стратегий.

Например, расстояние от любой точки отрезка B1B"1 до оси OX определяет средний выигрыш игрока A при любом сочетании стратегий A1 и A2 (с вероятностями u1 и u2) и стратегии B1 игрока B.

Ординаты точек, принадлежащих ломаной B1MB"2 определяют минимальный выигрыш игрока A при использовании им любых смешанных стратегий. Эта минимальная величина является наибольшей в точке М, следовательно, этой точке соответствует оптимальная стратегия U* = (,), а ее ордината равна цене игры v.

Координаты точки M найдем, как координаты точки пересечения прямых B1B"1 и B2B"2.

Для этого необходимо знать уравнения прямых. Составить такие уравнения можно, используя формулу для уравнения прямой, проходящей через две точки:

Составим уравнения прямых для нашей задачи.

Прямая B1B"1: = или y = 4x + 2.

Прямая B2B"2: = или y = -x + 5.

Получим систему: y = 4x + 2,

Решим ее: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Таким образом, U = (2/5, 3/5), v = 22/5.

20. Биматричные игры.

Биматричная игра - это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец - стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице - выигрыш игрока 2.)

Для биматричных игр также разработана теория оптимального поведения игроков, однако решать такие игры сложнее, чем обычные матричные.

21. Статистические игры. Принципы и критерии принятия решений в условиях полной и частичной неопределенности.

В исследовании операций принято различать три типа неопределенностей:

неопределенность целей;

неопределенность наших знаний об окружающей обстановке и действующих в данном явлении факторах (неопределенность природы);

неопределенность действий активного или пассивного партнера или противника.

В приведенной выше классификации тип неопределенностей рассматривается с позиций того или иного элемента математической модели. Так, например, неопределенность целей отражается при постановке задачи на выборе либо отдельных критериев, либо всего вектора полезного эффекта.

С другой стороны, два другие типа неопределенностей влияют, в основном, на составление целевой функции уравнений ограничений и метода принятия решения. Конечно, приведенное выше утверждение является достаточно условным, как, впрочем, и любая классификация. Мы приводим его лишь с целью выделить еще некоторые особенности неопределенностей, которые надо иметь в виду в процессе принятия решений.

Дело в том, что кроме рассмотренной выше классификации неопределенностей надо учитывать их тип (или "род") с точки зрения отношения к случайности.

о этому признаку можно различать стохастическую (вероятностную) неопределенность, когда неизвестные факторы статистически устойчивы и поэтому представляют собой обычные объекты теории вероятностей - случайные величины (или случайные функции, события и т.д.). При этом должны быть известны или определены при постановке задачи все необходимые статистический характеристики (законы распределения и их параметры).

Примером таких задач могут быть, в частности, система технического обслуживания и ремонта любого вида техники, система организации рубок ухода и т.д.

Другим крайним случаем может быть неопределенность нестохастического вида (по выражению Е.С.Вентцель - "дурная неопределенность"), при которой никаких предположений о стохастической устойчивости не существует. Наконец, можно говорить о промежуточном типе неопределенности, когда решение принимается на основании каких-либо гипотез о законах распределения случайных величин. При этом ЛПР должен иметь в виду опасность несовпадения его результатов с реальными условиями. Эта опасность несовпадения формализуется с помощью коэффициентов риска.

Принятие решений в условиях риска может быть основано на одном из следующих критериев:

критерий ожидаемого значения;

комбинации ожидаемого значения и дисперсии;

известного предельного уровня;

наиболее вероятного события в будущем.

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению определенной цели. Операция есть всегда управляемое мероприятие, т.е. имеется возможность распорядиться способом выбора некоторых параметров, характеризующих ее организацию. Эти параметры называют управляющими переменными .

Всякий определенный выбор таких переменных называется решением. Решения могут быть удачными и неудачными, разумными и неразумными. Оптимальными называют такие решения, которые по некоторым критериям предпочтительнее других.

Цель исследования операций – предварительное количественное обоснование оптимальных решений, которых может быть более одного. Окончательный выбор решения выходит за рамки исследования операций и производится средствами так называемой теории принятия решений.

Любая задача исследования операций имеет начальные «дисциплинирующие» условия, т.е. такие исходные данные, которые фиксированы с самого начала и не могут быть нарушены. В своей совокупности они формируют так называемое множество возможных решений.

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь количественный критерий, называемый показателем эффективности (или целевой функцией). Этот показатель выбирается так, чтобы отражать целевую направленность операции.

Часто выполнение операции сопровождается действием случайных факторов. Тогда в качестве показателя эффективности берется не сама величина, которую хотелось бы оптимизировать, а ее среднее значение (или математическое ожидание).

Иногда операция, сопровождаемая случайными факторами, преследует такую цель А , которая может быть либо достигнута полностью, либо не достигнута совсем (типа «да – нет»). Тогда в качестве показателя эффективности выбирают вероятность достижения этой цели p (A ). (Если p (A ) = 0 или 1, то приходим к известной в кибернетике задаче «черного ящика».)

Неправильный выбор показателя эффективности очень опасен. Операции, организованные под углом зрения неудачно выбранного критерия, могут привести к неоправданным затратам и потерям. (Например, «вал» в качестве основного критерия оценки хозяйственной деятельности предприятия.)

1.3. Общая постановка задачи исследования операций

Задачи исследования операций делятся на две категории: а) прямые и б) обратные.

Прямые задачи отвечают на вопрос: чему будет равен показатель эффективности Z , если в заданных условиях y  Y будет принято некоторое решение x  X . Для решения такой задачи строится математическая модель, позволяющая выразить показатель эффективности через заданные условия и решение, а именно:

где
заданные факторы (исходные данные),

управляющие переменные (решение),

Z – показатель эффективности (целевая функция),

F – функциональная зависимость между переменными.

Эта зависимость в разных моделях выражается по-разному. Зависимость между иобычно выражается в виде ограничений на

Если вид зависимости F известен, то показатель Z находится прямой подстановкой ив данный функционал.

Обратные задачи отвечают на вопрос: как при данных условиях выбрать решение
чтобы показатель эффективностиZ обратился в максимум (минимум). Такую задачу называют задачей оптимизации решения.

Пусть прямая задача решена, т.е. модель операции задана и вид зависимости F известен. Тогда обратная задача (т.е. задача оптимизации) может быть сформулирована следующим образом.

Требуется найти такое решение
при котором показатель эффективностиZ = opt :

Эта формула читается так: Z есть оптимальное значение
взятое по всем решениям, входящим в множество возможных решенийX .

Метод поиска экстремума показателя эффективности Z и связанного с ним оптимального решения должен всегда выбираться, исходя из особенностей функцииF и вида ограничений, накладываемых на решение. (Например, классическая задача линейного программирования.)

Задача исследования операций

Введение……………………………………………………………………...3

1. Основные понятия и определения исследования операций……..……..5

2. Общая постановка задачи исследования операций…………..…………6

Заключение……………………………………………………………….....13

Литература………………………………………………………………......14

Введение

Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.

Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций - количественное обоснование принимаемых решений по организации управления.

При решении конкретной задачи управления применение методов исследования операций предполагает:

Построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;

Изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия.

Примерами задач исследования операций, отражающих его специфику, могут служить следующие задачи.

Задача 1. Для обеспечения высокого качества выпускаемых изделий на заводе организуется система выборочного контроля. Требуется выбрать такие формы его организации - например, назначить размеры контрольных партий, указать последовательность контрольных операций, определить правила отбраковки, - чтобы обеспечить необходимое качество при минимальных расходах.

Задача 2. Для реализации определенной партии сезонных товаров создается сеть временных торговых точек. Требуется выбрать параметры сети - число точек, их размещение, количество персонала - так, чтобы обеспечить максимальную экономическую эффективность распродажи.

Задача 3. К заданному сроку необходимо провести массовое медицинское обследование группы населения с целью выявления определенных заболеваний. На обследование выделены материальные средства, оборудование, персонал. Требуется разработать такой план обследования - установить число медпунктов, их размещение, вид и количество анализов, чтобы выявить как можно больший процент из числа заболевших.

Необходимо отметить также задачи об использовании ресурсов, о смесях, об использовании мощностей, о раскрое материалов, транспортную задачу и др., в которых требуется найти решение, когда некоторый критерий эффективности (например, прибыль, выручка, затраты ресурсов и т.п.) принимает максимальное или минимальное значение.

Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель. В задаче 1 - это организация выборочного контроля с целью обеспечить качество выпускаемой продукции; в задаче 2 - организация временных торговых точек с целью проведения сезонной распродажи; в задаче 3 - массовое медицинское обследование с целью определения процента заболевших.

В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение - такое, чтобы мероприятие принесло определенную выгоду. Условиями проведения операции в каждой задаче оказываются средства, которыми мы располагаем, время, оборудование, технологии, а решение в задаче 1 заключается в выборе формы контроля - размера контрольных партий, правил отбраковки; в задаче 2 - в выборе числа точек размещения, количества персонала; в задаче 3 - в выборе числа медпунктов, вида и количества анализов.

1. Основные понятия и определения исследования операций

Операция - любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе - от выбора некоторых параметров.

Всякий определенный выбор параметров называется решением.

Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.

Замечание 1.Следует обратить внимание на постановку проблемы: само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных.

Замечание2. Если в одних задачах исследования операций оптимальным является решение, при котором некоторый критерий эффективности принимает

максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче 2 оптимальным можно считать такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек.

Для применения количественных методов исследования требуется построить математическую модель операции. При построении модели операция, как правило, упрощается, схематизируется, и схема операции описывается с помощью того или иного математического аппарата.

Модель операции - это достаточно точное описание операции с помощью математического аппарата (различного рода функций, уравнений, систем уравнений и неравенств и т.п.). Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата.

Эффективность операции - степень ее приспособленности к выполнению задачи - количественно выражается в виде критерия эффективности - целевой функции. Например, в задаче об использовании ресурсов критерий эффективности - прибыль от реализации произведенной продукции, которую нужно максимизировать, в транспортной задаче - суммарные затраты на перевозку грузов от поставщиков к потребителям, которые нужно минимизировать. Выбор критерия эффективности определяет практическую ценность исследования. (Неправильно выбранный критерий может принести вред, ибо операции, организованные под углом зрения такого критерия эффективности, приводят порой к неоправданным затратам.)

2. Общая постановка задачи исследования операций

Важно усвоить методологию построения моделей задач исследования операций. Все факторы, входящие в описание операции, можно разделить на две группы:

постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через α1, α2, ... ;

зависимые факторы (элементы решения) x 1, х2, ...; которые в известных пределах мы можем выбирать по своему усмотрению.

Например, в задаче об использовании ресурсов к постоянным факторам следует отнести запасы ресурсов каждого вида, производственную матрицу, элементы которой определяют расход сырья каждого вида на единицу выпускаемой продукции каждого вида. Элементы решения - план выпуска продукции каждого вида.

Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде

Z = f (x1, х2, ..., α1, α2, ...)

Все модели исследования операций могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов.

Следует отметить, прежде всего, большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизироватьпланирование и управление сложными системами, в первую очередьэкономическими системами. Оптимизационную задачу можносформулировать в общем виде: найти переменные х1, х2, ..., х n , удовлетворяющие системе неравенств (уравнений)

g i (х1, х2, х3,..., х n )<= b i , i = 1, 2,..., n (0.1)

и обращающие в максимум (или минимум) целевую функцию, т.е.

Z = f (x1, х2, ..., x n ) - m ах (m in ) (0.2)

(Условия неотрицательности переменных, если они есть, входят в ограничения (0.1))

Рассмотрим еще одну, характерную для исследования операций задачу - классическую задачу потребления, имеющую большое значение в экономическом анализе.

Пусть имеется п видов товаров и услуг, количества которых (в натуральных единицах) x1, х2, ..., x n ,по ценам соответственно p 1, p 2, ..., p n за единицу. Суммарная стоимость этих товаров и услуг составляет ∑ p i x i .

Уровень потребления Z может быть выражен некоторой функцией Z = f (x1, х2, ..., x n ) ,называемой функцией полезности. Необходимо найти такой набор товаров и услуг x1, х2, ..., x n при данной величине доходов I, чтобы обеспечить максимальный уровень потребления, т.е.

Z = f (x1, х2, ..., x n ) - m ах (0.3)

при условии

∑ p i x i <= I (0.4)

x i >= 0 ( i = 1, 2,..., n ) (0.5)

Решения этой задачи, зависящие от цен p 1, p 2, ..., p n и величины дохода I , называются функциями спроса.

Очевидно, что рассмотренная задача потребления (0.3)-(0.5), так же как и многие другие, является частным случаем сформулированной выше общей задачи (0.1)-(0.2) на определение экстремума функции п переменных при некоторых ограничениях, т.е. задачей на условный экстремум.

В тех случаях, когда функции f и g i , в задаче (0.1)-(0.2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако применение этих методов в исследовании операций весьма ограниченно, так как задача определения условного экстремума функции я переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким - тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция Z задана таблично. В этих случаях для решения задачи (0.1)-(0.2) применяются методы математического программирования.

Если критерий эффективности Z = f (x1, х2, ..., x n ) (0.2) представляет линейную функцию, а функции g i (х1, х2, х3,..., х n ) в системе ограничений (0.1) также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.

Если в задаче математического программирования имеется переменная времени и критерий эффективности (0.2) выражается не в явном виде как функция переменных, а косвенно - через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.

Если критерий эффективности (0.2) и система ограничений (0.1) задаются функциями вида с*( x 1^α 1 )*( x 2^α 2 )...( x n ^α n ) , то имеем задачу геометрического программирования. Если функции f и (или) g i в выражениях (0.2) и (0.1) зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, - задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее, удовлетворительное с точки зрения практики, решение.

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.

Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.

Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п.

Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.

Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.

Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.

Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.

Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.

Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов.

Среди моделей исследования операций особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) сторон, преследующих разные цели, можно отнести ряд ситуаций в области экономики, права, военного дела и т. п. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.

На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям, один из которых следует максимизировать, другие - минимизировать. Математический аппарат может принести пользу и в случаях многокритериальных задач исследования операции, по крайней мере, помочь отбросить заведомо неудачные варианты решений.

Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, прибыль и расход), выбрать целевую функцию, необходимо установить приоритет критериев. Обозначим f 1 (x), f 2 (x), ..., f n (x) (здесь х - условный аргумент). Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта:

В качестве целевой функции выбирается критерий f 1 (x), обладающий наиболее высоким приоритетом;

Рассматривается комбинация

f ( x ) = ω 1 * f 1 ( x ) + ω 2 * f 2 ( x ) + …+ ω n * f n ( x ) , (0.6)

где ω 1 , ω 2 , … ω n - некоторые коэффициенты (веса).

Величина f (х) , учитывающая в определенной степени все критерии, выбирается в качестве целевой функции.

В условиях определенности ω i - числа, f i (x) - функции. В условиях неопределенности f i (x) могут оказаться случайными и вместо f i (x) в качестве целевой функции следует рассматривать математическое ожидание суммы (0.6).

Попытка сведения многокритериальной задачи к задаче с одним критерием эффективности (целевой функцией) в большинстве случаев не дает удовлетворительных результатов. Другой подход состоит в отбрасывании ("выбраковке") из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются так называемые эффективные (или "паретовские") решения, множество которых обычно существенно меньше исходного. А окончательный выбор "компромиссного" решения (не оптимального по всем критериям, которого, как правило, не существует, а приемлемого по этим критериям) остается за человеком - лицом, принимающим решение.

Заключение

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В. Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие. Особо следует отметить роль академика Л.В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, о раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л.В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики - линейному программированию.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.

Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы - детерминированными, динамические процессы - статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т. Саати, как "искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами".

Литература

1. Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Исследование операций в экономике: Учебное пособие для вузов - М.: ЮНИТИ, 2002.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология - М.: Наука, 1980.

3. Горелик В.А., Ушаков И.А. Исследование операций. - М.: Машиностроение, 1986.

И.Н. Слинкина

Учебное пособие для студентов педагогических вузов

по специальности «Информатика»

Шадринск, 2003

Слинкина И.Н.

Исследование операций. Учебно-методическое пособие. – Шадринск: изд-во Шадринского государственного педагогического института, 2002. - 106 с.

Слинкина И.Н. – кандидат педагогических наук

В учебном пособии представлена теоретическая часть курса «Исследование операций». Оно предназначено для студентов очного и заочного отделений факультетов, реализующих специальность «Информатика».

© Шадринский государственный педагогический институт

© Слинкина И.Н., 2002

Вопросы к блокам по курсу «Исследование операций» 5

1.1. Предмет и задачи исследования операций 7

1.2. Основные понятия и принципы исследования операций 8

1.3. Математические модели операций 10

1.4. Понятие линейного программирования 12

1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов 13

1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий 15

1.7. Примеры экономических задач линейного программирования. Задача о смесях 16

1.8. Примеры экономических задач линейного программирования. Транспортная задача 17

1.9. Основные виды записи задач линейного программирования 19

1.10. Способы преобразования 21

1.11. Переход к канонической форме 22

1.12. Переход к симметричной форме записи 25

2.1. Геометрическая интерпретация задачи линейного программирования 28

2.2. Решение задач линейного программирования графическим методом 29

2.3. Свойства решений задачи линейного программирования 34

2.4. Общая идея симплексного метода 35

2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом 36

2.6. Признак оптимальности опорного плана. Симплексные таблицы 40

2.7. Переход к нехудшему опорному плану. 44

2.8. Симплексные преобразования 46

2.9. Альтернативный оптимум (признак бесконечности множества опорных планов) 51

2.10. Признак неограниченности целевой функции 52

2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание 53

2.12. Понятие двойственности для симметричных задач линейного программирования 54

3.1. Несимметричные двойственные задачи 57

3.2. Открытая и закрытая модели транспортной задачи 61

3.3. Построение начального опорного плана. Правило "Северо-западного угла" 63

3.4. Построение начального опорного плана. Правило минимального элемент 64

3.5. Построение начального опорного плана. Метод Фогеля 64

3.6. Метод потенциалов 65

3.7. Решение транспортных задач с ограничениями по пропускной способности 69

3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении 71

3.9. Сущность методов дискретной оптимизации 72

3.10. Задача выпуклого программирования 74

3.11. Метод множителей Лагранжа 75

3.12. Градиентные методы 77

4.1. Методы штрафных и барьерных функций 78

4.2. Динамическое программирование. Основные понятия. Сущность методов решения 79

4.3. Стохастическое программирование. Основные понятия 81

4.4. Матричные игры с нулевой суммой 83

4.5. Чистые и смешанные стратегии и их свойства 85

4.6. Свойства чистых и смешанных стратегий 88

4.7. Приведение матричной игры к ЗЛП 92

4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания 94

4.9. Потоки событий 96

4.10. Схема гибели и размножения 97

4.11. Формула Литтла 99

4.12. Простейшие системы массового обслуживания 101

Вопросы к блокам по курсу «Исследование операций»

Блок 1

1. Предмет и задачи исследования операций.

2. Основные понятия и принципы исследования операций.

3. Математические модели операций.

4. Понятие линейного программирования.

5. Примеры экономических задач линейного программирования. Задача

6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий.

7. Примеры экономических задач линейного программирования. Задача о смесях.

8. Примеры экономических задач линейного программирования. Транспортная задача.

9. Основные виды записи задач линейного программирования.

10. Способы преобразования.

11. Переход к канонической форме.

12. Переход к симметричной форме записи.

Блок 2

1. Геометрическая интерпретация задачи линейного программирования.

2. Решение задач линейного программирования графическим методом.

3. Свойства решений задачи линейного программирования.

4. Общая идея симплексного метода.

5. Построение начального опорного плана при решении задач линейного программирования симплексным методом.

6. Признак оптимальности опорного плана. Симплексные таблицы.

7. Переход к нехудшему опорному плану.

8. Симплексные преобразования.

9. Альтернативный оптимум (признак бесконечности множества опорных планов).

10. Признак неограниченности целевой функции.

11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.

12. Понятие двойственности для симметричных задач линейного программирования.

Блок 3

1. Несимметричные двойственные задачи.

2. Открытая и закрытая модели транспортной задачи.

3. Построение начального опорного плана. Правило "Северо-западного угла".

4. Построение начального опорного плана. Правило минимального элемент.

5. Построение начального опорного плана. Метод Фогеля.

6. Метод потенциалов.

7. Решение транспортных задач с ограничениями по пропускной способности.

8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении.

9. Сущность методов дискретной оптимизации.

10. Задача выпуклого программирования.

11. Метод множителей Лагранжа.

12. Градиентные методы.

Блок 4

1. Метод штрафных и барьерных функций.

2. Динамическое программирование. Основные понятия. Сущность методов решения.

3. Стохастическое программирование. Основные понятия.

4. Матричные игры с нулевой суммой.

5. Чистые и смешанные стратегии.

6. Свойства чистых и смешанных стратегий.

7. Приведение матричной игры к ЗЛП

8. Задачи теории массового обслуживания. Классификация систем массового обслуживания.

9. Потоки событий.

10. Схема гибели и размножения.

11. Формула Литтла.

12. Простейшие системы массового обслуживания.

Блок 1.

Предмет и задачи исследования операций

Современное состояние науки и техники, в частности, развитие компьютерных средств расчета и математического обоснования теорий позволило значительно упростить решение многих проблем, поставленных перед различными отраслями науки. Многие из проблем сводятся к решению вопроса об оптимизации производства, оптимальному управлению процессами.

Потребности практики вызвали к жизни специальные научные методы, которые удобно объединять под названием «исследование операций».

Определение: Под исследованием операций будем понимать применение математических, количественных методов для обоснование решений во всех областях целенаправленной человеческой деятельности.

Пусть предпринимается какое-то мероприятие, направленное к достижению определенной цели. У лица (или группы лиц), организующего мероприятие, всегда имеется какая-то свобода выбора: оно может быть организовано тем или иным способом. Решение и есть какой-то выбор из ряда возможностей, имеющихся у организатора.

Необходимость принятия решений и проверки выдвинутой гипотезы решения математически подтверждают следующие примеры:

Задача 1. О наилучшем использовании ресурсов.

На предприятии выпускается несколько видов продукции. Для их изготовления используются некоторые ресурсы (в том числе человеческие, энергетические и т.д.). Необходимо рассчитать, каким образом спланировать работу предприятия, чтобы затраты ресурсов были минимальны, а прибыль – максимальной.

Задача 2. О смесях.

Необходимо подготовить смесь, обладающую определенными свойствами. Для этого можно использовать некоторые "продукты" (для расчета диет – продукты питания, для кормовых смесей – продукты питания для животных, для технических смесей – сплавы, жидкости технического назначения). задача заключается в выборе оптимального количества продуктов (по цене) для получения оптимального количества смеси.

Задача 3. Транспортная задача.

Существует сеть предприятий, выпускающих однотипную продукцию одного качества и сеть потребителей этой продукции. Потребители и поставщики связаны путями сообщений (автодороги, железнодорожные линии, авиационные линии). Определены тарифы перевозок. Необходимо рассчитать оптимальный план перевозок продукции, чтобы затраты при перевозке были минимальны, запросы всех потребителей удовлетворены, а у поставщиков весь товар вывезен.

В каждом из приведенных примеров речь идет о каком-то мероприятии, преследующем определенную цель. Заданы некоторые условия, характеризующие обстановку (в частности, средства, которыми можно распоряжаться). В рамках этих условий требуется принять такое решение, чтобы задуманное мероприятие было в некотором смысле более выгодным.

В соответствии с этими общими чертами вырабатываются и общие приемы решения подобных задач, в совокупности составляющие методологическую схему и аппарат исследования операций.

В настоящее время большое распространение принимают автоматизированные системы управления (АСУ), основанные на использовании компьютерной техники. Создание АСУ невозможно без предварительного обследования управляемого процесса методами математического моделирования. С ростом масштабов и сложности мероприятий математические методы обоснования решений приобретают все большую роль.

Основные понятия и принципы исследования операций

Определение: Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

Операция есть всегда управляемое мероприятие, т.е. от расчетов зависит, каким способом выбрать параметры, характеризующие ее организацию. «Организация» здесь понимается в широком смысле слова, включая набор технических средств, применяемых в операции.

Определение: Всякий определенный выбор зависящий от решающих параметров называется решением.

Определение: Оптимальными называются решения, по тем или иным причинам предпочтительные перед другими.

Цель исследования операций – предварительное количественное обоснование оптимальных решений.

Иногда в результате исследования удается указать одно-единственное строго определенное решение, гораздо чаще – выделить область практически равноценных оптимальных решений, в пределах которой может быть сделан конечный выбор.

Само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица, чаще – группы лиц, которым представляется право окончательного выбора и на которых возложена ответственность за этот выбор.

Определение: Параметры, совокупность которых образует решение, называются элементами решения.

В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т.д. Для упрощения всю совокупность элементов решения будем обозначать х.

Кроме элементов решения в любой задачи исследования операций имеются еще и заданные условия, которые фиксированы в условии задачи и нарушены быть не могут. В частности, к таким условиям относятся средства (материальные, технические, людские), которыми можно распоряжаться, и иные ограничения, налагаемые на решение. В своей совокупности они образуют так называемое «множество возможных решений». Обозначим это множество Х, а тот факт, что решение х принадлежит этому множеству, будем записывать: хÎХ.

Чтобы сравнивать между собой по эффективности разные решения, нужно иметь какой-то количественный критерий, так называемый показатель эффективности (целевая функция). Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Лучшим будет считаться то решение, которое в максимальной степени способствует достижению поставленной цели. Чтобы выбрать показатель эффективности Z, нужно прежде всего определить, к чему должно привести решение задачи. Выбирая решение, предпочтение отдается такому, которое обращает показатель эффективности Z в максимум или в минимум. Например, доход от операции хотелось бы обратить в максимум; если же показателем эффективности являются затраты, их желательно обратить в минимум.

Очень часто выполнение операции сопровождается действием случайных факторов: «капризов» природы, колебания спроса и предложения, отказы технических устройств и т.д. В таких случаях обычно в качестве показателя эффективности берется не сама величина, которую хотелось бы максимизировать (минимизировать), а среднее значение (математическое ожидание).

Задача выбора показателя эффективности решается для каждой проблемы индивидуально.

Задача 1. О наилучшем использовании ресурсов.

Задача операции – произвести максимальное количество товаров. Показатель эффективности Z – прибыль от продажи товаров при минимальных затратах на ресурсы (max Z).

Задача 2. О смесях.

Естественный показатель эффективности, подсказанный формулировкой задачи, - это цена необходимых для смеси продуктов при условии необходимости сохранения заданных свойств смеси(min Z).

Задача 3. Транспортная задача.

Задача операции – обеспечить снабжение товарами потребителей при минимальных расходах на перевозки. Показатель эффективности Z – суммарные расходы на перевозки товаров за единицу времени (min Z).