Лекции - Математическое программирование

Подождите немного. Документ загружается.

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Развитие относится к 30-ым годам. Математик – Толстой . Бурное развитие после войны.

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

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

в каком-то смысле – там и возникают задачи математического программирования.

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

моделирование

Найти max или min функции Z=f(

уx,

) , где φ(

уx,

)



, где (i=1,k); φ(

уx,

)=b

, где

(i=1,k) (i=k+1, L);

- управляемый параметр.

- неуправляемый параметр. (не учитывается)

Чтобы решить задачу имея математическую модель нужно знать математические метод (Гауса,

Крамера, матричный и.т.д) Зная метод => нужно знать алгоритм.

КЛАССИФИКАЦИЯ МЕТОДОВ.

В зависимости от того какими являются функции f и φ

, задачи делятся на два класса :

1) Если функции f и φ

линейны относительно параметров Х и У , то имеем задачу линейного

программирования. (Л.П.)

2) Если хотя бы одна из функций f и φ

нелинейная относительно параметров

, то имеем

нелинейную задачу. (Н.П.)

Для Л.П. существует универсальный способ. Симплекс – метод Основ. разработку дал Дансон.

Х3

Х2

Х1

В Н.П. самым изученным является выпуклое программирование – это когда находится минимум

выпуклой функции на выпуклом множестве или максимум вогнутой функции на выпуклом

множестве. Существуют так же :1) Д.П. – динамическое программирование , вся задача

разбивается на n-этапов. 2) Стохастическое программирование – случайные параметры. 3)

Э.П. – эвристическое программирование , где оптимальное решение найти сложно из-за

большого количества вариантов. 4) Ц.П. – целочисленное программирование.

Транспортная задача.

Имеется два пункта однородного продукта. Мощность 1

го

400т.; 2

го

– 500т., имеется 3 пункта

потребления этого продукта. Известны затраты на перевозку 1т. продукции . Из 1

го

пункта к 1

му

– 2млн. р. ; 2

му

– 3 млн. р; 3

му

– 4 млн. р. Из 2

го

- 1

му

– 5 млн. р.;2

му

- 4 млн. р.; 3

му

- 2 млн. р.

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

1) нужно 300 т. 2) нужно 400 3) нужно 200 т.

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

– кол-во тонн продукции перевезенной из пункта i к пункту j- му потребителю. Найти план

перевозок. (матрицу Х) Х= х

Предложение = спросу.

900 900

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

закрытом моделирование все выражения равенства.

300

400

200

400

x11

x12

x13

500

x21

x22

x23

b –потребность .



=400

=500

2 x

=300

=400

=200

3 x

>=0 (i=

2,1

) (j=

3,1

)

Функция цели 1 Z=2x

+3x12+4x13+5x21+4x22+2x23 -> min

1.2.3 математическое моделирование задачи.

Различают другие типы задач :

1) задачи о диете или о рациональном питании.

2) задачи производственного планирования

3) на составление математического моделирования

4) задачи о раскрое

5) задачи о назначениях.

Метод Гауса.

М.Г. вычисляется с помощью таблиц Гауса.

2х1-х2+х3=3

х1+3х2-2х3=1 разрешающий элемнт.

х2+2х3=8 разрешающая строка разреш.столбец.

Х1 Х2 Х3 Св.чл



проверка

2 -1 1 3 5 5

1 3 -2 1 3 3

0 1 2 8 11 11

0 -7 5 1 -1 -1

1 3 -2 1 3 3

0 1 2 8 11 11

0 0 19 57 76 76

1 0 -8 -23 -30 -30

0 1 2 8 11 11

0 0 1 3 4 4

1 0 0 1 2 2

0 1 0 2 3 3

1)разрешающую строку делим на разрешающий элемент. 2) в разрешающем столбце элементы

заменяем на ноли. 3) Все остальные элементы таблицы считаются по правилу прямоугольника.

arsarjaisaijarsa



переход от одной формы модели к другой форме модели , различные формы моделей

З.Л.П.

В зависимости от системы ограничения различают в Л.П. три формы модели 1) каноническая 2)

стандартная форма 3) общая форма. Эти три формы эквиваленты между собой в том смысле ,

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

Стандартная форма модели З.Л.П. . Система задачи формируется : Найти вектор х,

удовлетворяющий системе ограничений и условию не отрицательности.

а11х1+а12х2+…+а1nxn<=b1

a21x1+a22x2+…+a2nxn<=b2

