Категория
Информатика
Тип
реферат
Страницы
17 стр.
Дата
22.05.2014
Формат файла
.html — Html-документ
Архив
1028412.zip — 10.09 kb
  • zadachi-linejnogo-programmirovanija_1028412_1.html — 34.99 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо



Текст работы

Система ограниченийпринимает вид:

 

/> ( 1 )

где />

Базис (X1, X2, X3… Xr) обозначим через Б. Пусть все небазисные переменные равны нулю:

/>.

Найдем из системы ( 1 )значение базисных переменных :

/>


В результате получаембазисное решение/> соответствующеебазису Б .

Целевая функция F ( X1, ...., Xn) также выражается через небазисные переменные :

/>/>

Замечаем, что значениецелевой функции, соответствующее базисному решению, равно :/> C0: FБ = C0.

2.  Следующим шагом алгоритма являетсяпроверка достижения оптимума. Если оптимум не достигнут, то из базиса Будаляется одна из переменных в небазисные, а вместо нее из числа прежнихнебазисных переменных вводится новая. Получаем новый базис Б’ .

С новым базисом поступаемтак же в соответствии с содержанием шагов 1 и 2. Если в результате этогооптимум не достигнут, то все шаги повторяем снова, причем каждый новый шагзаключается в переходе от базиса Б к новому базису Б’, такому, чтозначение Fб уменьшается или, по крайней мере, не увеличивается:Fb’< Fb

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

Проследим за этойпоследовательностью шагов на примерах.

Задача 4.2.1. Минимизировать F = X 2 - X 1 при неотрицательных X 1 и X 2 , удовлетворяющих системеограничений:

 



Ваше мнение



CAPTCHA