Математическое программирование
 Скачать 227.5 Kb.
|
1 2 Если одна из задач не разрешима из-за не ограниченности функции , то и вторая задача не имеет решения по причине не совместимости систем ограничений. Док-во : Согласно первой лемме СХ<=уb , если прямая задача не имеет решения zmax->бесконечности , то, очевидно, что нет такого допустимого решения (у) в котором значение функции было бы больше бесконечности. ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ И СВОЙСТВА ДВОЙСТВЕННЫХ ОЦЕНОК. Z=CX->max W=yb->min  Ax>=b ¦ y1 A- матрица коэффициентов x>=0 ¦ y>=0 y1>=c теорема : Для того что бы допустимое решение Х* и У* пары двойственных задач были оптимальными , необходимо и достаточно , что бы для них выполнялись условия «дополнительное не жесткости» Z=Cx->max W=yb->min Ax<=b ¦y YA>=C ¦x x>=0 y>=0
необходимость : Х* У* - оптимальное решение. Док-ть: 1 и 2 Док-во: т.к. Х* является оптимальным решением , то и я является допустимым решением => Ах*<=b¦y*>=0 Y*Ax*<=y*b; y* в ходит ОДР => Y*A>=C¦x*>=0 y*Ax*>=Cx* => Cx*<=Y*Ax*<=y*b, т.к. х* и у* - оптимальное решение , то Сх*=уb* , по первой теореме => Сх*=у*Ах*=у*b. Ч.т.д (С-у*А)х*=0 2) (у*А-С)х*=0 1) у*(Ах*-b)=0 достаточность Дано 1) 2) Док-ть Х* и У* - оптим. решение. Док-во: у*Ах*-у*b=0 Y*Ax*=y*b y*Ax*-Cx=0 yAx*=Cx* Cx*=T=y*b=> Cx*=y*b Вывод для практики : Если в оптимальном решении исходной задачи х*j ><0 , то соответствующее ограничение Д.З. превращается в оптимальное решение равенства. Если какое либо из ограничений исходной задачи в оптимальном решении превращается в строгое не равенство , то соответствующая переменная Д.З=0 Свойства двойственных оценок. В экономике вектор у, называется вектором двойственных оценок или «теневыми ценами». Двойственные оценки сырья и т.д. Свойства:
ТРАНСПОРТНАЯ ЗАДАЧА. Дадим постановку транспортной задачи в общем виде. Пусть имеется m- пунктов производства однородного продукта, мощности каждого пункта соответственно = а1 а2 а3 … аь(столбец) , имеется n- пунктов потребления данной продукции. Потребности которых составляют соответственно b1 b2 bn (строка) Известны затраты на перевозки единицы продукции из i-го пункта j- потребителю, которые составляют Сij денежных единиц. Требуется спланировать перевозки таким образом что бы суммарные затраты были минимальными. Математическая модель. Матрица С – матрица затрат. Обозначим через Xij кол-во единиц продукции от i-ог производителя j-потребителю. =>матрица m*n где последний элемент Xmn/ из условия Xij>=0 3) Предположим что српос = предложению т.е. сумма всех аi= сумме всех bj   х11+х12+…+х1n =a1x21+x22+…+x2n =a2 m 2) xm1+xm2+…+xmn = am x11+ x21 +xm1 = b1x12+ x22+ xm2 = b2 n x1n+ x2n+ +xmn=bn
Бывают задачи типа закрытого и открытого. А) предположим что спрос >предложения , т.е. сумма ai< суммы bj . Тогда что бы перейти к закрытой задачи вводят фиктивного производителя мощность которого равно am+1=   а в транспортно таблице вводится новая строка m+1 в которой am+1= ,а затраты = 0 (Cm+1,j=0) Б) Если > , т.е. предложение выше чем спрос. Вводят фиктивного потребителя bn+1=-, а в таблице добавляем фиктивный столбец с затратами =0 Очевидно что Т.З. является Л.П., то можно решить симплекс методом., но таблица которая будет состоять к примеру из 100 столбцов – считать не удобно , то используют такие методы как : распределительный метод, метод дифференциальных рент, метод потенциалов. Особенности Т.З.
Т.З. всегда имеет оптимальное решение если сумма ai= сумме bj. Д  ок-во: Z= CijXij->min   =ai (i=1,m) =bj (j=1,n) Xij>=0 Очевидно что решением будет Хij = aibj/ =aibj/ Просуммируем по i: = aibj/ai = bjai/ai = bjПро суммируем по j : = ai Xij=min(ai;bj)ТЕОРЕМА О РАНГЕ МАТРИЦЫ. Ранг матрицы системы ограничений = m+n-1  х11+х12+…+х1n =a1x21+x22+…+x2n =a2 m 2) xm1+xm2+…+xmn = am x11+ x21 +xm1 = b1x12+ x22+ xm2 = b2 n x1n+ x2n+ +xmn=bn Докажем что ранг матрицы (А) А1=(1,1,1,0…0000…000) (коэффициенты первого уравнения размерность m*n) А2=(0000,1111,0000000) А1+А2+…+Аm=(111111111111) Am+1 Am+2 A1+A2+…+Am=Am+1+Am+2+…+Am+n => Векторы линейно зависимые => уравнения Am+n системы линейно зависимые между собой , а раз они линейно зависимые , то r(A) Докажем что ранг = m+n-1 Ранг – наивысший порядок минора отличный от 0.
Из этого следует что число базисных неизвестных в Т.З. = m+n-1 , а остальные переменные будут свободными. Ч.Т.Д. Матрица Х=¦Хij¦ , называется допустимым решением Т.З. или допустимым планом , если она удовлетворяет системе ограничений и условиям не отрицательности. Допустимый план называется оптимальным , если Z при этом плане принимает свое минимальное значение. Этапы решения Т.З.
Метод нахождения первоначального опорного плана.
Х11=min(ai;bj) Клетка становится занятой – базисной. Если удовлетворен покупатель то столбец закрывается, если все со склада вывезли то закрывается строка. И.т.д. Если баланс по строкам и столбцам выполняется и число клеток (занятых) совпадает с рангом матрицы то получаем допустимый план. Но данный опорный план может быть далеким от оптимального, потому что не берутся в расчет расходы. Поэтому используют для этого метод минимального элемента. Если в середине таблицы одновременно закрывается строка и столбец , а число занятых клеток не равно рангу, то в следующую клетку ставят 0 базисный и клетка считается занятой -> выражденной решение. Переход от одного опорного плана к другому. Необходимо перейти к другому опорному решению, т.е. одну из базисных переменных сделать свободной , а одну из свободных занять, так же как и симплекс метод. Для перехода используют замкнутую ломаную линию. Цикл 0 замкнутая ломаная линия вершины которой лежат в клетках а звенья лежат в строках и столбцах. Это ломаная должна быть связной в том смысле что в каждой вершине встречаются только два звена. Циклы могут быть самопересекающимися , при чем т. пересечения не является вершиной. Цикл пересчета - называется цикл, одна вершина которого лежит в свободной клетке , а остальные в занятой. При переходе от одного плана к другому используются только циклы пересчета. λ>=0 λmin(xij) – i,j нечетные клетки цикла пересчета. Если в цикле пересчета в нескольких клетках разность будет равно 0 , то пишут базисный 0. Проверка плана на оптимальность. Теорема об оптимальности плана или теорема о потенциальности плана. Для док-ва составим двойственную к прямой задаче. Z  =Cijxij->minх11+х12+…+х1n =a1 ¦ -u1 x21+x22+…+x2n =a2 ¦ -u2 xm1+xm2+…+xmn = am ¦ -um x11+ x21 +xm1 = b1 ¦ V1 x12+ x22+ xm2 = b2 ¦ V2 x1n+ x2n+ +xmn=bn ¦ Vn xij>=0 V1-u1<=c11 Vm-Un<=C1n Формулировка : Для того чтобы решения Х состоящее Х=¦xij¦ (i=1,m) (j=1,n) б было оптимальным для Т.З. необходимо и достаточно что бы существовала система из m+n чисел таки что бы выполнялось условия Vj-Ui<=Cij (для свободных клеток) Vj-Ui=Cij (для занятых) Необходимость Х* - оптим. решение Т.З. Док-ть 1) и 2) условие Если Х* оптим. решение прямой задачи то по 1-ой т. двойственности существует и решение двойственной задачи , т.е. существуют такие числа Vj & Ui такие что Vj-Ui<=Cij, - 1 условие Хij(Vj-Ui-Cij)=0 но если клетка занятая то xij>=0 => Vj-Ui=Cij Достаточность : Дано : Xij>=0 Vj-Ui=Cij Доктть : Х* оптим решен.
Алгоритм потенциалов. Проверяем Vj-Ui=Cij и Vj-Ui<=Cij Совместный учет производственных и транспортных издержек. Предположим что имеется m-производителей и n-покупателей. Ai = (i = 1,m ) Bj = (j = 1.n ) Известны производственные затраты di (i = 1,n ) Спланировать перевозки так чтобы суммарные (производственные и транспортные) затраты были минимальными. Нужно решить обычную транспортную задачу, затраты которой Cij = Cij + d Блокирование перевозки или запрещение перевозок. Очень часто на практике при решение Т.З либо какой-то производитель или потребитель закладывает “запрет“ на продукцию. Если это производитель – то он может запретить перевозку своего товара любому потребителю своей продукции. Если это потребитель – то он может запретить перевозку товара к себе любому производителю с которым нехочет иметь дело. В этом случае клетка с номером i , j должна быть заблокирована. И осуществляется это следующим образом. В клетку с номером i , j место Cij записываем число m (очень большое положительное число). Задачи о назначении. Пусть имеются m исполнителей которые должны быть назначены на выполнение n работ. Известна матрица C. С – затраты при назначении i – исполнителя на выполнение j – вида работ C = Cij Произвести назначение таким образом, чтобы каждый исполнитель выполнял только 1 работу, и каждая работа выполнялась только 1 исполнителем. При этом затраты должны быть минимальными. Возможные постановки: Ai – Экономисты. (i = 1,m) Bj – Работа. (j = 1,n) Cij – Затраты. Ai – Строительные механизмы. Bj –Площади. Cij – производительность. Математическая модель. Предположим m=n. Введем целочисленное обозначение пусть Xij 1- i-ый на j—ю , 0 в противном случае. Получим матрицу из элементов 0 и 1. Так как исполнитель может быть назначен на одну работу и одна работа может быть выполнена только одним исполнителем в каждой строке и столбце только одна 1. Система ограничение все = 1 (по строкам и столбцам) Х –(0 ;1) Z=двойная сумма СijXij ->min =>Задача о назначениях является частной Т.З. , где ai и bj=1 причем r=m+n-1=2n-1>n –решение всегда выраждена. Теоремы на которых основаны решения задачи о Назначениях. Т. Кенинга Если элементы матрицы С, разделить на два класса , на основании свойства R , то минимальное число линий содержащих все элементы со свойством R = максимальному числу таких элементов со свойством R, не какие два из которых не лежат на одной прямой. Теорема: Решения задачи о назначениях не изменится если к матрице прибавить или отнять из каждого столбца иил каждой строки одно и тоже число. С=¦Сij¦ C1=¦Cij-Ui+Vj¦ - док-ть что Х не изменится. Z1(X)= (Cij-Ui+Vj)Xij=CijXij-UiXij+VjXij=Z(x)- Ui Xij +VjXij = > Z1(x)=Z(x)- Ui+Vj – очевидно что решение не изменилось Xij=1Изменилось только значение функции 3) Если можно найти такую матрицу назначений функции Х, для которой значение функции Z будет равно=0 то Х является оптимальным решением данной задачи. Если Xij>=0; Сij>=0, то произведение их Сij*Xij>=0 сумма их тоже >=0. Очевидно что самое минимальное число 0, Х – будет являться решением задачи. => назначение производится по 0. Алгоритм решения.
Задача коммивояжера. Постановка задачи: Известно что комиваяжер выезжает из города и должен посетить A1 , A2 , A3 ,…, AK городов и вернутся в город A1. Известно расстояние Cij между городами Ai – Bj причем известно Cij Cji. Cij = Cjj = . Спланировать маршрут таким образом, чтобы расстояние L для этого маршрута (I1 , I2 , I3 ,…, Ik ) было кротчайшим. Математическая модель этой задачи: х11+х12+…+х1k =1 x21+x22+…+x2k =1 xk1+xk2+…+xkk = 1 x11+ +x21 +xk1 = 1 x12+ x22+ xk2 = 1 x1k+ x2k+ +xkk = 1 Z =  CijXij min Маршрут – это цикл. Метод ветвей и границ.
F(x) min (1,2,3,…,K,1) XД (1,3,2,…,K,1) Для задачи допустимым планом является маршрут от 1 города, 2, 3. О.Д.Р. – есть множество маршрутов (перестановки).
  Д Нижней оценкой к где Д* множество – называется такое число * = (Д*) удовлетворяет условию * f(x) где XД*. Ветвлениею Ветвление на множестве Д такое разбиение множества Д на k 2 подмножеств. Дi (i =1,k) для которых справедливы следующие 2 условия.
В результате ветвей получим дерево решений. Вершина от которой нет ответвлений называется висячей вершиной. Если выходит две стрелки , то дерево называется диадическое дерево Перспективное ветвление. Пусть на каком то шаге дерево возможных вариантов , каждый из которых имеет нижнюю оценку , на очередном шаге выбирается для ветвления вершина с наименьшей минимальной оценкой. и та вершина становится перспективной. Признак оптимальности. F(x)=min оценки Д (последней) Пусть есть матрица Х* принадлеж Дк , такой что f(x*)= сигма (Дк) => Х* оптимальное решение. 1 2 |