Экономико-математическое моделирование в химии и экологии. Бутырская Е.В - 8 стр.

                                    8
решением называется решение, при котором              все      переменные
неотрицательны. Для канонической задачи множество всех допустимых
решений задачи представляет выпуклый многогранник, который называется
многогранником решений. Если задача линейного программирования имеет
оптимальное решение, то линейная функция F принимает максимальное
(минимальное ) значение в одной из угловых точек многогранника решений.
Каждому      допустимому      базисному    решению      задачи   линейного
программирования соответствует угловая точка многогранника решений и
наоборот, каждой угловой точке многогранника решений соответствует
допустимое базисное решение. Таким образом, оптимум линейной функции
задачи линейного программирования следует искать среди конечного числа ее
допустимых базисных решений. Один из путей решения задачи линейного
программирования – перебрать конечное число допустимых базисных решений
системы ограничений и выбрать среди них то, на котором функция цели
принимает оптимальное решение. Геометрически это соответствует перебору
всех угловых точек многогранника решений. Такой перебор в конце концов
приведет к оптимальному решению ( если оно существует ), однако его
практическое осуществление связано с огромными трудностями, так как для
реальных задач число допустимых базисных решений хотя и конечно, но может
быть чрезвычайно велико.
      Число перебираемых допустимых базисных решений можно сократить,
если проводить перебор не беспорядочно, а с учетом изменений линейной
функции, т.е. добиваясь того, чтобы каждое следующее решение было ближе к
оптимуму, чем предыдущее. Идея последовательного улучшения решения легла
в основу универсального метода решения задач линейного программирования –
симплексного метода. Для реализации симплексного метода необходимо
освоить три основных элемента :
- способ определения какого–либо первоначального допустимого базисного
   решения задачи;
- правило перехода к лучшему ( точнее, не худшему ) решению;
- критерий проверки оптимальности найденного решения.
Критерий оптимальности решения при отыскании максимума линейной
функции: если в выражении линейной функции цели через неосновные
переменные отсутствуют положительные коэффициенты при неосновных
переменных, то решение оптимально. Критерий оптимальности решения при
отыскании минимума линейной функции: если в выражении линейной функции
через неосновные переменные отсутствуют отрицательные коэффициенты при
неосновных переменных, то решение оптимально. Рассмотрим решение задачи
линейного программирования с использованием симплексных таблиц на
конкретном примере.