В14 Прямая и двойственная задачи. Правила составления двойственной задачи

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую др. задачу, называемую двойственной по отношению к исходной или прямой задачи. Двойственная задача строится по определенным правилам: 1. Число переменных в двойственной задаче равно числу ограничений системы исходной задачи. 2.Коэф-ми перед переменными в целевой ф-ции двойственной задачи выступают свободные члены из системы ограничений исходной задачи. 3. если прямая задача решается на МАХ, то двойственная на MIN и наоборот.4 Число ограничений системы двойственной задачи=числу переменных исходной задачи. 5. Коэф-тами перед неизвестными в системе ограничений двойственной задачи выступают коэф-ты перед неизвестными из системы ограничений исх. Задачи, но строки и столбцы нужно поменять местами 6.Свободными членами системы ограничений в двойственной задаче явл-ся коэф-ты перед переменными из целевой ф-ции исх.задачи. 7. Если ограничения двойственной задачи соответсвуют перем-й прямой задачи, кот. подчиняется условию неотрицательности, то это ограничение имеет вид неравенства; если двойственная задача на MIN, то знак неравенства ³. Если ограничение двойственной задачи соотв-т перемен-й прямой задачи, кот. не подчиняется условию неотрицательности, то это огранич-е имеет вид уравнения. 8Если переменная двойственной задачи соот-т ограничению - неравенству исходной задачи, то эта переменная подчиняется условию неотрицательности. Если переменная двойственной задачи соответствует ограничению – уравнению исходной задачи, то она не ограничена по знаку. Замечания: Если исходная задача решается на максимум, а система ограничений содержит неравенства разного знака, то целесообразно привести их к виду ≤,тогда неравенство системы ограничений двойственной задачи будут иметь вид≥

В12 Построение опорного начального плана м-дом искусственного базиса.

F (Х)= С1Х1+С2Х2+…+СnХn®MAX (1)

ìа11х1+а12х2+а1nхn=b1

íа21х1+а22х2+…+а2nхn=b2 (2)

îаm1х1+аm2х2+…+аmnхn=bm

х1³ 0 х2³ 0 хn ³0 (3)

В данном случае ограничения в системе (2) не содержат базисных переменных Þ к каждому равенству прибавляют по одной переменной (искусственные переменные), при этом величина Сn+i предполагается достаточно малым отрицательным числом, если задача решается на МАХ (Сn+i= –М)и достаточно большим положительным числом, если задача решается на МIN (Сn+i=М). В результате получают так называемую расширенную задачу. Для задачи 1;2;3; расширенная задача имеет вид:

F(X)=C1X1+C2X2+...+CnXn-MXn+1 – MXn+2 – MXn+m®MAX (4)

ìа11х1+а12х2+...+а1nхn+xn+1=b1

íа21х1+а22х2+…+а2nхn+xn+2=b2 (5)

îаm1х1+аm2х2+…+аmnхn+xn+m=bm

х1³ 0 х2³ 0 хn ³0 xn+m³0 (6)

задача 4;5;6; записана в базисной форме Þее можно решать симплекс-методом. Первый опорный план таков, что в базисе будут искусственные переменные, однако коэф-ты Сn+i у абсолютной величины значительно превосход. остальные коэф-ты целевой ф-ции позволяет выводить из базиса искусственные переменные и вводить в базис переменные исходные задачи. Для отыскания оптимального плана исп-ой задачи исп-ют след. теорему: если в оптимальном плане Х* расширенной задачи переменные Хn+i=0,то план Х*=(Х*1,х*2,…,Х*n)явл-ся оптимальным планом исходной задачи. Решаем расширенную задачу симплекс-методом необходимо руководствоваться след.:1. для первого опорного плана F(X) и дельта оц-ки состоят из двух частей: одна из кот. зависит от n, а др. нет. В симплексной таблице две оценочные строки. При этом /m+2/-ой строке помещают коэф- ты при М, а /m+1/-ой строке помещают слагаемые не содержащие М. Проверка рассматриваемого опорного плана на оптимальность, а также выбор ключевого столбца осущ-тся по показателям /m+2/-ой строки искусственные переменные исключ-е из базиса на некоторой итерации в дальнейшем не могут быть введены в базис и соответствующий столбец можно не заполнять. 2. пересчет симплекс-табл. При переходе от одного опорного плана к др. производят по общим правилам симплексного метода. Итерационный процесс по /m=2/-ой строке производят до тех пор пока не исключат из базиса все искусственные переменные. Затем процесс отыскания оптимального плана продолжается по /m+1/-ой строке. Доказано, что: 1. если в оптимальном плане расширенной задачи хотя бы одна из искусственных переменных положительна, то исходные задачи не имеют допустимых планов. 2.если расширенная задача не имеет решения то исходная задача не разрешима. В13. Построение начального опорного плана общей задачи.

Рассмотрим на примере:

F(X)=5X1+X2®MAX

Х1-Х2£5

4Х1+Х2³1

7Х1+2Х2=4

Х1³ 0; Х2³ 0

Общая задача смешанная система ограничений.

F(X)=5X1+X2+0X3-0X4®MAX (канонич. Вид)

Х1-Х2+Х3=5

4Х1+Х2-Х4=1

7Х1+2Х2=4

