10. Теорема двойственности и экономическая интерпретация двойственных задач

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

Вторая теорема двойственности или теоремао дополняющей нежесткости.

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

Условия (2.31), (2.32) называются условиями допол­няющей нежесткости. Из них следует:

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

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

 

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

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

 

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

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

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

Третья теорема двойственности или теорема об оценках.

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

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

 

Экономическая интерпретация

Таким образом относительная оценка i-ой дополнительной переменной дает величину прироста целевой функции на единицу увеличения элемента Bi вектора ограничений. Так как элемент Bi обычно представляет собой объем i-го ресурса то относительная оценка равная Yi называется оценкой ресурса (оценкой единицы i-го ресурса) ибо она представляет относительную ценность единицы дополнительного ресурса. Эти относительные оценки являются маргинальными оценками в том смысле что они действительны лишь при таком диапазоне изменения ресурсов Bi когда текущий базис остается оптимальным.

 

Маргинальная оценка ресурсов

Оценки ресурсов связаны скорее с ограничениями а не с переменными.

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

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

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

11. Транспортная задача. Определение исходного опорного решения

Постановка ТЗ в матричной форме

Классическая транспортная задача ЛП формулируется следующим образом. Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы величины:

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

- объем потребления (спрос) j-го потребителя, i=1, n ;

 - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

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

 

Постановка ТЗ в математической форме

Математическая модель транспортной задачи имеет вид

 

Методы нахождения начального опорного плана

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

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

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

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

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

Постановка задачи

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

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

12. Метод “Северо-западного угла”. Метод “Минимального элемента”

На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. Для того, чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце . Если существующий запас позволяет перевезти всю потребность, то · в клетку (i,j) в качестве перевозки вписывается значение потребности ; · j-й столбец вычеркивается, поскольку его потребность уже исчерпана; · от существующего запаса в i-й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т. е. . Если существующий запас не позволяет перевезти всю потребность, то · в клетку (i,j) в качестве перевозки вписывается значение запаса ; · i-я строка вычеркивается, поскольку ее запас уже исчерпан; · от существующей потребности в j-й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т. е. . Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА

Метод минимального элемента сводится к тому, что на каждом шаге отыскивается минимальный элемент cij из незаполненных клеток, после чего величина xij полагается равной min ( ai, bj ). Далее, после коррекции на ai (или на bj ) процедура повторяется до получения плана. В этом случае получаемое начальное опорное решение более близко к оптимальному, что позволяет существенно сократить количество итераций численного метода решения задачи. Если опорное решение невырожденное, то оно содержит m+n-1 положительных значений базисных переменных. Если базисное допустимое решение вырожденное (содержит менее m+n-1 ненулевых значений переменных), необходимо некоторые из нулевых значений считать принадлежащими базису с тем, чтобы общее число базисных переменных было бы равно m+n-1. Если число ненулевых значений в опорном решении превышает m+n-1, то опорное решение построено неверно.

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

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

d_ij = с_ij^* - с_ij, где с_ij^* расчётные затраты(косвенне тарифы)… с_ij затраты (истинные тарифы)

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

алгоритм:

Алгоритм метода потенциалов состоит в следующем: каждому поставщику A_i ставится в соответствие некоторое число u- потенциал; каждому потребителю B_j ставится в соответствие некоторое число v- потенциал.

Получаем систему с числом уравнений. Из этой системы определяем неизвестные потенциалы u_i и v_j.. Если клеток с не оптимальным решением несколько, то выбирают любую из них.  Для правильного перемещения перевозок, строят так называемый цикл. ставят там + или -. и выполняем до тех пор пока все критерии для незаполненных клеток окажутся d_ij<=0. Затем вычисляется оптимальная стоимость перевозок.

14. Основные понятия теории графов (Граф, вершина, степень вершины, дерево и.д.

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

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

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

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

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

Дерево — это связный граф без циклов.

15. Остовное дерево. Алгоритм (Prim). Алгоритм (Kruskal)

Остовное дерево.

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

Пошаговая реализация Прим

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

Алгоритм:

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

На каждом последующем шаге к уже построенному графу добавляется одно ребро.

Шаг k. Если подграф уже построен, то граф  получается из  добавлением ребра l(эль), обладающего следующими свойствами:

l инцидентно какому-либо ребру G_k-1,

При добавлении l к G_k-1 не образуется циклов,

l имеет минимальный вес среди ребер, удовлетворяющих условию 1) и 2).

 

Пошаговая реализация Краскал

Шаг 1. Тот же, что и в алгоритме Прим.

Шаг k. Если  уже построен, то граф  получается из Gk-1 добавлением ребра l, обладающего следующими свойствами:

При добавлении l к Gk-1 не образуется циклов, l имеет минимальный вес среди ребер, удовлетворяющих условию 1).