Войти на сайт

Забыли пароль?
Регистрация

Навигация

Главная Рефераты Информатика, программирование

Представление пространства решений стандартной задачи ЛП

Линейное программирование
Ограничения на допустимое множество Графическое решение задачи ЛП Представление пространства решений стандартной задачи ЛП Искусственное начальное решение Двухэтапный метод Двойственность
20533
знака
10
таблиц
1
изображение
Скачать работу
Похожие
Заказать работу
Графическое решение задачи ЛП Читать далее: Искусственное начальное решение

4.2.1. Представление пространства решений стандартной задачи ЛП.

Модель:

максимизировать целевую функцию

$z=3x_{E}+2x_{I}+0s+0s_{2}+0s_{3}+0s_{4}$

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

\begin{displaymath}\begin{array}{c}\begin{array}{ccccccccccccc}x_{E} & + & ......array}\\x_{E},x_{I},s_{1},s_{2},s_{3},s_{4}\geq 0\end{array}\end{displaymath}

На – пространство решений. Каждую точку можно определить с помощью

$x_{E},x_{I},s_{1},s_{2},s_{3},s_{4}$

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

Анализируя , заметим, что

$x_{E},x_{I},s_{1},s_{2},s_{3},s_{4}$

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

Экстр.

 переменные
точка нулевые ненулевые
A

$x_{E},x_{I}$

$s_{1},s_{2},s_{3},s_{4}$
B

$s_{2},x_{I}$

$s_{1},x_{E},s_{3},s_{4}$
C

$s_{2},s_{1}$

$x_{I},x_{E},s_{3},s_{4}$
D

$s_{4},s_{1}$

$x_{I},x_{E},s_{3},s_{2}$
E

$s_{4},s_{3}$

$x_{I},x_{E},s_{1},s_{2}$
F

$s_{3},x_{E}$

$x_{I},s_{4},s_{1},s_{2}$

Из таблицы выделим закономерности:

1.         Стандартная модель содержит четыре уравнения и шесть неизвестных, поэтому в каждой из экстремальных точек (6–4) переменные должны иметь нулевые значения.

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

Если линейная модель стандартной формы содержит $m$уравнений и  неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы $m$уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен x­E и s2 между небазисными и базисными переменными.

Включаемая переменная – небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации. Исключаемая переменная – базисная в данный момент переменная, которая на следующей итерации подлежит исключению из множества базисных переменных.

 

4.2.2 Вычислительные процедуры симплекс-метода

Симплекс-алгоритм:

Шаг 0: Используя линейную модель стандартной формы, определяют НДБР путём приравнивания к нулю n-m (небазисных) переменных.

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

Шаг 2: Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна стать небазисной при введении в состав базиса новой переменной.

Шаг 3: Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных. Переход к Шагу 1.

$\begin{array}{ccccccccccccccc}z & - & 3x_{E} & - & 2x_{I} & & & & & & & & & =...... s_{3} & & & = & 1\\& & & & x_{I} & & & & & & & + & s_{4} & = & 2\end{array}$

Если x­E=xI=0, то

$s_{1}=6,s_{2}=8,s_{3}=1,s_{4}=2$

(соответствует точке A Ha ) $\Rightarrow A$ – начальное допустимое решение.

$z$

$x_{E}$

$x_{I}$

$s_{1}$

$s_{2}$

$s_{3}$

$s_{4}$

 Решение

$z$

$1$

 -3 -2

$0$

$0$

$0$

$0$

$0$

$s_{1}$

$0$

$1$

 2

$1$

$0$

$0$

$0$

 6

$s_{2}$

$0$

 2

$1$

$0$

$1$

$0$

$0$

 8

$s_{3}$

$0$

 -1

$1$

$0$

$0$

$1$

$0$

$1$

$s_{4}$

$0$

$0$

$1$

$0$

$0$

$0$

$1$

 2

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

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

Отношение, идентифицирующее исключаемую переменную, можно определить из симплекс-таблице. Для этого в столбце вводимой переменной вычёркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных из правых частей ограничений к оставшимся элементам столбца. Исключаемая переменная – та, для которой это отношение минимально.

$z$

$x_{E}$

$x_{I}$

$s_{1}$

$s_{2}$

$s_{3}$

$s_{4}$

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

$z$

$1$

 -3 -2

$0$

$0$

$0$

$0$

$0$

 -

$s_{1}$

$0$

$1$

 2

$1$

$0$

$0$

$0$

 6

$\frac{6}{1}$

$s_{2}$

$0$

 2

$1$

$0$

$1$

$0$

$0$

 8

$\frac{8}{1}$

$s_{3}$

$0$

 -1

$1$

$0$

$0$

$1$

$0$

$1$

 -

$s_{4}$

$0$

$0$

$1$

$0$

$0$

$0$

$1$

 2 -

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

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

Тип 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$-уравнении имеет наибольший положительный коэффициент. Условия допустимости в обоих случаях одинаковы.



Графическое решение задачи ЛП Читать далее: Искусственное начальное решение
Информация о работе «Линейное программирование»
Раздел: Информатика, программирование
Количество знаков с пробелами: 20533
Количество таблиц: 10
Количество изображений: 1
Скачать

Похожие работы

Решение транспортной задачи линейного программирования в среде MS Excel
Скачать
62893
11
17

... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...

O Л. В. Канторовиче и линейном программировании
Скачать
58662
0
0

... среди математиков, его разделяли А.Н.Колмогоров, И.М.Гельфанд, В.И.Арнольд, С.П.Новиков и др. Нельзя не восхищаться естественностью и внутренней стройностью математической работ Л.В. по двойственности линейного программирования и их экономической интерпретацией. 2. О математической экономике как области математики и о некоторых ее связях А) Связи линейного программирования с функциональным и ...

Решение оптимизационной задачи линейного программирования
Скачать
59893
13
0

... решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5).   СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995. 2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного ...

Линейное программирование: решение задач графическим способом
Скачать
32158
4
0

... области (если допустимая область ограничена и не пуста); 3.   ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи. Гл 2 Решение задач линейного программирования графическим способом на ЭВМ 2.1 Описание работы программы Программа написана с использованием собственных функций и процедур и трех стандартных модулей System, Crt и ...

0 комментариев

Разделы
Главная Новости Рефераты Статьи Вузы
Инфо
О проекте Соглашение
Следите за новостями
VK
© 2009-2025 Образовательная социальная сеть KazEdu.com

Наверх