Теорема (Правило вершин). Оптимальное решение задачи линейного программирования достигается в одной из вершин области.

Как найти вершины допустимой области:

Любая вершина допустимой области соответствует базисному решению задачи. Но не всякое базисное решение является вершиной, а только допустимое базисное решение.

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

Можно было их просматривать подряд, но есть более быстрые способы, выделяют 2 основных

1) графический метод

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

2) симплекс метод

Суть метода: для того чтобы найти наилучшую вершину области мы последовательно перебираем смежные вершины так, чтобы в ней значение функции было лучше чем в текущей вершине (для максимума лучше там, где значение функции >, для минимума - <).

Симплекс метод должен начинаться с выбора начального допустимого базисного решения. Предлагаются три варианта нахождения начального допустимого базисного решения:

Метод искусственного базиса

Метод искусственной целевой функции

Метод большого коэффициента М

Дата добавления: 2015-07-11