Курс лекций по линейному программированию

Курс лекций по линейному программированию.
Лекция № 1: «Предмет курса. Оптимизационные задачи. Основы линейного программирования».
В связи с расширение приложения математики в решении экономических задач основное внимание уделяется решению задач, которые в рамках классической математики оказалось затруднительным и в первую очередь это касается экстремальных задач в экономических моделях в такого рода задачах экстремум достигается, как правило, в граничных тачках изменения параметра.

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

Требуется определить максимум и минимум функции f(x1, …, xn) при условиях:

g(x1, …, xn){≤, =, ≥} bii=/>

xj≥0 j=/>

— показатель качества решения (целевая функция)

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

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

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

Решить задачу – это найти её оптимальное решение, либо установить её неразрешимость.

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

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

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

Общей задачей ЛП является задача нахождения max />:

∑aijxj{} bi; i=/>j=/>

xj≥0 j=/>

где aij, bi, cj – заданные постоянные, при этом целевая функция называется линейной формой.

Условие 1 – ограничение задачи

Условие 2 – условие неотрицательности переменных.

Стандартной (симметричной) задачей ЛП называется задача, в которой опред. экстремум целевой функции при выполнении условия 1 только ву одну сторону и условия 2 для всех переменных.

Каноническая задача ЛП называется задача, в которой:

функция цели исследуется на максимум и минимум

ограничение задач только типа равенство

все переменные неотрицательны

все элементы правых частей положительны

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

План х* при котором целевая функция достигает максимума, называется оптимальным => решение состоит в нахождении хотя бы одного оптимального плана.

Различные формы записи задачи ЛП:

векторная форма

/>=(x1, …, xn)

/>=(x1, …, xn)

/>

/>

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

Z=Cx→max

A1x1+…+Anxn

матричная форма записи

/>

Где А – матрица условий; Сх – скалярное произведение векторов; Ах – умножение матрицы на вектор.
Элементы выпуклого анализа.

Линейная комбинация векторов называется выпуклой, если выполняется условие />

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

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

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

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

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

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

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

Теорема № 1:

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

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

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

Применительно к ЛП при переходе к канонической форме получается система уравнений, в которой переменных больше чем уравнений, при этом элемент столбца правых частей b, является линейными комбинациями векторов ???? и дополнительных векторов, которые получаются в результате данного преобразования, следовательно, в качестве базисных векторов выбирают только т. векторов (соответствующие им переменные называются базисными, а остальные переменные в силу условий неотрицательности полагаются равными 0, т.о. получаем опорное решение или опорный план.
Алгебраическая характеристика угловой точки.
Рассмотрим канонический вид задачи ЛП в векторной форме. Т.к. размерность векторов А1, …, Аk = m то в системе уравнений можно выбрать m базисных переменных, которые определяют некоторое решение данной системы.

Теорема № 2:

Если система векторов А1, …, Аk в каноническом разложении (*) линейно независима (k≤m) и такова, что А1х1, …, Аkхk=b, где все хj≥0 j=/>, то точка х=(b1,bk,0…0) является угловой точкой многогранника решений. Если точки х является угловой точкой многогранника решений, то система векторов А1, …, Аk в разложении (*) является линейно независимой, образующий базис.

Следствия:

т.к. вектора А1, …, Аkимеют размерность m, то угловая точка многогранника решений имеет не более, чем m положительных координат, а в силу неотрицательности переменных остальные = 0.

Для любой угловой точки в разложении (*) имеется не более чем m линейно независимых векторов.

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

Заключение:

опорный план соот. угловой точке и число опорных планов всегда конечно.

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

Оптимальный план находится среди опорных, следовательно, перебирая все опорные планы, количество которых конечно, всегда может быть найден оптимальный план.
Лекция № 2: « Симплексный метод».
Теорема № 1. Критерий оптимальности плана.

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

Критерий неразрешимости задачи на максимум:

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

Теорема о не единственности оптимального плана:

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

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

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

Прямая задача

Двойственная задача

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

Z=CX→max

AX≤B

X≥

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

F=BY→min

ATY≥c

Y≥0

Формально

Определить вектор Х, удовлетворяющий ограничениям и обеспечивающий максимальный целевой функции z.

X=(x1, … ,xn)

Anx1+…+a1nxn≤bn

…………

Amx1+…+amnxv≤bn

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

Yiобозначим стоимость единицы i-ого вида ресурсов, то стоимость ресурсов, затраченных на изготовление j-ого вида продукции = />и по т. должна быть ≥ стоимости изначального продукта.

/>, тогда двойственная задача и задаче планирования производства планируется следующим образом:

Определить вектор Y=(y1, … ,ym), удовлетворяющий ограничениям:

a11y1+ … + a1mym≥0

…………

an1yi+ … + anmym≥0

и обеспечивающий минимум целевой функции.

F=b1y1+…+bmym

Виды моделей двойственных задач:

— Симметричные данные выше

— Несимметричные:

Z=cx→min

AX=B

X≥0

V = YB→max

YAT≤C

Соответствие между прямой и двойственной задачами

Целевая функция исследуется по максимуму

Коэффициент целевой функции прямой задачи

Матрица ограничений

Столбец правых частей целевой задачи

/>

знаки соотношения правых и левых частей:

а.) неравенство (i-ое ограничение)