….

am1x1+am2x2+…+amnxn<=bn

xj>=0 j=1,4; Z=c1x1+c2x2+..+cnxn->max

A-матрица (m*n) Z=cx->max Ax<=b x>=0 ; C=(C1 C2 …Cn) b(b1 b2..bm)

Каноническая тоже самое только в системе ограничений = и Ax=b.

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

a11x1+a12x2+...+a1nxn=b1

am1x1+amnxn=bm

Xj>=0 (j=1,l) l<n Для которого Z=с1х1+cnxn -> max

Для того что бы решать задачи Л.П. симплекс методом необходимо иметь каноническую форму

модели, поэтому необходимо знать , как перейти от одной формы модели к другой .

Переход от стандартной формы к канонической форме.

1) ai1x1+ai2x2+…+ainxn<=bi (2)

ai1x1+ai2x2+..+ainxn+ainxi+n=b xn+i>=0 , i=1,m – балансовые переменные. (1)

Можно доказать, что все решения системы 1 равны решениям неравенства 2 и в этом сысле они

эквивалентны. Функцию цели эти переменные(xn+i) могут быть введены с коэффициентами =0

=> z=c1x1+..+cnxn+oXn+1+..+oxn+m->max

Переход от канонической к стандартной.

Осуществляется двумя способами.

1. а=b (a>=b a<=b) -> a1x1+a2x2=b a1x1+a2x2>=b

a1x1+a2x2<=b

2. Z=c1x1+…+cnxn->max

a11x1+…+a1nxn=b1

a21x1+…+a2nxn=b2

am1x1+…+amnxn=bm (m<n – бесконечно много решений)

1. Приводим к единичному базису методом гауса. Приравняем все свободные переменные к 0,

т.е. xm+1=xm+2=0 то получим первоначальное базисное решение.

2. Выражаем все базисные переменные через свободные.

Х1=b1-a1,m+1xm+1-..-a1,nxn>=0

Xm=bm-am,m+1-…-amnxn>=0

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

Z=c1(b1-..-a1nxn)+c2(b2-..-a2nxn)+cm(bm-..-amnxn)+cm+1xm+1+…+cnxn->max/

Переход от задачи max к min и наоборот.

Во всех формах моделях все сводится к max, но иногда необходимо найти min/

Z=f(x)

min

z1max

z1=f(x)

Чтобы перейти от задачи min к max достаточно поменять знак и ввести новое значение

функции.

Графический метод решения Л.П.

Понятие: допустимого , оптимального , опорного решений, понятие области допустимых

решений.

Вектор Х называется допустимым решением , если он удовлетворяет системе ограничений и

условиям не отрицательности если они есть.

Вектор Х называется оптимальным решением если он является допустимым , а функция цели в

этом решении достигает своего оптимального значения. (max or min)

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

x1+x3 –x4=1

x2+2x3+4x4=-2

x1 и х2 –базисные неизвестные. Х3,х4 - неизвестные .

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

и получаем базисное решение. Оно является не опорным , т.к. х=-2. Данное решение допустимое

, базисное, не опорное.

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

системы.

Геометрическая интерпретация линейного неравенства.

n=2 a1x1+a2x2<=b (n-кол-во переменных , m число неравенств )

Из математики знаем что геометрическим образом уравнение а1х1+а2х2=b – прямая на

плоскости х1 х2 Прямая разбивает плоскость на две полуплоскости . а1х1+а2х2<=b и >= , т.е.

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

данного неравенства нужно взять любую точку M и подставить в данное неравенство. И если не

равенство удовлетворяется, то точка эта принадлежит той полуплоскости в которая является

решением . И наоборот.

Геометрическая интерпретация системы линейны неравенств.

n=2 . a1x1+a1x2<=b1 ГИСЛН – является пересечение всех полуплоскостей соответству

a2x1+a2x2<=b2 ющих каждому неравенству системы , таким образом нашли ОДР.

am1x1+am2x2<=bm

Возможные случаи ОДР.

1. ОДР является точка.

2. ОДР выпуклый многоугольник.

3. ОДР выпуклая многоугольная область.

4. ОДР – пустая область

Графический метод .

ГМ состоит из двух этапов.

1) ОДР.

2) Среди всех решений необходимо найти такое решение при котором Z достигает своего либо

max или min.

Grad показывает наискорейшее возрастание функции. (С – коэффициент) (линии уровня)

Возможные случаи

