Реферат: Математическое программирование

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

1. Общая задача линейногопрограммирования (ЗЛП):

<img src="/cache/referats/2738/image002.gif" v:shapes="_x0000_i1025">

Здесь(1)  называется системой ограничений, еематрица имеет ранг r<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">£

n, (2) — функцией цели(целевой функцией). Неотрицательное решение (х10, x20,…, xn0) системы (1) называетсядопустимым решением (планом) ЗЛП. Допустимое решение называется оптимальным,если оно обращает целевую функцию (2) вminилиmax (оптимум).

2. Симплексная форма ЗЛП. Длярешения ЗЛП симплекс — методом необходимо ее привести к определенной(симплексной) форме:

<img src="/cache/referats/2738/image004.gif" v:shapes="_x0000_i1026">(2`)   f+cr+1xr+1 +… + csxs +… + cnxn = b0<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">®

min

Здесьсчитаем  r < n(система имеетбесчисленное множество решений), случайr =nнеинтересен:в этом случае система имеет единственное решение и если оно допустимое, то автоматическистановится оптимальным.

Всистеме (1`) неизвестные  х1, х2,…, хr   называются базисными (каждое из них входит водно и только одно уравнение с коэффициентом +1), остальные хr+1,…, xn — свободными. Допустимоерешение (1`) называется базисным (опорным планом), если всесвободные неизвестные равны 0, а соответствующее ему значение целевойфункции  f(x10,…, xr0,0,… ,0)называется базисным.

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

а)система (1`) удовлетворяет условиям :

1) все ограничения — в видеуравнений;

2) все свободные членынеотрицательны, т.е. bi <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">³

0;

3) имеет базисные неизвестные;

б)целевая функция (2`) удовлетворяет условиям :

1) содержит только свободныенеизвестные;

2) все члены перенесены влево,кроме свободного члена b0;

3) обязательна минимизация(случай  max  сводится к min  по формуле   max f = — min(-f)).

3) Матричная формасимплекс-метода.Симплексной форме ЗЛП соответствует симплекс — матрица :

<img src="/cache/referats/2738/image005.gif" v:shapes="_x0000_s1027 _x0000_s1028 _x0000_s1029"><img src="/cache/referats/2738/image006.gif" v:shapes="_x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038">1     0… 0… 0     a1,r+1…a1s… a1n     b1

0     1… 0… 0     a2,r+1…a2s… a2n     b2

.................................................................

0     0… 1… 0     ai,r+1…ais… ain       bi

.................................................................

0     0… 0… 1     ar,r+1…ars… arn       br

0     0… 0… 0     cr+1   … cs  … cn        b0

Заметим,   что каждому  базису  (системе базисных  неизвестных ) соответствует   своя   симплекс- матрица,  базисное   решение         х = (b1,b2,… ,br, 0,… ,0)и базисное значение целевой функции   f(b1,b2,… ,br, 0,… ,0) = b0 (см.Последний столбец !).

Критерийоптимальности плана .Если в последней (целевой) строке симплекс-матрицы все элементынеположительны, без учета последнего b0, то соответствующий этойматрице план оптимален,

<img src="/cache/referats/2738/image007.gif" v:shapes="_x0000_s1039">т.е.     сj<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">£

0 (j = r+1, n) =>  min f (b1,… ,b2,0,… ,0) =  b0.

<img src="/cache/referats/2738/image008.gif" v:shapes="_x0000_s1040">Критерий отсутствияоптимальности.Если в симплекс-матрице имеется столбец (S-й), в котором последнийэлемент сs> 0, aвсе остальныеэлементы неположительны, то ЗЛП не имеет оптимального плана, т.е.  сs> 0, ais<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family: Symbol">£

0 (i=1,r) => min f = -<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-ansi-language:EN-US;mso-char-type:symbol;mso-symbol-font-family:Symbol">¥.

Еслив симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходитьк следующей матрице с помощью некоторого элемента ais> 0 иследующих преобразований (симплексных):

1)всеэлементы i-й строки делим на элемент a+is;

2) все элементы  S-го столбца, кроме ais=1, заменяем нулями;

3) все остальные элементыматрицы преобразуем по правилу прямоугольника, что схематично показано нафрагменте матрицы и дано в формулах:

<img src="/cache/referats/2738/image010.gif" v:shapes="_x0000_i1027">

akl` = akbais — ailaks  = akl — ailaks;

                  ais                        ais

bk` = bkais — biaks;             cl` = clais — csail

               ais                                           ais

Определение.  Элемент ais+ называется разрешающим, еслипреобразование матрицы с его помощью обеспечивает уменьшение (невозрастание)значения, целевой функции;строка и столбец, напересечении которых находится разрешающий элемент, также называются разрешающими.

Критерийвыбора разрешающего элемента.  Если элементais+ удовлетворяет условию

bi  = min bk

ais0                        aks0+

гдеs0 — номер выбранного разрешающего столбца, то онявляется разрешающим.

4. Алгоритм симплекс-метода (поминимизации).

1) систему ограничений ицелевую функцию ЗЛП приводим к симплексной форме;

2) составим симплекс-матрицу изкоэффициентов системы и целевой функции в симплексной форме;

3) проверка матрицы навыполнение критерия оптимальности;если он выполняется, торешение закончено;

4) при невыполнении критерияоптимальности проверяем выполнение критерия отсутствия оптимальности;вслучае выполнения последнего решение закончено — нет оптимального плана;

5) в случае невыполнения обоихкритериев находим разрешающий элемент для перехода к следующей матрице, длячего :

    а)выбираем разрешающий столбец по наибольшему из положи                                                        тельных элементов целевой строки;

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

6) c помощьюразрешающего элемента и симплекс-преобразований переходим к следующей матрице;

7) вновь полученнуюсимплекс-матрицу проверяем описанным выше способом (см. п. 3)

Через конечное число шагов, как правило получаемоптимальный план ЗЛП или его отсутствие

Замечания.

1) Если в разрешающей строке(столбце) имеется нуль, то в соответствующем ему столбце (строке) элементыостаются без изменения при симплекс-преобразованиях.

2) преобразования — вычисленияудобно начинать с целевой строки;если при этом окажется, чтовыполняется критерий оптимальности, то можно ограничиться вычислением элементовпоследнего столбца.

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

4) правильность полученногоответа — оптимального плана — проверяется путем подстановки значений базисныхнеизвестных в целевую функцию;ответы должны совпасть.

5.  Геометрическая интерпретация ЗЛП играфический метод решения (при двух неизвестных)

<img src="/cache/referats/2738/image011.gif" v:shapes="_x0000_s1026">Система ограничений ЗЛПгеометрически представляет собой многоугольник или многоугольную область какпересечение полуплоскостей — геометрических образов неравенств системы. Целеваяфункция  f = c1x1+ c2x2 геометрически изображает семейство параллельных прямых, перпендикулярныхвектору n(с1, с2).

<img src="/cache/referats/2738/image012.gif" v:shapes="_x0000_s1030">Теорема.    При перемещении прямой целевой функциинаправлении вектора nзначения целевой функции возрастают, в противоположномнаправлении — убывают.

Наэтих утверждениях основан графический метод решения ЗЛП.

6. Алгоритмграфического метода решенияЗЛП.

1)<span Times New Roman""> 

В системе координат построить прямые по уравнениям, соответствующимкаждому неравенству системы ограничений;

2)<span Times New Roman""> 

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

3)<span Times New Roman""> 

найти многоугольник (многоугольную область) решений системы ограниченийкак пересечение полуплоскостей;

4)<span Times New Roman""> 

<img src="/cache/referats/2738/image013.gif" v:shapes="_x0000_s1031">построить вектор n(с1, с2)по коэффициентам целевой функции  f = c1x1 + c2x2;

5)<span Times New Roman""> 

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

6)<span Times New Roman""> 

перемещать прямую целевойфункции параллельно самой себе по области решения, достигая max fпри движении вектора nи minfпри движениив противоположном направлении.

7)<span Times New Roman""> 

найти координаты точек max и minпочертежу и вычислить значения функции в этих точках (ответы).

7.Постановка транспортной задачи.

Приведемэкономическую формулировку транспортной задачи по критерию стоимости:

