Двоистый симплекс-метод

Размещено на http://www.allbest.ru/

Двоистый симплекс-метод

План

Двоистый симплекс-метод

Методы отсекающих плоскостей в задачах целочисленного линейного программирования

Список использованной литературы

Двоистый симплекс-метод

Симплекс метод - универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала.

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

Ограничения вида «Ј»- ресурсные ограничения. Справа находится то что мы используем на производстве, слева - то что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0».

Ограничения вида «=». Часто бывает, что несмотря на то что ограничения имеют вид равенства, единичный базис не выделяется или трудно выделяется. В этом случае вводятся искусственные переменные для создания единичного базиса - Yi. В систему ограничений они входят с коэффициентом «1» , а в целевую функцию с коэффициентом «M», стремящимся к бесконечности (при Fmin - «+M», при Fmax - «-M»).

Ограничения вида «і» - Плановые ограничения. Дополнительные переменные (X), несущие определенный экономический смысл - перерасход ресурсов или перевыполнение плана, перепроизводство, добавляются с коэффициентом «-1», в целевую функцию - с коэффициентом «0». А искусственные переменные (Y) как в предыдущем случае.

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

Пусть система приведена к каноническому виду.

X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1

……………………………………………………….

Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm

В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных.

Fmin= C1X1+ C2X2+ C3X3+....+ CnXn

Все hi должны быть больше либо равны нулю, где i=1,2...m. На первом шаге в качестве допустимого решения принимаем все Xj=0 (j=m+1,m+2,...,m+k). При этом все базисные переменные Xi=Hi.

Основное поле симплекс метода - система коэффициентов из уравнения.

Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет».

Для первой итерации

F0= е--ci*hi.

D1,--D2,--D3,...,--Dm - оценки они рассчитываются по формуле:

D--j = е ciqij-cj.

Индексная строка позволяет нам судить об оптимальности плана:

При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки.

При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки.

Переход ко второй итерации:

Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку.

Ключевым столбцом является тот, в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax.

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

На пересечении строки и столбца находится разрешающий элемент.

На этом этапе осуществляется к переходу к последующим итерациям.

Переход к итерациям:

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

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

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

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

Остальные элементы переносятся по формуле:

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

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

Построение искусственного базиса и оптимизация функции суммы искусственных переменных, т.е. F0=Y1+Y2+…+Yn = 0 (F®min). Если при этом F0=0, то искусственный базис мы вывели из состава переменных, переходим ко второй фазе - решаем задачу по первой симплекс таблице с действительными переменными. Если же F0№0, т.е. искусственный базис не выведен из состава переменных - ОЗЛП решений не имеет.

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

Замечания:

При решении задач на max с искусственным базисом следует переходить к решению на min, меняя лишь только целевую функцию:

Fmax = - Fmin.

При решении ОЗЛП с искусственным базисом особое внимание следует обратить на вычисление элементов индексных строк.

a) Для столбцов X вычисление элементов идет по формулам:

D--j = е qij.

е yi = y1+y2+…+yR.

еHi=F0.

Примечание: только для строк Y.

б) Для столбцов Y работает старая формула:

D--j = е ciqij-cj.

2. Методы отсекающих плоскостей в задачах целочисленного линейного программирования

симплекс метод программирование базис

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

Здесь (1) называется системой ограничений , ее матрица имеет ранг r n, (2) - функцией цели (целевой функцией). Неотрицательное решение (х₁⁰, x₂⁰, ... , x_n⁰) системы (1) называется допустимым решением (планом) ЗЛП. Допустимое решение называется оптимальным, если оно обращает целевую функцию (2) в min или max (оптимум).

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

2) f+c_r+1x_r+1 + ... + c_sx_s + ... + c_nx_n = b₀ min

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

В системе (1`) неизвестные х<sub>1</sub>, х<sub>2</sub>, ... , х<sub>r</sub> называются базисными (каждое из них входит в одно и только одно уравнение с коэффициентом +1), остальные х<sub>r+1</sub>, ... , x<sub>n</sub> - свободными. Допустимое решение (1`) называется базисным (опорным планом), если все свободные неизвестные равны 0, а соответствующее ему значение целевой функции f(x₁⁰, ... , x_r⁰,0, ... ,0) называется базисным.

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

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

все ограничения - в виде уравнений;

все свободные члены неотрицательны, т.е. b_i 0;

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

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

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

все члены перенесены влево, кроме свободного члена b₀;

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

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

1 0 ... 0 ... 0 a_1,r+1 ... a_1s ... a_1n b₁

0 1 ... 0 ... 0 a_2,r+1 ... a_2s ... a_2n b₂

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

0 0 ... 1 ... 0 a_i,r+1 ... a_is ... a_in b_i

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

0 0 ... 0 ... 1 a_r,r+1 ... a_rs ... a_rn b_r

0 0 ... 0 ... 0 c_r+1 ... c_s ... c_n b₀

Заметим, что каждому базису (системе базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение х = (b₁,b₂, ... ,b_r, 0, ... ,0) и базисное значение целевой функции f(b₁,b₂, ... ,b_r, 0, ... ,0) = b₀

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

т.е. с_j 0 (j = r+1, n) => min f (b₁, ... ,b₂,0, ... ,0) = b₀.

Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец (S-й), в котором последний элемент с_s > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. с_s > 0, a_is 0 ( i= 1,r ) => min f = -.

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

все элементы i-й строки делим на элемент a⁺_is;

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

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

a_kl` = a_kba_is - a_ila_ks = a_kl - a_ila_ks;

a_is a_is

b_k` = b<sub>k</sub>a<sub>is</sub> - b<sub>i</sub>a<sub>ks</sub>; c<sub>l</sub>` = c_la_is - c_sa_il

a_is a_is

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

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

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

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

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

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

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

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

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

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

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

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

Замечания

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

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

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

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

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

Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция f = c₁x₁ + c₂x₂ геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с₁,с₂).

Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают.

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

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

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

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

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

построить вектор n (с₁,с₂) по коэффициентам целевой функции f = c₁x₁ + c₂x₂;

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

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

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

Список использованной литературы

О.О. Замков, А.В. Толстопятенко, Р.Н. Черемных. Взвешенный метод наименьших квадратов Взвешенный метод наименьших квадратов Математические методы в экономике. - М.: Дис, 1997.

Анна Эрлих. Технический анализ товарных и финансовых рынков. - М.: ИНФРА, 1996.

Я.Б. Шор. Статистические методы анализа и контроля качества и надёжности. - М.: Советское радио, 1962.

4. В.С. Пугачёв. Теория вероятностей и математическая статистика. - М.: Наука, 1979. - 394с.

Размещено на Allbest.ru