Двойственная задача линейного программирования

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

F=c1x1+c2x2+…+CnXn (19)

При условиях

A11x1+a12x2+…+A1nXn≤b1,

A21x1+a22x2+…+A2nXn≤b2,

……………………………….

Ar1X1+Ar2X2+…+ArnXn≤br,

Ar+11X1+Ar+12X2+…Ar+1nXn=br+1, (20)

………………………………………….

Am1x1+am2x2+…+mnXn=bm,

Xj≥0 (J=1,l≤n). (21)

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

F*=b1y1+b2y2+…bmyYm (4)

При условиях

A11y11+a21y2+…+am1ym≥c1,

A12y1+a22y2+…+am2ym≥c2

……………………………….. (22)

A1nY1+a2ny2+…+AmnYm=Cm,

Yj≥0 (l=1,r,r≤m), (23)

Называется двойственная по отношению к задаче

Задачи 19-20 и 21-22 образуют пару задач, называемую в линейном программировании двойственной парой.

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

1. Целевая функция исходной задачи 19-20 задается ее максимум, а целевая функция двойственной 22-23 на минимум.

2. Матрица

(24)

Составленная из коэффициентов при неизвестных в системе ограничений(20) исходной задачи 19-20, и аналогичная матрица

(25)

В двойственной задаче 22-24 получают друг из друга транспортированием

3. Число переменных в двойственной задаче (22-24) равно числу соотношений в системе (2) исходной задачи (19)-(21), а число ограничений в системе(23) двойственной задачи----числу переменных в исходной задаче.

4.Коэффициентами при неизвестных в целевой функции(22) двойственной задачи (22)-(24) являются свободные члены в системе(20) исходной задачи (19)-(21), а правым частям в соотношениях системы(23) двойственной задачи---коэффициенты при неизвестных в целевой функции (19) исходной задачи.

5. Если переменная Xj исходной задачи (19)-(20) может принимать только лишь положительные значения то J-e условие в системе(23) двойственной задачи(22)-(24) является неравенством вида “≥”. Если же переменная Xj может принимать как положительные так и отрицательные значения, то j-e соотношение в системе(23) представляет собой уравнение. Аналогичные связи имеют место между ограничениями(2) исходной задачи(19)-(21) и переменными двойственной задачи (22)-(24). Если j-e соотношение в системе (20) исходной задачи является неравенством, то l-я переменная yl может принимать как положительные, так и отрицательные значения.

Решение задачи линейного программирования


Vj Ui	V1=30	V2=8	V3=11	V4=12	V5=26
U1=0	³⁰ ⁶	²⁴ ⁸	¹¹ ¹⁵	¹² ⁰	²⁵ ²⁶
U2=4	²⁶ ⁴	⁴ ¹⁵	²⁹ ⁷	²⁰ ⁸	²⁴ ²⁰
U2=2	²⁷ ²⁸	¹⁴ ⁶	¹⁴ ⁹	¹⁰ ¹⁵	¹⁸ ²⁴
U2=24	⁶ ⁵	¹⁴ ¹⁶	²⁸ ¹³	⁸ ^-12	² ²⁰

F=6*30+15*11+4*26+15*4+15*10+5*6+20*2=729


Vj Ui	V1=12	V2=12	V3=11	V4=12	V5=20
U1=0	³⁰ ¹²	²⁴ ¹²	¹¹ ¹⁵	¹² ⁶	²⁵ ²⁰
U2=8	²⁶ ⁴	⁴ ¹⁵	²⁹ ³	²⁰ ⁴	²⁴ ¹²
U2=2	²⁷ ¹⁰	¹⁴ ¹⁰	¹⁴ ⁹	¹⁰ ⁹	¹⁸ ⁶
U2=6	⁶ ¹¹	¹⁴ ⁶	²⁸ ⁵	⁸ ⁶	² ¹⁴

F=15*11+6*12+4*26+15*4+9*10+6*18+11*6+14*2=693 (ед)

Графы и их применение

Основные понятия теории графов

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

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

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

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

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

Полный граф - это граф, в котором каждая вершина соединена со всеми остальными. Число ребер в полном графе без петель с N вершинами равно (N² - N)/2. В полном ориентированном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направлениях, а переход по ребру в орграфе - только в одном, в полном орграфе в два раза больше ребер, то есть их число равно N² - N.

Подграф (V_S, E_S) графа или орграфа (V, E) состоит из некоторого подмножества вершин и некоторого подмножества ребер, их соединяющих.

Путь в графе или орграфе - это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины A в вершину B начинается в A и проходит по набору ребер до тех пор, пока не будет достигнута вершина B. С формальной точки зрения, путь из вершины v_i в вершину v_j это последовательность ребер графа v_iv_i+1, v_i+1v_i+2, ..., v_j-1v_j. Мы требуем, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина - число ребер в нем. Длина пути AB, BC, CD, DE равна 4.

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

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

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

Ориентированным путём в орграфе называют конечную последовательность вершин , для которой все пары , (i=1,…k-1) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

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

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

Всякий простой неэлементарный путь содержит элементарный цикл.

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

Петля — элементарный цикл.

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

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

Основными понятиями являются: работа, события, пути.

Действительная работа в прямом смысле слова (например — подготовка трассы соревнований), требующая затрат труда, материальных ресурсов и времени;

Ожидание — работа не требующая затрат труда и материальных ресурсов, но занимающая некоторое время;

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

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

Исходное событие — начало выполнения комплекса работ;

Завершающее событие — конечное событие, означающее достижение конечной цели комплекса работ;

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

Событие определяет состояние, а не процесс.

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

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

Путь, предшествующий событию — путь от исходного события сети до данного события;

Путь, следующий за событием — путь, соединяющий событие с завершающим событием;

Путь между событиями i и j — путь, соединяющий какие-либо два события i и j, из которых ни одно не является исходным или завершающим событием сетевого графика;

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

Правила составления сетевых графиков

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

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

В сетевом графике не должно быть замкнутых контуров.

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

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

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

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

Для построения сетевого графика необходимо составить таблицу с перечнем всех событий и работ. Для оценки продолжительности работ применяется вероятностный принцип, при этом ответственный представитель по каждой работе делает две оценки и, на основе этих оценок, определяет ожидаемое время по формуле:3t_MIN + 2t_MАХt_ож = , где 5 t_MIN – минимальная продолжительность работы при благоприятных условиях t_MАХ– максимальная продолжительность работы при неблагоприятных условиях.Для контроля правильности работ в каждом случае необходимо рассчитать величину дисперсии по формуле:t²_t = 0,04 * (t_MАХ - t_MIN)²

Если t²_t > 1, то это свидетельствует о том, что не точно определены t_MАХ и t_MIN и поэтому необходимо повторить расчёт t_ож по новым значениям t_MАХ и t _MIN.