б.) равенство (i-ое ограничение)

6. Число ограничений

7. Переменные

а.) xj≥0

б.) на xjнет ограничений на знак

1. Целевая функция исследуется на минимум

2. Столбец свободных членов двойственной задачи

3. Транспонированная матрица

4. Коэффициент целевой функции

5. Переменные (ограничения)

а.) yi≥0

б.) на yiнет ограничений на знак

6. Количество переменных

7. ограничения

а.) j-ое ограничение неравенство

б.) j-ое ограничение равенство

Теорема № 1 двойственности

Для любой пары даойственных задач имеет место один из следующих задач:

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

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

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

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

Лемма: для любых планов X и Y прямой и двойственной задач соответственно (прямая на максимум; двойственная на минимум) имеет место z(x)≤F(x), где z – целевая функция прямой, а F – целевая функция двойственной.
Теорема № 2 двойственности

Пусть х*=(х*1, …, х*n) и y*=(y*1, …, y*m) – допустимые решения прямой и двойственной задач, соответственно. Для того чтобы x* и y* были оптимальными решениями необходимо и достаточно выполнение следующих условий:

1.) />

2.) />

Условия 1 и 2 позволяют, зная оптимальное решение одной из задач, найти решение другой. На основании второй теоремы двойственности, формулируется критерии оптимальности для допустимого решения задач.

Теорема:

Пусть х1* — допустимое решение прямой задачи, то вектор х* является оптимальным решением прямой задачи в том и только в том случае, когда среди решений уравнения 1 при xj*≠0 найдётся хотя бы одно допустимое решение двойственной задачи и yi*=0 при выполнении условия

/>

yi – это не цены, это оценка цен, т.к. если ресурс дефицитные (полностью используется в производстве) то оценка совпадает с ценой, а если ресурс не дефицитный, то оценка = 0.
Нахождение решения двойственной задачи по таблице оптимального решения прямой.
Пусть найдено оптимальное решение прямой задачи х*, которая определенна системой базисных векторов Аi, …, Aim через Сб обознач. вектор, состоящий из коэффициентов целевой функции при базисных переменных оптимального решения. Через Р-1 обозначают матрицу, обратную матрице Р, составленную из компонент векторов Аi, …, Aim оптимального базиса.
Теорема:

Если прямая задача имеет оптимальный план х*, то оптимальный план двойственной задачи y*=CБ.Р-1. Решение двойственной задачи находится в симплексной таблице оптимального решения прямой на пересечении индексной строки и векторов столбцов исходного базиса прямой.
Экономическая интерпретация.

Пусть имеются m видов ресурсов, количества b1, … ,bm. На основе этих ресурсов предполагают выпускать продукцию n различными способами, при этом за единицу времени применение j-ого способа расходуется аij единиц i-ого вида ресурсов, а выпускаемая, при этом, продукция имеет ценность ij. Как оценить имеющиеся ресурсы?