1. задача имеет единственное решение.

2. Задача имеет – бесконечно много решений.

3. Задача не имеет решений а) нет ОДР б) в случаи когда zmax - ф-ия не ограниченной сверху

линией уровня и наоборот.

Графический метод можно применять если имеется только две переменные или задача может

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

ОПОРНЫЙ ПЛАН.

Свойства допустимых планов.

1) Выпуклая линейная комбинация точек . х1 х2 …хk сумма вида α1х1+ α2х2+ ...+ αkxk , где





αi =1 (αi>=0 αi – коэффициент линейной комбинации).

2) Выпуклым множеством называется такое множество т. Д на плоскости , когда вместе с

любыми двумя точками Х1є Д ; Х2 є Д принадлежащим множеству Д. Ему принадлежит и

их выпуклая Л.К. х=tx1+(1-t)x2 є Д 0<=t<=1

3) Крайняя точка – т.Х выпуклого множества называется крайней если она не может быть

представлена в виде выпуклой Л.К. любых двух точек этого множества (n=2)

Опорное решение – это допустимое базисное решение имеющая не более чем m положительных

элементов , и причем векторы столбца матрицы соответственно положительны координатам

вектора линейны независимы.

Свойства допустимых планов.

Теорема №1

Множество допустимых планов З.Л.П. выпукла если оно не пусто.

Дано: Д- не является пустым множеством – ОДР

Доказать Ж Д- выпуклое множество.

Док-во :

Х1 єД; Х2 єД,то оно удовлетворяет системе ограничений в З.Л.П. Z=cx->max Ax=b X>=0

Ax1=b 0<=t<=1

Ax2=b (1-t) => tAx1+(1-t)Ax2=bt+b(1-t) = A[tx1+(1-t)x2]=b

t>=0

x1; x2>=0 => x>=0

1-t>=0

Ax=b X- решение задачи.

Х = tx1+(1-t)x2 0<=t<=1, согласно опр. Имеем выпуклое множество – Д, т.к. с любыми двумя

точками ему принадлежит и их выпуклая Л.К.

Теорема № 2

Если целевая функция имеет максимум на выпуклом многограннике решений, то это максимум

достигается в вершине многогранника..

Дано: Zmax->X

Док-ть X

вершина.

Zmax=C X

Док-во: Дан многогранник. А,В,С,Д,Е – вершины. (Док-во проведем от противного)

– не вершина , тогда согласно опр. Крайней точки , X

– не крайняя точка , и может быть

представлена в виде выпуклой Л.К. точек хi є ОДР

C X

>Cxi (т.к. С X

->max)





i 1

αiXi





i 1

αi=1 αi>=0

Найдем значение функции Z=C X





i 1

αiXi=





i 1

αiCXi<





i 1

αiCX

=CX





i 1

αi=CX

В каждом слагаемом сменим Xi на Х

СХ

<CX

– противоречие.

Теорема №3

Об альтернативном оптимуме.

Если целвевая функция достигает своего оптимального значения в нескольких вершинах (т)х1

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

Дано : Док-ть: х=





i 1

αiXi

Xi , i:=1,k





i 1

αi=1 αi>=0 CX=d

Zmax=C{i=d

Док-во

Найдем Z=СХ=C





i 1

αiXi=





i 1

αiCXi=





i 1

αid=d





i 1

αi=d

Теорема № 4

Вектор Х является опорным решением тогда и только тогда , если он является вершиной

многогранника.

Если переменных n>3 то говорят гиперплоскость, положение точек в т – мерном

пространстве.

ИДЕЯ СИМПЛЕКС МЕТОДА.

Симплекс метод является универсальным.

Симплекс метод – аналитический метод.

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

записана в виде равенств (каноническая форма)

Б)Преобразовать что бы bi >=0 i=1,m

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

Поэтому за разрешающий элемент выбирается строго положительный элемент.

Д)Приравниваем свободные к 0 , получаем первоначальное базисное неотрицательное

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

2. Рассматривая функцию цели выясняем является ли полученное решение оптимальным.

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

вершине (опорному решению) Переход осуществляется по определенному правилу по

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

одна из свободных перейти в базисную.

Алгебра симплекс метода.

Х1 Х2 Х3 Х4 Х5 св.чл

1 0 1 6 2 8

0 1 1 0 3 9

0 0 7 -1 -3 -0

1 -2/3 1/3 6 0 2

0 1/3 1/3 0 1 3

