Содержание
Вид материала | Документы |
Содержание2.4. Переход к новому базису |
- Содержание дисциплины наименование тем, их содержание, объем в часах лекционных занятий, 200.99kb.
- Содержание рабочей программы Содержание обучения по профессиональному модулю (ПМ) Наименование, 139.63kb.
- Заключительный отчет июль 2010 содержание содержание 1 список аббревиатур 3 введение, 6029.85kb.
- 5. Содержание родительского правоотношения Содержание правоотношения, 110.97kb.
- Содержание введение, 1420.36kb.
- Сборник статей Содержание, 1251.1kb.
- Сборник статей Содержание, 1248.25kb.
- Анонсы ведущих периодических изданий содержание выпуска, 806.18kb.
- Вопросы к экзамену по дисциплине «Коммерческая деятельность», 28.08kb.
- Конспект лекций содержание содержание 3 налог на прибыль организаций 5 Плательщики, 795.2kb.
2.4. Переход к новому базису
В старом базисе

![]() | (8) |
Теперь мы перешли в новую вершину, которой соответствует базис


![]() | (9) |
Выведем формулы для





выразим из него вектор


и подставим это выражение в (8). Тогда мы получим

Перегруппировывая слагаемые, получим:

Таким образом, координаты вектора ![]() | в новом базисе имеют вид |
![]() | (10) |
что и дает разложение векторов по новому базису
2.5. Отыскание оптимального плана
Пусть мы стремимся к минимуму целевой функции, то есть нашей задачей является

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


![]() | (1.34) |
![]() | (1.35) |
где все





![]() | (1.36) |
Введем величины
![]() | (1.37) |
где



Теорема 1.9. Если для некоторого j выполняется условие

- Случай 1. Если целевая функция ограничена снизу, то можно построить опорный план с меньшим значением целевой функции, чем предыдущий;
- Случай 2. Если целевая функция неограничена снизу, то можно построить план, соответствующий сколь угодно малому значению целевой функции.
Доказательство:
Попробуем ввести в базис именно вектор


Умножив разложение (1.36) для





В последнем равенстве к обеим частям равенства прибавлена величина

Теперь рассмотрим два случая.
Случай 1.
Пусть среди чисел


где минимум ищется по всем тем индексам j , для которых


так как


Случай 2.
Пусть все

![]() | (1.38) |
будет стремиться к

Теорема 1.10. Если для некоторого опорного плана для всех j справедливы неравенства

Доказательство:
Пусть


![]() | (1.39) |
![]() | (1.40) |
Покажем, что

По предположению, все



![]() | (1.41) |
Подставим в (1.39) вместо


и изменим порядок суммирования
![]() | (1.42) |
Аналогично, подставляя в (1.41) для каждого j выражение


Так как система векторов




получим

то есть любой другой план имеет не меньшее значение целевой функции, чем наш опорный план.
Эта теорема дает критерий оптимальности опорного плана.
Теоремы 1.9 и 1.10 дают возможность, начав с некоторого исходного опорного плана, получать последовательность все более лучших опорных планов, которые завершатся либо оптимальным планом, либо будет показано, что целевая функция неограничена.
Отметим следующее:
- Если при вычислении
минимум достигается при нескольких i, то для вывода из базиса обычно берут вектор
с наименьшим индексом.
- Для определения вектора
, вводимого в базис, обычно берут тот вектор
, для которого разность
наибольшая