1. Предмет и задачи матпро. Постановка общей задачи мп. Матпро



страница1/4
Дата30.10.2016
Размер0.59 Mb.
  1   2   3   4

1. Предмет и задачи матпро. Постановка общей задачи МП. Матпро – это раздел матем-ки, в кот-ой разраб-ся числовые м-ды решения многомерных задач с ограничениями. Чтобы решить задачу матем. м-дами необходимо составить модель. Мат.модель – это с-ма матем. выражений, которая описывает хар-ки изучаемого объекта и взаимосвязи м/у ними. Матпро включает: ленейное пргр-е, динамическое прогр-е, целочисленное прогр-е, дробнолинейное прогр-е и т.д. Постановкой общей задачи МП: определить значение неизв-ых х1,х2,…хn, при которых выпол-ся ограничения gi(x1,x2,….xn) (<=,=, >=) bi(i=1,m)(1) и доставляется экстремум функции Z=f(x1,x2,…xn) –extr-(2) целевая функция или функция цели. Значение переменных (х1,х2,…хn) наз-ся решением задачи или планом. План удовлетворяющий ограничениям (1) наз-ся допустимым. Допустимый план, при котором значения достигают экстремума наз-ся оптимальным. Задачи МП: определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т.д.

Экономические примеры задач, решаемых методами МП. Компания имеет 2 склада и 3 оптовых покупателей. Запасы на складах составляют 120 и 180 тыс.ед., а потребность покупателей 70,140,90тыс.ед. Стоимость транспортировки 1тысячи продукции приведена в матрице. Определить план при транспортировки, при котором суммарные затраты минимальные. А1, А2 –склад, В1,В2,В3 –потребители. Обозначим ч/з хij-количество продукции, перевозимое со склада Аi(i=1,2) потребителю Bj(j=1,3). Затраты на транспортировку могут быть описаны функцией. f=8x11+5x12+6x13+4x21+9x22+7x23 –min

{x11+x12+x13=120

{x21+x22+x23=180
{x11+x21=7 xiJ>=0 (i=1,2) (j=1,3)

{x12+x2=140

{x13+x23=90

Предприятие может производить 2 вида продукции(П1,П2), используя для этого 3вида ресурсов сырье, оборудование и труд.



ресурс

Росход ресурсов на ед.прод.

Кол-во ресурсов

П1

П2

Сырье,кг

1

3

210

Фонд времени работы оборудования ст/час

3

2

210

Труд, чел/час

3

1

180

Прибыль от реализации ед.прод.

35

49




Определить оптим. план выпуска продукции. Обозначим х1,х2 количество продукции П1 и П2 в оптимальном плане. Прибыль опишется функцией: f= 35x1+49x2 – max

1x1+3x2<=210}

3x1+2x2<=210}

3x1+x2<=180 }

x1>=0,x2>=0


2. Различные формы записи ЗЛП (общая, каноническая, симметрическая)

Задачи МП: определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т.д.

Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Σcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n )(3) где cj,aij, bi-постоянные числа.



Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной.

min f(x) = -max(-f(x))

Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn,xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5.

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



3. Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП.

Пусть дана задача f=c1x1+c2x2-max (1)

a11x1+a12x2<=b1 }

am1x1+am2x2<=bm}

x1>=0, x2>=0 (3)

План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскастей. При пересечении могут получиться:

1)выпуклая многоугольная замкнутая область.

2) выпуклая открытая многоугольная область

3) единственная точка

4) пустое множество

5) луч и отрезок

Геометрическая интерпретация целевой функции: ф-ция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции.Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых рещений(ОДР).


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

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

1. Построить ОДЗ; 2. Построить вектор С; 3. Перпендикулярно С построить линию уровня f=0; 4. Перемещая линию уровня в градиентном направлении найти точку максимума или минимума ОДЗ; 5. Найти координаты точки максимума (минимума) и значение функции в этой точке. В ходе решения ЗЛП граф. способом могут получаться след. результаты:

1. Оптимальный план единственный: линия уровня и ОДЗ в крайнем положении имеют одну общую точку;

2. Оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через грань ОДЗ;

3. Задача не имеет решения: ОДЗ=ø;