0 1 8 -1 0 9

1/6 -2/18 1/18 1 1/3

0 1 -9

1/6 8/9 8 1/8 0 0 1/3

Особенность выделенная клетка.

1) Чтобы решать симплекс методом необходимо Z->min (перейти к min)

2) В строке Z записываются коэффициенты ф-ии цели, а свободный член записывается в

выделенную клетку св.чл. с противоположным знаком.

3) Сделаем свободные члены неотрицательными.

4) Приводим систему ограничений к единичному базису методом Гауса, выбирая за

разрешающий элемент положительный элемент.

5) Функция цели должна быть выражена только через свободные неизвестные , чтобы

определить оптимален ли полученный опорный план. Для определения опорного плана

свободные элементы =0 r=(7;-1;-3} Среди них выбираем самый отрицательный и делаем

разрешающий столбец. Для выбора разрешающей строки находится min-ое из отношений

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

столбца

6) Для выбора разрешающей строки находится min-ое из отношений свободных членов

системы ограничений к положительным коэффициентам разрешающего столбца.

Альтернативный оптимум.

Предположим найдено оптимальное решение. r>=0. Признаком альтернативного оптимума в

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

компонента rj =0 , для найденого оптимального плана (Х

) то можно найти еще одно

оптимальное решение Х

, значение в котором будет таким же как и значение в Х

. Z(Х

)= Z

(Х

=Zmin

За разрешающий столбец берем rj =0 Zmin=Z(X

)=-Q (свободный член в Z) Q

=aij*Q-bi*rj/aij =

Q-(bi*rj/aij)=Q bi>0 aij>=0

Сделав шаг метода Гауса , получим новое решение , а значение функции в т Х

будет точно

таким же как и в Х

– т.е. задача Альтернативного оптимума.

Монотонность и конечность алгоритма симплекс метода.

Покажем , что применяя алгоритм симплекс метода к З.Л.П. мы получим , что значение

функции монотонно убывает. Предположим, что на кокаком то шаге симплекс метода выбран

разрешающий столбец rj<0 , а за разрешающую строку выбрана i строка. Покажем что значение

функции не возрастает , если мы применим один шаг симплекс метода. Qнов=aij*Q-bi*rj/aij=

Q-bi-rj/aij<=0 (bi>=0 rj<0 aij>=0) Qнов>=Q -Qнов<=-Q

Так как многогранник имеет конечное число вершин , то алгоритм симплекс метода будет

конечен.

Проблема выражденности.

Если получено в опорном плане число положительных координат меньше чем m , то решение

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

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

строка в которой bi=0 Тогда моежт быть проблема зацикливания, т.е. возврат к прежней

вершине , для того чтобы избежать этого нужно «расклеить» точки для чего служит ипсилон

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

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

Если в конце преобразований получена таблица , то столбец соответсвующем столбце нет ни

одного положительного элемента то Zmin->- бесконечности ( нет решения)

Если в результате преобразований сстрока превратилась ( 0 0 0 0 = 7), то задача не имеет

решения по причине не совместимости систем . Нет ОДР.

Если оптимальное решение и соответствующий ему вектор (r) имеет 0 координату то задача

на альтернативный оптимум. Что бы найти второе решение берем за разрешающий столбец 0.

Метод искусственного базиса.

Z=CX->min В данной задаче нет естественного базиса. Введем в каждое ограничение

Ax=b искусственную переменную «у»>=0 Z преобразуем в T. М – полож. большое чис

X>=0 -Z задача.

Ах+у=b

Х>=0 у>=0

T=CX+M*y->min (М –задача)

Теорема . Если М задача имеет оптимальное решение , то Z – задача : а) тоже имеет решение ,

если все искусственные переменные = 0. Б) Z- задача не имеет решения если хотя бы одна из

искусственных переменных не равна 0, систем ограничений будет не совместна. Если М задача

не имеет решения ,т.е. Tmin ->-бесконечности , то и Z- задача тоже не имеет решения.

ТЕОРИЯ ДВОЙСТВЕННОСТИ .

Каждой задаче Л.П. можно поставить в соответствие двойственную задачу , решения которой

дает немедленное решение прямой задачи.

Стандартная форма.

Z=CX->max

Ax<=b

x>=0 1)

Двойственной задачей к данной З.Л.П. называется задача вида

w=yb->min

YA>=C

Y>=0 2)

Задача 1) и 2) называется пара двойственных задач.

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

