скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыРеферат: Линейное программирование

Столбец, ассоциированный с вводимой переменной – ведущий столбец; строка, соответствующая исключаемой переменной – ведущая строка; на их пересечении – ведущий элемент.

Поиск нового базисного решения осуществляется методом исключения переменных (метод Жордана-Гаусса). Этот процесс включает в себя вычислительные процедуры двух типов.

Тип 1. Формирование ведущего уравнения

Новая ведущая строка = предыдущая ведущая строка/ведущий элемент

Тип 2. Формирование остальных уравнений

Новое уравнение = предыдущее уравнение – (коэффициент ведущего столбца предыдущего уравнения)*(новая ведущая строка)

Новая симплекс-таблица, полученная после проведения рассмотренных операций:

$z$

$x_{E}$

$x_{I}$

$s_{1}$

$s_{2}$

$s_{3}$

$s_{4}$

 Решение Отношение

$z$

$1$

$0$

$-\frac{1}{2}$

$0$

$-\frac{3}{2}$

$0$

$0$

$12$

 -

$s_{1}$

$0$

$0$

$\frac{3}{2}$

$1$

$-\frac{1}{2}$

$0$

$0$

$2$

$\frac{4}{3}$

$x_{E}$

$0$

$1$

$\frac{1}{2}$

$0$

$\frac{1}{2}$

$0$

$0$

$4$

$\frac{8}{1}$

$s_{3}$

$0$

$0$

$\frac{3}{2}$

$0$

$\frac{1}{2}$

$1$

$0$

$5$

$\frac{10}{3}$

$s_{4}$

$0$

$0$

$1$

$0$

$0$

$0$

$1$

$2$

$2$

$z$

$1$

$0$

$0$

$\frac{1}{3}$

$\frac{1}{3}$

$0$

$0$

$1$

 -

$x_{I}$

$0$

$0$

$1$

$\frac{2}{3}$

$-\frac{7}{3}$

$0$

$0$

$1$

 -

$x_{E}$

$0$

$1$

$0$

$-\frac{1}{3}$

$\frac{2}{3}$

$0$

$0$

$3$

 -

$s_{3}$

$0$

$0$

$0$

$-1$

$1$

$1$

$0$

$0$

 -

$s_{4}$

$0$

$0$

$0$

$-\frac{2}{3}$

$\frac{1}{3}$

$0$

$1$

$\frac{3}{5}$

 -

xI – вводимая переменная (т.к. коэффициент в $z$-уравнении -1/2). Исключаемая переменная s1, (отношение 4/3 – минимальное). Снова проведём вычисления двух типов. Последняя симплекс-таблица соответствует оптимальному решению задачи, т.к. в $z$-уравнении ни одна из небазисных переменных не фигурирует с отрицательными коэффициентами.

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


4.2.3. Искусственное начальное решение

Для получения начального базисного решения мы использовали остаточные переменные. Однако когда исходное ограничение записано в виде равенства или имеет знак, нельзя сразу же получить НДБР. Поэтому были разработаны два метода, в которых используется «штрафование» искусственных переменных.

1.         Метод больших штрафов (М-метод)

Рассмотрим линейную модель, приведённую к стандартной форме:

минимизировать

$z=4x_{1}+x_{2}$

при ограничениях

$\begin{array}{c}\begin{array}{c}3x_{1}+x_{2}=3\\4x_{1}+3x_{2}-x_{3}=6\\x_{1}+2x_{2}+x_{4}=4\\x_{1},x_{2},x_{3},x_{4}\ge 0\end{array}\end{array}$

В первом и втором уравнениях нет переменных, исполняющих роль остаточных. Поэтому введём в каждое из этих уравнений по одной из искусственных переменных R1 и R2: $\begin{array}{c}3x_{1}+x_{2}+R_{1}=3\\4x_{1}+3x_{2}-x_{3}+R_{2}=6\end{array}$

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

минимизировать

$z=4x_{1}+x_{2}+MR_{1}+MR_{2}$

при ограничениях

$\begin{array}{c}\begin{array}{c}3x_{1}+x_{2}+R_{1}=3\\4x_{1}+3x_{2}-x_{3......_{2}+x_{4}=4\\x_{1},x_{2},x_{3},x_{4},R_{1},R_{2}\ge 0\end{array}\end{array}$

Теперь если

$x_{1}=x_{2}=x_{3}=0$

,то начальное допустимое решение:

Метод оптимизации, направленный на нахождение минимального значения $z$, приведёт к тому, что переменные R1 и R2 в оптимальном решении обратятся в нуль.

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

$\begin{array}{c}R_{1}=3-3x_{1}-x_{2}\\R_{2}=6-4x_{1}-3x_{2}+x_{3}\end{array}$

получим выражение для $z$:

$z=4x_{1}+x_{2}+M(3-3x_{1}-x_{2})+M(6-4x_{1}-3x_{2}+x_{3})=(4-7M)x_{1}+(1-4M)x_{2}+Mx_{3}+9M$

Решение представлено в сводной таблице:

Итерация

$x_{1}$

$x_{2}$

$x_{3}$

$R_{1}$

$R_{2}$

$x_{4}$

 Решение Отношение

$z$

$-4+7M$

$-1+4M$

$-M$

$0$

$0$

$0$

$9M$

 -

$R_{1}$

$3$

$1$

$0$

$1$

$0$

$0$

$3$

$1$

$R_{2}$

$4$

$3$

$-1$

$0$

$1$

$0$

$6$

$\frac{3}{2}$

$x_{4}$

$1$

$2$

$0$

$0$

$0$

$1$

$4$

$4$

$z$

$0$

$5M$

$-M$

$\frac{4-7M}{3}$

$0$

$0$

$4+2M$

 -

$x_{1}$

$1$

$\frac{1}{3}$

$0$

$\frac{1}{3}$

$0$

$0$

$1$

$3$

$R_{2}$

$0$

$\frac{5}{3}$

$-1$

$-\frac{4}{3}$

$1$

$0$

$2$

$\frac{6}{5}$

$x_{4}$

$0$

$\frac{5}{3}$

$0$

$-\frac{1}{3}$

$0$

$1$

$3$

$\frac{9}{5}$

$z$

$0$

$0$

$\frac{1}{5}$

$\frac{8}{5}-M$

$-M-\frac{1}{5}$

$0$

$\frac{18}{5}$

 -

$x_{1}$

$1$

$0$

$\frac{1}{5}$

$\frac{3}{5}$

$-\frac{1}{5}$

$0$

$\frac{3}{5}$

$3$

$x_{2}$

$0$

$1$

$-\frac{3}{5}$

$-\frac{4}{5}$

$\frac{3}{5}$

$0$

$\frac{6}{5}$

 -

$x_{4}$

$0$

$0$

$1$

$1$

$-1$

$1$

$1$

$1$

$z$

$0$

$0$

$0$

$\frac{7}{5}-M$

$-M$

$-\frac{1}{5}$

$\frac{17}{5}$

 -

$x_{1}$

$1$

$0$

$0$

$\frac{2}{5}$

$0$

$-\frac{1}{5}$

$\frac{2}{5}$

 -

$x_{2}$

$0$

$1$

$0$

$-\frac{1}{5}$

$0$

$\frac{3}{5}$

$\frac{9}{5}$

 -

$x_{3}$

$0$

$0$

$1$

$1$

$-1$

$1$

$\frac{3}{5}$

 -

Страницы: 1, 2, 3, 4

Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

Обратная связь

Поиск
Обратная связь
Реклама и размещение статей на сайте
© 2010.