4. Целевая функция не ограничена, в этом случаи добавляется еще одно ограничение.
Граф.способом можно решать задачи с большим чем 2 количественных переменных. Если в канонической форме задачи разность м/у количеством линейно-независимых уравнений (r ) и количеством переменных n ровна 2. Для решения такой задачи: 1. преобразуют модель к симметрической форме, в результате получается задача ЗЛП с двумя независимыми; 2. решить ЗЛП граф.способом; 3. координаты точки экстремума подставить в уравнение канонич.записи и найти значение остальных переменных.


5. Опорные планы ЗЛП. Соответствие между опорными планами и вершинами многогранника планов.

Рассмотрим задачу:

F=c1x1+c2x2+cnxn-max (1)

a11x1+…a1nxn<=b1 }

am1x1+…+amnxn<=bm } (2)

xj>=0, ( j=1,n) (3)

Чтобы задача 1-3 имела решение (2) должна быть совместной и иметь неотрицательное решение. Это возможно если число линейно-независимых уравнений с-мы ( r ) не больше числа переменных (r<=n). При r=n –с-ма имеет единст. решение; r

Хi=Bi0-(n-m;J=1)ΣBij*Xj+m ( i=1,m ) (4)

Подставим Xi в целевую функцию, получим

F= Boo-(n-m; j=1)ΣBoj*Xj+m (5)

Базисное решение получается путем подстановки вместо переменных Xj+m (j=1,n-m) нулей. Переменные, которые стоят в правой части (4) наз-ся свободными. Если в базисном решении значение всех базисных переменных неотрицательное, решение наз-ся опорным. Каждому опорному плану (1-3) соответствует вершина многогранника плана и наоборот, каждой вершине многогранника плана соотвтствует опорный план задачи 1-3. Опорных планов задачи 1-3 не более, чем число сочетаний из m по n , поэтому выбирая все опорные планы можно определить тот, для которого целевая функция принимает экстремальные значения.
6. Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.

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



БП

1

СП

-Xm+1 -Xm+2 -Xn



х1

b1o

b11 b12 b1n-m

х2

b2o

b21 b22 b2n-m

хm

bm

bm1 bm2 bmn-m

f

boo

bo1 bo2 bon-m




7. Симплексный метод решения ЗЛП. Общая идея симплекс-метода.

Одним из универсальных методов явл-ся симплесный метод. В симплексном м-де осущ-ся направленный перебор опорных планов, в том смысле, что при переходе от одного опорного плана к другому целевая функция возрастает. Пусть задача записана в канонической форме:

f=(n; j=1)ΣCj*Xj (max)

(n;j=1)Σaij*xj=aio (i=1,m)

Xj>=0 (j=1,n)

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



Общая идея симпл.метода состоит в том что симпл. м-д разбивается на 2 этапа:

1. нахождение начального опорного плана;

2. последовательное улучшение вплоть до нахождения оптимального, в котором целевая функция достигает максим.значения.
8. Признак оптимальности опорного плана ЗЛП.

Признак опорного плана явл-ся неотрицательность элементов столбца свободных членов, не считая элементов f-строки. Признаком оптимального плана - если в симплексной таблице содержится опорный план, все элементы f-строки, которые неотрицательны (не считая свободного члена bоо), то этот опорный план является оптимальным. Если в соотношении f=boo-(n-m;j=1)Σboj*Xj+m значение всех свободных переменных равно нулю, то целевая функция будет равна свободному члену f(векторXo)=boo. При увеличении значений свободных переменных функция начнет умен-ся, следовательно при плане Хо функция принимает экстремальное значение.





9. Нахождение начального опорного плана ЗЛП.

Для нахождения начального опорного плана можно предложить следующий алгоритм:

1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.

2.





1

-x1 ….. -xn

0=

a1o

a11 …. a1n

…..

…..

………………………..

0=

amo

am1 ….. amn

f=

0

-c1 …. -cn

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


10. Нахождение оптимального опорного плана ЗЛП.

Начальный опорный план Хо исследуется на оптимальность.

Если в f-строке нет отрицательных элементов (не считая свободного члена), -план оптимален. Если в f- строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f- строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи.
11. Признак неограниченности целевой функции на множестве планов и геометрическая иллюстрация.