Пусть х=(х1, …, хn) – вектор, компоненты которого – времена использования j-ого способа производства, то xj≥0 ∑аijxj≤bi, если yi – оценка ресурсов, используемых в единицу времени при j-ом способе производства.

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

Z(x)≤F(Y)

Величина Δху=F(Y) – Z(X) характеризует потери в зависимости от плана х и выбранных ресурсных оценок у = > х и у надо выбирать так, чтобы величина потерь была наименьшей, а для этого достаточно план подобрать так, чтобы z(x) было как можно больше, а F(y) – как можно меньше. Отсюда возникает пара симметричных двойственных задач.

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

Из теоремы 2 двойственности следует, что если х*, у* — оптимальные решения прямой и двойственной задач соответственно, то справедливо соотношение:

/>

/>

Условие (*) интерпретируется: если оценка i-ого вида ресурса положительна в оптимальном плане, то ресурс используется полностью, если ресурс используется не полностью, то его оценка = 0.

Условие (**): если производство j-ого вида продукции включено в оптимальный план, то он в оптимальной оценке неубыточен. Если он убыточен (затратная оценка превосходит цену реализации) то этот продукт не производится в оптимальном плане.

∑aijyi – затратная оценка производства единицы j-ого вида продукции.
Лекция № 3: «Целочисленное программирование».

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

Задача о расписании (назначении).

Есть 3 самолета и 15 маршрутов. Известны затраты и прибыль от посылки каждого самолета на каждый маршрут. Требуется составить такое назначение направлений, что юы получить максимальную прибыль. Переменные – Гулиевы вектора (вектора, принимающие 0 или 1).

Задачи ЛП называются задачи целочисленного ЛП (ЦЛП), если на переменные задачи положено условие целочисленности.

А) полностью целочисленная задача

Б) частично целочисленная задача
Разница, проявляемая в методах решения.

Методы решения трудоемки и существенно зависят от размерности задачи.

методом сечения Гомори.

1-ый алгоритм Гомори, аддитивный.

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

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

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

Пусть а- действительное число. Число [a] – целая часть числа а – это наибольшее целое, не превосходящее данного числа.

qa — дробная часть числа – это разность между числом и его целой частью а-[a] 0≤qa
основой метода является понятие правильного отсечения. Пусть х* — оптимальный план ослабленной задачи, который не является целочисленным. Неравенство αх≤β называется правильным отсечением или отсечением Гомори, если оно удовлетворяет условиям:

условие отсечения. Если х* оптимальный не целочисленный план, то он не удовлетворяет этому ограничению αх*>β

условие правильности. Для любого целочисленного плана х* αх*≤β

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

Алгоритм:

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

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

Условие неразрешимости целочисленной задачи.

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

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

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

/>

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

хj* = [xj*] + qj0qj
aij = [aij] + qij 0≤qij
переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой.

xj– [xj] + ∑[qij]xj=qj+∑qijxj

т.к. переменные xm+1, …, xn, принимают целочисленные значения, то правая часть уравнения является целочисленной, следовательно, в силу не отрицательности дробных частей и переменных задачи, получаем:

qi+∑aijxj≥0, => qi-∑aijxj≤qj,

т.к. qjqj на 1 и получает неравенство qi-∑aijxj≤1

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

qi-∑qij
Вводя остаточною переменную Sj получим выражение для переменной Гомори Sj.

qj-∑qijxj+Sj=0,

где Sj – неотрицательная добавочная переменная, которая по определению должна принимать целое значение, но для данной системы ограничений =>, что если

xj=0, то Sj=-qj,

т.е. она принимает отрицательное значение => не является допустимой. Т.о. полученное ранее решение не удовлетворяет новому ограничению и в этой ситуации используется М-метод.
2.Комбинаторный метод

Идеи: Пусть решение задачи без ограничений целочисленности х* — целочисленная переменная, значение которой в оптимальном плане является дробным, то интервал

{x*]≤xrxr*]+1 не содержит допустимых решений с целочисленной координатой хr => допустимое значение хr должно удовлетворять одному из следующих неравенств:

хr≤[xr*],

xr≥[xr*]+1

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

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

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

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

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

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

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

Содержательно, как только получено допустимое значение, то соответствующее значение целевой функции может быть использовано в качестве верхней (в случае минимума) и нижней (в случае максимума) границы, наличие которой позволяет формализовать процедуру исключения прозондированной задачи.
Лекция № 4: «Транспортная задача».

Пусть имеется m пунктов производства (складирования) однородной продукции, запасы которой = А1, …, Аn. Имеется n пунктов потребления этого же продукта с потребностями В1, …, Вn; известны тарифы (транспортные расходы, связанные с доставкой единицей продукта из заданного пункта отправления в пункт потребления. {Cij} i=/> j=/>/

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

Формально требуется указать вектор х={xij} поставок (хij≥0 – ограничения, где хij количество единиц продукта, направленный из i-ого пункта отправления в j-ый пункт назначения), который удовлетворяет следующим условиям:

условие полного удовлетворения потребления для всех пунктов потребления />

Весь продукт, хранимый в пункте отправления должен быть вывезен ∑хij=Ai

достовляющ. минимум целевой функции />

транспортная задача исследуется только на минимум.

ТЗ называется закрытой (сбалансированной), если выполняется условие:

/>

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

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

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

/>

Из которого перевозку во все пункты назначения осуществляют по нулевым тарифам

б.) в случае избытка продукции вводится фиктивный пункт потребления с потреблением равным: />в который перевозки осуществляются по нулевым тарифам.

Метод решения ТЗ.

Пусть имеется ТЗ:

/>

хij≥0

/>

/>

/>

Общее число уравнений m+n.

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

/>

Которое «связывает» некоторые из этих m+n уравнений, то число линейных независимых уравнений (переменных) = n+m-1. Т.к. известны в задаче т. n, то в невырожденном опорном плане должно быть n+m-1 положительная компонента с остальными нулевыми.

Содержательно: имеем n+m-1 ненулевую поставку, которые образуют суммарный объем перевозок из всех пунктов отправления во все пункты потребления.

Опорный план вырожденный, если число положительных компонент строго меньше n+m-1

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

В таблицу заносят значения ненулевых поставок (xij>0) и такие клетки называются «занятыми» остальные – свободными.
Сопоставление исходного опорного плана:

Метод наименьших переменных.

Выбираем клетки с наименьшим тарифом и в эту клетку помещаем поставку xij=min(Ai,Bj) по минимальному тарифу перевозится максимальное количество продукта.

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

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

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

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

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

При построении цикла руководствуются следующими правилами:

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

в каждой свободной клетке цикл единственный

виды циклов:

/>
Каждой клетке цикла соответствует коэффициент целевой функции сij.

Пусть для свободной клетки ij построен цикл. Расставим чередующиеся знаки + и – начиная с – свободной клетки на которой цикл строится и осуществляется обход цикла. Подсчитаем сумму тарифов клеток цикла, который назовём оценкой свободных клеток ij. Свободные клетки – аналог небазисных векторов.
Первая транспортная теорема.

Для любой ТЗ оценка свободных клеток ij — элементов индексной строки симплекс-таблицы (соотв. ij небазисному вектору) и численно = zij-cij.

Опираясь на эту теорему рассчитаем индекс стока, т.к. ТЗ – задача на минимум, то критерий отрицательный:

— план оптимальный, если все оценки свободных клеток не положительны

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

Для построения нового опорного лана ТЗ необходимо:

определить свободную клетку с максимальной положительной оценкй.

для данной клетки строится цикл и расставляются знаки – и +

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

Такое перераспределение приводит к новому основному плану.

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

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

Определение: числа />называются потенциалами если выполняются условия:

х*={xij}-оптимальный план, то для занятых клеток выполняется

хij>0 Vj-Ui=Cij(*)

xij=0 Vj-Ui=Cij(**)

(c ij-тариф)

В этом случае Δij=Vj-Ui-Cij

Алгоритм:

находит базисное решение

из условия (*) вычисляем все потенциалы, но т.к. потенциалов m+n, а значений m+n-1, то система неопределенна и для получения единственного рения обычно полагают U1=0.

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

Лекция № 5: « Теория игр».

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

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

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

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

Допустимые действия игроков – правила игры.

Количественная оценка результатов игры – платеж.

Игра парная, если участвуют две стороны и множественная в противном случае.

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

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

Стратегия оптимальна, если при многократном повторе игры она обеспечивает игроку максимально возможный выигрыш (минимально возможный проигрыш), один из которых может выиграть i-ую стратегию из m возможных стратегий, а второй не зная выбора первого, выбирает j-ую стратегию из n возможных. В результате полагают, что первый игрок выигрывает величину Аij а второй проигрывает эту же величину.

Сопоставим матрицу, которая называется матрицей игры

/>

Строки – стратегии первого игрока, столбцы – второго.

Эта матрица – матрица резервов игры. В зависимости от выбора игроками своих стратегий
Игра размерностью mxn

Число α=max(min aij) называется нижней ценой игры. Это максимум из минимума по строкам.

Число β=mn(max aji) – минимум из всех максимумов, взятых по столбцам. Верхняя цена игры.

Для любой игры нижняя цена не превосходит верхнюю.

Если α=β=V, то игра называется определенной или игрой с седловой точкой:

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

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

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

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

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

Обычно, в случае решения игры в свешанных стратегиях х*=(х1*, …, хn*) у*=(у1*, …, уm*), где х*, у* — оптимальные смешенные стратегии, 1-ого и 2-ого игроков соответственно. Под выигрышным понимается величина

/>-

максимальныйвыигрыш математического ожидания.
Теорема Неймана:

Всякая конечная матричная игра имеет решение в смешенных стратегиях.

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

Критерий оптимальности – для того чтобы V* было ценой игры, а х* и у* были оптимальными стратегиями первого и второго игрока соответственно, необходимо и достаточно выполнение следующих условий:

/>

/>

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

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

Математически это выражается:
первый игрок выбирает стратегию хi, дающую max{min ∑aijуj ∑amjyj}, а второй игрок выбирает стратегию уj, дающую min{max ∑aijxi ∑ainxi}.

Согласно критерию оптимальности, для оптимальной стратегии первого игрока U* выполняется неравенство:

/>

Предположим, для определения, что V>0, это может быть, если ко всем элементам матрицы прибавить число С (С>0). Такое преобразование не приведет к изменению относительных часто оптимальных строк, а только увеличит цену игры на С единиц. Реальный выигрыш получаем после вычисления числа С из найденной цены игры после решения.

В этом случае поделим все неравенство на V, получим:

/>Обозначая получаем задачу линейного программирования.

/>, используя введенные обозначения переменных условий />переходим к

(*)/>

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

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

/>/>/>
Лекция № 6: « сетевое планирование».

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

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

Каждый проект – некоторый ориентированный график (сетевой график). Для этого задают:

— перечень всех операций проекта

— время, необходимое для выполнения каждой операции

— совокупность операций, которые предшествуют каждой операции.
Каждая операция представленная в виде дуги ориентированного графа, который построен по правилу:

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

Правило построения сетевой модели:

если (i,j) – операция, то в вершину i входят только дуги, которое представляют операции, непосредственно предшествующие данной.

Каждой операции соответствует только одна дуга (на одна операция не может появиться в модели два раза).

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

при включении в сетевую модель операции необходимо определить:

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

Какие операции непосредственно следуют после завершения данной операции.

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

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

Свойства ориентированного графика:

нет контуров. Контур – это ориентированный цикл.

есть одно начальное событие (вершина в которую не входит ни одна дуга) и финальное событие (вершина из которой не исходит ни одной дуги)

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

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

Определение: операция называется критической, если задержка начала её выполнения приведет к задержке срока выполнения всего проекта на такое же количество единиц времени.

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

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

Нумерация вершин происходит по алгоритму:

начальному событию присваивается № 1

присвоить № N любому пронумерованному событию для которого все непосредств. предшествующие события пронумерованы от 1 до N-1.

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

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

Пример:


/>

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

Пусть Е(х) – наиболее ранний из сроков наступления события х.

L(n) – наиболее поздний из сроков наступления события х, так то допускается своевременное завершение проекта.

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

L(n) – E(x) – длинна пути наибольшей длины от события х к конечному событию.