Хi³ 0

Т.к. во 2 и 3 уравнениях нет базисных переменных, то добавим туда искусственные переменные и будем решать задачу по м-ду искусственного базиса.F(X)=5X1+X2+0X3-X4-MX5-VX6®MAX

Х1-Х2+Х3=5

4Х1+Х2-Х4+Х5=1

7Х1+2Х2+Х6=4

Х1…Х6³0

Первое опорное решение:Х1=Х2=Х4=0; Х3=5; Х5=1; Х6=4.

Далее строим симплекс-таблицу

Задача составления оптимальной смеси.

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

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

Известно:

- содержание каждого компонента в единице каждого исходного материала.

- требуемое количество каждого компонента в смеси.

- цена за единицу каждого исходного материала.

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

Условные обозначения:

n – количество исходных материалов

j – порядковый номер вида исх.материала

m –количество компонентов

i – порядковый номер вида компонента

aij – содержание i–го компонента в единице j–го исходного материала

bi – min требуемое количество i-го компонента в смеси

сj – цена единицы j-го исходного материала

xj – количество j-го исходного материала в смеси

маленькие буквы в формулах большими!!!

Математическая модель:

F(X)=C1X1+C2X2+…+CnXnàmin (1)

A11X1+A12X2+…+A1nXn > B1

A21X1+A22X2+…+A2nXn > B2 (2)

………………………

Am1X1+Am2X2+…+AmnXn > Bm

X1, X2, …, Xn >0 (3)

8 и 9. 8. Геометрическая интерпретация задачи линейного программирования; 9. Графический метод решения задач линейного программирования.

Совокупность чисел Х=(Х1;Х2;…;Хn), удовлетворяющих ограничениям задачи, называется допустимым решением или допустимым планом.

План Х*=(Х1*;Х2*;…;Хn*), при котором целевая ф-я задачи принимает свое экстремальное значение, называется оптимальным.

Пусть задача задана в двумерном пространстве:

F(x)=c1x1+c2x2 à max (1)

a11x1+a12x2 < b1

a21x1+a22x2 > b2 (2)

…………………..

am1x1+am2x2 < bm

x1>0, x2>0 (3)

(1)-целевая ф-я

(2)-система ограничений

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

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

ai1x1+ai2x2=bi (i=1;m)

Условие неотрицательности определяет полуплоскости с граничными прямыми х1=0 и х2=0 соответственно.

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

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

Уравнение целевой ф-ии c1x1+c2x2=h для любого фиксированного h, представляет собой прямую. При различных значениях h получатся параллельные между собой прямые. Направление увеличения h задается вектором с=(с1;с2), при этом последняя общая точка ф-ии и многоугольника решений и определяет оптимальный план задачи.

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

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

Если допустимый многогранник неограничен, то возможны случаи:

1.Существует единственное решение задачи.

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

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

4.Ограничения противоречивы и множество допустимых решений пустует.

в пп 1,2,3,4 есть графики!!!

Опред-е опт-го плана трансп-й задачи методом потенциалов.

1. Сост-м сист. потенциалов. Для кажд. пункта отпр-я и назнач-я опр-т потенциалы. u_i – потенц. отпр-ей, n_j – потенц. потр-ей. Знач-е одного из потенц-в можно положить равным про-му числу (допустим u₁ = 0). Знач-е ост-х потенц-в опр-ся однозначно из усл-я

u_i + n_j = c_ij, кот. выполн-я для занятых клеток. Найденные зн-я потенц-в запис-т в столбец и в строку, добавл-е к табл. усл-я задачи. 2. Проверка выполн-я усл-я опт-ти. Для кажд. свободной клетки опр-т D_ij = u_i + n_j - c_ij. Если среди чисел D_ij нет полож-х, то получен опт-й план. Иначе переходят к новому опорному плану. 3. Постр-е нового опорного плана. Из D_ij > 0 (D_ij < 0) выбирают max по абсол-й величине. Клетку, кот. соотв-т это число, делают занятой. При этом необх. изменить V-мы поставок в некот. др. клетках, связ-х с дополн-й клеткой, так назыв-й цикл – ломанная линия, выход-яя из заполн-й клетки и возвр-ся в неё, вершины кот. расположены в занятых клетках, а звенья вдоль строк и столбцов, причём в кажд. вершине встреч-ся ровно 2 звена, 1 из кот. наход-ся в строке, а др. в столбце (точки самопересечения линии не явл-ся вершинами). Каждой клетке, соотв-й вершине цикла, приписывают опр-й знак. Начинают со своб-й клетки. В ней ставят знак «+», а ост-м клеткам поочерёдно «-» и «+». В клетках с «-» вершинами опр-т min V перевозки. Это кол-во прибавляют в клетка с «+» и вычит-т в клетках с «-». В рез-те клетка, кот. была свободна, станет занятой, а «-» клетка с min V станет своб-й. В рез-те получаем нов. опорн. план. Возвр-ся к шагу 1.

Примеч-я. Если наибольших по модулю «+»(«-») D_ijнеск-ко, то следует выбрать клетку, для кот. меньше тариф. Если в «-» имеются 2 или более одинаковых min числа, то освобожд. лишь одну из таких клеток, а др. ост-т занятой с нулевыми поставками.