задачи называются взаимозаменяемыми или сопряженными.

(y- строка)

(y1,y2..ym) a11

a21

am1

Экономический смысл : Экономически двойственную и прямую задачу можно интерпретировать

прямая на max прибыль. , при выпуске х1 х2 х3 , а двойственную min -> расходов на ресурсы.

1) b – сырье ; у1 у2 – оценка ресурсов.

Правило построения двойственных задач к общей З.Л.П.

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

задаче.

2. Количество ограничений двойственной задачи равно числу переменных в прямой задачи.

3. Вектор свободных элементов прямой задачи b является вектором коэффициентов

двойственной задачи.

4. Вектор коэффициентов функции цели C=(C1…Cn) прямой задачи служит вектором

свободных членов системы ограничений двойственной задачи.

5. Если прямой Z->max то в Д.З. W->min/

6. Каждому ограничению – неравенству ai1x1+a12x2+..+ainxm , i=1,m Соответствует

неотрицательная переменная yi>=0 ; i=1,m Д.З.

7. Каждой неотрицательной переменной (xj>=0) j=1,n прямой задачи соответствует

ограничения неравенства Д.З. a1jy1+a2jy2+…+amjym>=Cj (j=1,n)

8. Матрица системы ограничений Д.З. служит транспонированная матрица прямой задачи.

9. Каждом ограничению равенству прямой задачи ai1x1+ai2x2+…+ainxn=bi (i=1,m)

соответствует свободная переменная yi><0

10. Каждой свободной переменной xj><0 (j=1,n) соответствует ограничение равенства a1j+a2j+

…+amjym=Cj

ТЕОРЕМА ДВОЙСТВЕННОСТИ.

1. Если прямая и двойственная задача имеют допустимые решения Х и У , то они имеют

оптимальное решение Х

и У

и причем значение функции в этих точках совпадают.

Zmax=Wmin CX

Лемма №1

Для любых двух допустимых решений Х и У пары Д.З. справедливо СХ<=Уb

Док-во:

Z=CX->max W=yb->min

Ax<=b YA>=C

x>=0 y>=0

Допустим что X

– любое допустимое решение П.З. , а Y

– для Д.З.

Тогда Х

удовлетворяет системе ограничений , т.е. АХ

<=b ¦ y

>=0 Y

A>=C¦x

>=0

Первое ограничение умножим на y

<=y

>=Cx

<=T<=y

b => Cx

<=y

Лемма № 2

Если для допустимых решений X

и У

, выполняется условие равенства СХ

=У

b , то Х

и У

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

Док-во : Дана пара Д.З. Х

и У

допустимые решения. СХ

=У

b , док-ть Х

и У

оптим. решение

Предположим что Х- ОДР (любое) , тогда по первой лемме СХ<=У

b , но У

b=Cx

=> Cx=Cx

отсюда следует , что Х

т. максимума => у

т. минимума.

На основании графического анализа Д.З. исследовать разрешимость данной задачи в случаи

разрешимости – найти экстремальные значение целевой функции.

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. Y*(Ax*-b)=0 (тогда оптимальное решение)

2. (У*А-С)Х*=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

Свойства двойственных оценок.

В экономике вектор у, называется вектором двойственных оценок или «теневыми ценами».

Двойственные оценки сырья и т.д.

Свойства:

1) y*i – является покупателем дефицитности i-го ресурса (i=1,m) Оценка не дефицитного

ресурса –0 (y*=0) , если





j 1

аijxj<bi Чем выше yi (оценка ресурса), тем ресурс дефицитнее.

2) Y*i=dzmax/dbi y*i=lim ▲Zmax/▲bi (bi->0) => y*i≈▲Zmax/▲bi => Zmax=y*i*▲bi

3) Вектор y*i – является показателем необходимости введения в производство j- технологии

Х*j(





i 1

aijy*i-Cj)=0 , если





i 1

aijy*i>Cj, то выгодно (Cj- цена ед. продукции) =>Х*j=0 ,

то не надо выпускать продукцию Х*j>0 , то затраты совпадают с доходами .

4) Вектор У является показателем сопоставимости затрат на ресурсы (у*1b1+y*2b2..) со

стоимостью продукции.

ТРАНСПОРТНАЯ ЗАДАЧА.

Дадим постановку транспортной задачи в общем виде.

Пусть имеется 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 =a1

x21+x22+…+x2n =a2 m

2) xm1+xm2+…+xmn = am