Рассмотрим операции (х, у). Какое максимальное время можно выделить для выполнения операции (х, у) без задержки своевременного завершения проекта)?

Операция (х, у) не может начаться раньше, чем Е(х) и закончиться познее, чем L(n), следовательно, для её выполнения может быть выделено время L(y) – E(x), следовательно, максимальная задержка к выполнения, еще допускающая своевременное завершение проекта =

L(n) – E(x) – t (x,y) ≥ 0. Эта величина называется полным резервом времени операции (х, у). Задержка выполнения операции, полный резерв времени которого = 0 приведет к такой же задержке всего проекта.
Какое количество времени можно выделить для выполнения операции (х, у) без введения дополнительных временных ограничений на последующие операции проекта?

Для выполнения этого условия операция (х, у) должна быть выполнена к моменту Е(у), поскольку операция (х, у) начинается не раньше чем Е(х), то на её выполнение без введения дополнительного времени ограничения на последующие операции проекта можно выделить Е(у) – У(х) единиц времени и тогда величина Е(у) – Е(х) – t(x,y) называется свободным резервом времени операции (х, у).
Какое максимальное время можно выделить для выполнения операции (х, у) без введения дополнительного времени на операция проекта?

Операция (х, у) должна начаться в момент L(x) как можно позднее для выполнения этого условия, а завершиться как можно раньше в момент Е(у), следовательно, для её выполнения можно выделить Е(у) – L(x) единия времени. Величина Е(у) – L(x) = t(x,y) это независимый резерв времени. Он может быть отрицательным и если эта величина отрицательно, то для своевременного завершения преокта необходимо введение дополнительных временных ограничений на некоторые операции этого проекта.

Полный резерв ≥ свободный резерв ≥ независимый резерв.

Определение: операция называется критической, если все три её резерва равны 0.

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

Свойства критических путей:

самый длинный путь из начального события в финальное.

критических путей может быть несколько.

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

Построение критического пути – это второй этап оптимизации проекта.

Следующий этап состоит в перераспределении ресурсов v;le операциями проектов с целью уменьшения длины критического пути. При этом допускается возникновение нового критического пути, который отличается от уже построенного.
Лекция № 7: «Динамическое программирование».

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

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

Пример задачи распределения:

Для расширения трех предприятий фирма выделила 5000000$. Каждое предприятие предоставляет проект в котором С – суммарные издержки, R – доходы. Цель фирмы – получить максимальную прибыли от инвестиций.

проекты

I

II

III

C1

R1

C2

R2

C3

R3

1

0

0

0

0

0

0

2

1

5

2

8

1

3

3

2

6

3

9

-

-

4

-

-

4

12

-

-




Сетевая модель

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

х1 – объем инвестиций, распределяемых на первом этапе

х2 – объем инвестиций, распределяемых на первом и втором этапах

х3 – объем инвестиций, распределяемых на первом, втором и третьем этапах.

Эначение х1 и х2 – заранее неизвестны, но они могут принимать значения из 1, 2, 3, 4, 5. х3 = 5

Каждому из возможных значений х1, х2, х3 поставляется в соответствие узел, ассоциируемый с одним из этапов (j=1, j=2 j=3).

Длины дуг, соединяющие узлы на некотором этапе с узлами на последующем этапе численно равны доходам от реализации лучшего проекта. Величина (х2 – х1) = объему инвестиций, распределенных только на втором этапе, следовательно дуга х1, х2 является допустимой лишь для проектов, затраты на реализацию которых не превышают (х2 – х1) и длина этой дуги = max (R) для всех таких проектов.

/>/>/>/>

Рассмотрим дугу L U

Из первого этапа во второй, следовательно между 1 и 2 предприятиями распределяет 4000000$, из них 2000000$ во второе и 2000000$ в первое.

На последнем этапе распределяется 5000000$. Из них 3000000 – в 1 и 2 предприятия; 2000000$ — в 3 предприятие.

По аналогии с сетевыми графиками максимальный доход соответствующий самому длинному пути с этапа G0 до этапа G3.

Регулентные соотношения.

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

Это отражает сущность принципа оптимальности Баумана составляет основу вычисление схемы ДП.