Однородныйгруз, имеющийся в mпунктах отправления (производства) А1, А2,..., Аmсоответственно в количествах а1, а2, ..., аmединиц,требуется доставить в каждый из nпунктов назначения(потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bnединиц.Стоимость перевозки (тариф) единицы продукта из Aiв Bjизвестна для всех маршрутовAiBjи равна Cij(i=1,m; j=1,n). Требуется составить такойплан перевозок, при котором весь груз  изпунктов отправления вывозиться и запросы всех пунктов потребленияудовлетворяются  (закрытая модель), асуммарные транспортные расходы минимальны.

Условиязадачи удобно располагать в таблицу, вписывая в клетки количество перевозимогогруза из Aiв Bj груза Xij>0, а в маленькиеклетки — соответствующие тарифы Cij:

<img src="/cache/referats/2738/image015.gif" v:shapes="_x0000_i1028">

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

Из предыдущей таблицы легко усматривается исоставляется математическая модель транспортной задачи для закрытой модели <img src="/cache/referats/2738/image017.gif" v:shapes="_x0000_i1029">

Число r = m + n — 1, равное рангу системы (1),называется рангом транспортной задачи. Если число заполненных клеток (Xij¹0) в таблице равно r, топлан называется невырожденным, а если это число меньше r, то план вырожденный — вэтом случае в некоторые клетки вписывается столько нулей (условно заполненныеклетки), чтобы общее число заполненных клеток было равно r.

Случай открытой модели <span Courier New"; mso-bidi-font-family:«Times New Roman»;background:aqua;mso-highlight:aqua">Σ

аi¹ <span Courier New"; mso-bidi-font-family:«Times New Roman»;background:aqua;mso-highlight:aqua">Σbj легко сводится к закрытой модели путемвведения фиктивного потребителя Bn+1c потребностью bn+1=<span Courier New"; mso-bidi-font-family:«Times New Roman»;background:aqua;mso-highlight:aqua">Σai-<span Courier New";mso-bidi-font-family:«Times New Roman»;background: aqua;mso-highlight:aqua">Σbj, либо — фиктивного поставщикаАm+1c запасомam+1=<span Courier New";mso-bidi-font-family:«Times New Roman»; background:aqua;mso-highlight:aqua">Σbj-<span Courier New"; mso-bidi-font-family:«Times New Roman»;background:aqua;mso-highlight:aqua">Σai; при этом тарифы фиктивных участников принимаютсяравными 0.

9. Способы составления1-таблицы (опорного плана).

I. <span Times New Roman""> 

Способ северо-западного угла(диагональный). Сущностьспособа заключается в том, что на каждом шаге заполняется левая верхняя клетка(северо-западная) оставшейся части таблицы, причем максимально возможнымчислом: либо полностью вывозиться груз из Аi, либо полностьюудовлетворяется потребность Bj.Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы aiи не удовлетворяются потребности bj. В заключение проверяют,что найденные компоненты плана Xijудовлетворяют горизонтальным и вертикальным уравнениям и что выполняетсяусловие невырожденности плана.

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

10. Метод потенциалов решениятранспортной задачи.

Определение:потенциалами решения называются числа ai®Ai, bj®Bj,удовлетворяющие условию ai+bj=Cij(*) для всех заполненных клеток (i,j).

Соотношения (*) определяют систему из m+n-1линейных уравнений с m+nнеизвестными, имеющуюбесчисленное множество решений; для ее определенности одному неизвестномупридают любое число (обычно a1=0), тогда все остальныенеизвестные определяются однозначно.

Критерий оптимальности.Если известны потенциалырешения X0транспортной задачи и для всех незаполненныхклеток выполняются условияai+bj£Ci j, то X0является оптимальным планом транспортной задачи.

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

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

1) одна клетка пустая, всеостальные занятые;

2) любые две соседние клеткинаходятся в одной строке или в одном столбце;

3) никакие 3 соседние клетки немогут быть в одной строке или в одном столбце .

Пустой клетке присваивают знак « + », остальным — поочередно знаки « — » и « + ».

Для перераспределения плана перевозок с помощьюцикла перерасчета сначала находят незаполненную клетку (r, s), вкоторой ar+bs>Crs,и строят соответствующий цикл; затем в минусовых клетках находят число X=min{Xij}.Далее составляют новую таблицупо следующему правилу:

1) в плюсовые клетки добавляем X;

2) из минусовых клеток отнимаемХ;

3) все остальные клетки внецикла остаются без изменения.

Получим новую таблицу, дающее новое решение X,такое, что f(X1)£f(X0); оно снова проверяется наоптимальность через конечное число шагов обязательно найдем оптимальный плантранспортной задачи, ибо он всегда существует.

11. Алгоритм метода потенциалов.

1) проверяем тип моделитранспортной задачи и в случае открытой модели сводим ее к закрытой;

2) находим опорный планперевозок путем составления 1-й таблицы одним из способов — северо-западногоугла или наименьшего тарифа;

3) проверяем план (таблицу) наудовлетворение системе уравнений и на невыражденность; в случае вырожденияплана добавляем условно заполненные клетки с помощью « 0 »;

4) проверяем опорный план наоптимальность, для чего:

а) составляем систему уравнений потенциалов позаполненным клеткам;

б) находим одно из ее решений при a1=0;

в) находим суммыai+bj=C¢ij(«косвенные тарифы») для всех пустых клеток;

г) сравниваем косвенные тарифы с истинными: есликосвенные тарифы не превосходят соответствующих истинных(C¢ij£Cij)во всех пустых клетках, то план оптимален (критерий оптимальности). Решениезакончено: ответ дается в виде плана перевозок последней таблицы и значения min f.

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

5) Для перехода к следующейтаблице (плану):

а) выбираем одну из пустых клеток, где косвенныйтариф больше истинного (C¢ij=ai+bj > Cij);

б) составляем цикл пересчета для этой клетки ирасставляем знаки « + », « — » в вершинах цикла путем их чередования,приписывая пустой клетке « + »;

в) находим число перерасчета по циклу: число X=min{Xij}, где Xij — числа в заполненныхклетках со знаком « — »;

г) составляем новую таблицу, добавляя Xвплюсовые клетки и отнимая Xиз минусовых клеток цикла

6) См. п. 3 и т.д.

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

еще рефераты
Еще работы по программированию, базе данных