x11+ x21 +xm1 = b1

x12+ x22+ xm2 = b2 n

x1n+ x2n+ +xmn=bn

1) Z=C11X11+C12X12+…+CmnXmn->min

Бывают задачи типа закрытого и открытого.

А) предположим что спрос >предложения , т.е. сумма ai< суммы bj . Тогда что бы перейти к

закрытой задачи вводят фиктивного производителя мощность которого равно am+1=



bj



а в транспортно таблице вводится новая строка m+1 в которой am+1=



bj



,а затраты = 0 (Cm+1,j=0)

Б) Если



, т.е. предложение выше чем спрос. Вводят фиктивного потребителя

bn+1=



, а в таблице добавляем фиктивный столбец с затратами =0

Очевидно что Т.З. является Л.П., то можно решить симплекс методом., но таблица которая

будет состоять к примеру из 100 столбцов – считать не удобно , то используют такие методы как

: распределительный метод, метод дифференциальных рент, метод потенциалов.

Особенности Т.З.

1) Все ограничения равенства ( в закрытой)

2) Все переменные входят в систему ограничений, входят в систему либо 0 или 1

3) Каждая переменная входит в С.О. только два раза.

4) Теорема о существовании решения.

Т.З. всегда имеет оптимальное решение если сумма ai= сумме bj.

Док-во: Z=



 

j1 1

CijXij->min





xij

=ai (i=1,m)





xij

=bj (j=1,n) Xij>=0

Очевидно что решением будет Хij = aibj/



=aibj/



Просуммируем по i:





xij





i 1

aibj/





i 1

ai = bj





i 1

ai/





i 1

ai = bj

Про суммируем по j :





xij

= ai Xij=min(ai;bj)

ТЕОРЕМА О РАНГЕ МАТРИЦЫ.

Ранг матрицы системы ограничений = m+n-1

х11+х12+…+х1n =a1

x21+x22+…+x2n =a2 m

2) xm1+xm2+…+xmn = am

x11+ x21 +xm1 = b1

x12+ x22+ xm2 = b2 n

x1n+ x2n+ +xmn=bn

Докажем что ранг матрицы (А)<m+n

А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

Докажем что ранг = m+n-1

Ранг – наивысший порядок минора отличный от 0.

1) Построим матрицу А из (1 и 0) размерность m*n , найдем минор нужного порядка n-1

вычеркиваем одну из строк. Минор будет равен 1, отличен от 0.

Из этого следует что число базисных неизвестных в Т.З. = m+n-1 , а остальные переменные

будут свободными. Ч.Т.Д.

Матрица Х=¦Хij¦ , называется допустимым решением Т.З. или допустимым планом , если она

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

называется оптимальным , если Z при этом плане принимает свое минимальное значение.

Этапы решения Т.З.

1) Находят первоначальный опорный план , либо методом северо-западного угла , либо

методом минимального элемента.

2) Согласно т. о потенциальности плана (оптимальности плана) проверяют полученный план

на оптимальность если он оптимален , то записывают ответ X* и Zmin=

3) Если полученный план не оптимален переходят к новому опорному плану.

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

1) северо-западного угла.

Х11=min(ai;bj) Клетка становится занятой – базисной. Если удовлетворен покупатель то столбец

закрывается, если все со склада вывезли то закрывается строка. И.т.д.

Если баланс по строкам и столбцам выполняется и число клеток (занятых) совпадает с рангом

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

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

минимального элемента.

Если в середине таблицы одновременно закрывается строка и столбец , а число занятых клеток

не равно рангу, то в следующую клетку ставят 0 базисный и клетка считается занятой ->

выражденной решение.

Переход от одного опорного плана к другому.

Необходимо перейти к другому опорному решению, т.е. одну из базисных переменных сделать

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

используют замкнутую ломаную линию. Цикл 0 замкнутая ломаная линия вершины которой

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

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

самопересекающимися , при чем т. пересечения не является вершиной.

Цикл пересчета - называется цикл, одна вершина которого лежит в свободной клетке , а

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

пересчета. λ>=0 λmin(xij) – i,j нечетные клетки цикла пересчета. Если в цикле пересчета в

нескольких клетках разность будет равно 0 , то пишут базисный 0.

Проверка плана на оптимальность.

Теорема об оптимальности плана или теорема о потенциальности плана.

Для док-ва составим двойственную к прямой задаче.



 

j1 1

Cijxij->min