Признаком неограниченности целевой функции является получение в процессе поиска оптимал-го плана столбца с отрицательном элементом в f-строке, не содержащего ни одного положит. элемента.



12. Признак бесконечности множества оптимальных планов и геометрическая иллюстрация.

Признаком бесконечности множ-ва планов явл-ся наличие в f-строке симплексной т-це, содержащей оптимал.план, хотя бы одного нулевого элем-та не считая свободного члена. Пусть найден оптим.план Х1*, при чем в f-строке один нулевой элемент. Другой оптим.план Х2* можно найти, выбрав в качестве разреш-го столбец с нулевым элементом в f-строке. Остальные оптим. планы можно определить как линейную комбинацию:

Х1*= λХ1*+(1-λ)Х2* 0=<λ<=λ
13. Признак неразрешимости ЗЛП и геометрическая иллюстрация.

При нахождении базисного решения начальный опорный план может не выделиться. В этом случаи необходимо построить начальный опорный план по след. правилам:

1. записать с-му уравнений канонич. Формы задачи в виде 0-равенств. Свободные члены должны быть неотрицательными.

2. записать полученную с-му в симплексную таблицу.

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





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

1. привести модель задачи к канонической форме;

2. найти начальный опорный план;

3. записать задачу в симпл. таблицу;

4. если содержащейся в таблице план явл-ся оптимальным выписывается ответ. Если нет, то выполняется следующий пункт;

5. прперейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулю отрицательному элементу f-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т.е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.:

bij bis bkj=(bkj*bis-bij*bks)/bi

bkj bks



15. Понятие двойственности в ЛП. Симметричные двойственные задачи и их экономическая интерпретация.

К любой задаче ЛП можно построить др задачу, тесно связ с усл-еи исходной задачи. При чем решая одну из них автом-ки получаем реш-е для др задачи. За исх задачу можно принимать любую из 2ух. Она наз прямой, а 2ая – двойственной.

Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij.Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость

f= c1x1+…+cnxn (1)

При этом расход ресурсов не должен превышать их наличия:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Все известные по своему экономическому смыслу неотрицательны:

Xj>=0 (j=1,n). (3)

Заметим, что это задача образуют симметричную двойственную задачу.


16. Несимметричные двойственные задачи. Связь между элементами моделей задач двойственной пары. Соответствие между переменными двойственных задач.

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1) Σcj*xj (n;j=1) Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

В пару взаимнодвойственных симметричных задач

f=(n;A=1) Σcj*xj – max P= (m;i=1)Σbi*xi – min

(n;j=1)Σaij*xj<=bj i=1,m (m;i=1) Σaij*yi>=cj j=1,n

Xj>=0, j=1,n yi>=0 i=1,m

Вводим дополнительные переменные и приводим их к каноническому виду:

f=(n;j=1)Σ- max P= (m;i=1)Σbi*xi –min

(n;j=1)Σaij*xj+xn+1=bi i=1,m (m;i=1)Σaij*yi-ym+y=cj j=1,n

Xj>=0 j=1,n yi>=0, i=1,m

Xn+1>=0 i=1,m ym+j>=0 j=1,n

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

Х1 X2 … Xn Xn+1 Xn+2 … Xn+m

Уm+1 Ym+2 … Ym+n Y1 Y2 … Yn

Это соответствие можно сформировать словесно: основным переменным исходной задачи ставятся дополнительные переменные двойственной задачи, а дополнительным переменным исходной ставятся в соответствие основные двойственные.


Каталог: ld
ld -> Информация относительно прав пожилых людей
ld -> «Великая Отечественная война» Воспитательная. Воспитание патриотизма, нравственное воспитание на примерах героев войны
ld -> В русском бардовском творчестве
ld -> 4. предприятия и заводы оборонной промышленности
ld -> Информация о Сибае (Республика Башкортостан)
ld -> Внутренний предиктор СССР
ld -> [26/01/2009] Атомная энергетика для подводного флота
ld -> 1. Средства измерения, их характеристика, разновидности, области применени
ld -> Отчет о деятельности Федерального государственного учреждения науки
ld -> Научная подготовка, степень и звание: Доцент по специальности 07. 00. 07 – «Этнография, этнология и антропология»


Поделитесь с Вашими друзьями:
  1   2   3   4


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал