Исследование операций

Untitled

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. Метод обратной матрицы

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

F=c*x -> min

A*x=b

x>=0 (1)

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, и, следовательно, система приобретает такой вид:

< (2).>

Выразим <: >

<.>

Т.к. |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

Первоначальные

Дополнительные

<>

<>

Дополнительные

Первоначальные

Переменные исходной задачи II

Теорема. Положительным (ненулевым) компонентам оптимально­го решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых 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(b1,b2,…,bm) по соответствующим аргументам, т.е.

<>

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставщик

Потребитель

Запас груза

B1

…

Bn

A1

c11

x11

…

c1n

x1n

a1

…

…

…

…

…

Am

cm1

x1m

…

cmn

xmn

am

Потребность

в грузе

b1

…

bn

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

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

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

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

< (1).>

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

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

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

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

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

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

<(4).>

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, т. е. <. Если , то и первый столбец «закрыт», т. е. спрос первого потребителя удовлетворен полностью. Это означает, что для всех остальных клеток первого столбца количество груза для .>

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

Если <, то аналогично «закрывается» пер­вая строка, т. е. , для . Переходим к заполнению соседней клетки (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