Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Симплексные преобразования

 

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

.

Получаем, что

 

 

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

,

получим:

 

откуда

 

Аналогично, при подстановке в выражение для целевой функции

получим:

и окончательно

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

1. Элементы разрешающей строки новой таблицы получаются делением старых элементов этой строки на разрешающий элемент:

2. Элементы остальных строк разрешающего столбца обнуляются:

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

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

 

 
 

 

 


Рис. 2.11

 

Соответствующие формулы для новой симплексной таблицы получаются из вышеприведенных соотношений и имеют вид:

 

 

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

Но величина – это наименьшее симплексное отношение, равное значению переменной в новой симплексной таблице, следовательно

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


<== предыдущая | следующая ==>
Общая идея симплексного метода | Методы решения задач целочисленного программирования

Date: 2016-07-25; view: 577; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию