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

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

Метод прямого перебора решения ЗЛП

Если известна функциональная связь целевой функции Y и искомой переменной X, то можно последовательно вычислить значения целевой функции для некоторых значений искомой переменной. Вычисления повторяются до тех пор, пока не будет найден min (max) значения целевой функции

Y=f(x₁, ..., x_i, ..., x_n, u₁, ..., u_j, ..., u_m),

x_i=x_0i+Dx_ik (k=0, 1, 2, ..., l).

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

Особенность и преимущества метода прямого перебора заключаются: 1) в независимости поиска от вида и характера целевой функции; 2) в цикличности поисковой процедуры; 3) в определении глобального экстремума целевой функции; 4) в простоте алгоритма и программы оптимизации; 5) в малом объеме необходимой машинной памяти.

В случае большой области изменения искомой переменной и (или) наличия более чем одного экстремума исследуемой функции использование этого метода неэффективно.

 

Основная идея симплекс-метода решения ЗЛП и ее теоретическое обоснование

геометрическим методом решение- наглядное 2.3.перем. если больше то нельзя.

методом простого перебора- можно но долго

Если известны какая-нибудь крайняя точка и значение целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведмо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей). Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея (рационального перебора). симплексного метода ( метода последовательного улучшения плана) для решения ЗЛП. Итак, симп. м. предполагает : 1) умение находить начальный опорный план; 2) наличие признака оптимальности опорного плана; 3) умение переходить к нехудшему опорному плану.

 

 

Теорема о возможности улучшения опорного решения задачи ЛП

Т . Если опорный план Х ЗЛП не вырожден и D_k<0, но среди чисел a_ik есть положительные ( не все a_ik<0), то существует опорный план X^’ такой, что Z(X^’)>Z(X), где Х исходное опорные решения.

Условие применимости симплекс-метода и теорема о неограниченности целевой функции на ОДЗ

Т . Если D_k<0 для некоторого j=k и среди чисел a_ik ()нет положительных, то целевая функция ЗЛП не ограничена на множестве ее планов.

 

 

Структура симплекс таблицы

			с1	с2	...	сi	...	сm	cm+1	...		cj		...	cn
Базис	Сб	А0	A1	A2	...	Ai	...	Am	Am+1	...		Aj		...	An
A1	с1	b1	1	0	...	0	...	0	a1,m+1	...		a1,j		...	a1,n
A2	с2	b2	0	1	...	0	...	0	a2,m+1	...		a2,j		...	a2,n
...	...	...	...	...	...	...	...	...	...	...		...		...	...
Ai	сi	bi	0	0	...	1	...	0	ai,m+1	...		ai,j		...	ai,n
...	...	...	...	...	...	...	...	...	...	...		...		...	...
Am	сm	bm	0	0	...		...	1	am,m+1	...		am,j		...	am,n
Zj-cj		D0	0	0	...	0	...	0	Dm+1	...	Dj		...		Dn

 

 

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

1. Находят опорный план.

2. Составляют симплекс-таблицу.

3. Выясняют, имеется ли хотя бы одно положительное число D_j . Если нет, то найденный план оптимален. Если же среди чисел  D_j имеются положительные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.

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

5. Определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов А_i по векторам нового базиса и числа D₀ и D_j.Все эти числа записываются в новой симплекс-таблице.

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

 

Контроль за правильностью решения ЗЛП симплекс-методом

1) все таблицы должны содержать положительные компоненты.

       2) Оценки при базисных векторах всегда нулевые.

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

 

Понятие о вырождении. Причины зацикливания в симплекс-методе

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

---

Дата добавления: 2018-05-12; просмотров: 713; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!