Во всех случаях работы с симплекс-методом злп представляется в виде (5), (6)

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Рассмотрим те неизвестные в форме (5), которые имеют положительные коэффициенты. Пусть это будет Если все остальные свободные переменные равны нулю, и увеличивать только , то .

Увеличивать можно до тех пор, пока первая из базисных переменных не обратиться в нуль.В системе (6) имеем:

1.Если , то вызывает только лишь увеличение базисной переменной, и не нарушает условия неотрицательности.

2.При переменная не изменится.

3.Необходимо рассматривать только те базисные переменные , которые имеют .

Базисная переменная обратиться в нуль только при .

Составим отношения: . Выберем среди всех отношений наименьшее – i -тое:

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

Выведем переменную из свободных, а в их число введем .

Получимновый набор переменных:

Выразим новый набор базисных переменных через новые свободные. Из i -го уравнения выразим :

Выразим остальные базисные переменные через свободные. Для этого в выражение для подставим во все уравнения системы (6). Для l -го уравнения будем иметь:

Аналогично получаем новое выражение для минимизируемой формы F:

Получаем новое базисное решение:

Свободные переменные, равные 0:

Базисные переменные:

Целевая функция:

Полученное решение является допустимым, кроме того, значение F становится меньше. Подтвердим:

Для : все по условию, в соответствии с выбором, значит .

Для :

а) Если , то и , а

б) Если , то в силу условия выбора минимального отношения:

Коэффициент , поэтому для .

Значение F не увеличивается, а, если , то строго уменьшается.

Замечания:

1. Условие обеспечивает допустимость нового базисного решения.

2. Положительность гарантирует невозрастание линейной формы F.

3. Если , то при переходе к новому базисному решению значение F не изменится.

Решение ЗЛП с использованием симплекс- таблицы.

Свободные переменные

Базисные переменные , .

!!! Базисное решение должно быть допустимым.

Алгоритм решения

1. Для заданного набора коэффициентов в линейной форме (5) и в системе линейных ограничений (6) строится симплекс-таблица.

1. Выбрать генеральный элемент согласно правилам:

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

- Составить отношения ;

- Выбрать наименьшее среди этих отношений ;

- Вычислить - генеральный элемент и .

3. Величину λ заносим в правый нижний угол i -й строки и j -го столбца.

4. В нижние углы i -й строки записываем произведения .

5. В нижние углы j -го столбца записываем произведения .

6. Выделяем в i -той строке верхний угол, в j -м столбце – нижний.

7. Заполняем остальные клетки симплекс-таблицы. В нижний угол заносится произведение:

верхний угол i -той строки × нижний угол j-го столбца

8. Строится следующая таблица. Свободная переменная меняется местами в таблице с базисной переменной .

9. Заполняются i-я строка и j-й столбец: Элементы из нижних углов выделенных строки и столбца переносятся в верхние углы соответствующей клетки.

10. Заполняются верхние углы остальных клеток таблицы: Верхние углы клеток новой таблицы равны алгебраической сумме верхнего и нижнего угла соответствующих клеток предыдущей таблицы.

β

x1

…

xs

…

xk+i

…

xk

F

…

…

-λγj

…

xk+1

…

-λα1j

…

…

…

…

…

…

…

…

…

xk+l

…

…

-λαlj

…

…

…

…

…

…

…

…

…

xj

λβi

λαi1

…

λαis

…

λ

…

λαik

…

…

…

…

…

…

…

…

xn

…

…

-λαnj

…

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

Все переменные в строке таблицы являются свободными и равны 0.

Базисные переменные – в столбце равны:

Значение целевой функции:

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?