2. Оптимальное планирование
Первыми работами в области оптимального планирования следует считать исследования Л. В. Канторовича, относящиеся к 1939-Д940 гг. [14]. В своих работах Л. В. Канторович показал, что многие задачи экономики, управления производства формулируются как задачи оптимального планирования, и предложил несколько методов их решения [14, 15, 16].
За рубежом задача оптимального планирования впервые математически была сформулирована в 1941 г. американским ученым Ф. Хичкоком [54]. В 1947—1948 гг. Дж. Данциг разработал общий метод решения задач линейного программирования; [52, 53]. Большую роль в практическом освоении методом оптимального планирования сыграли А. Чарнес, В. Купер, A. Хандерсон [55]. В настоящее время накоплен довольно большой опыт решения задач оптимального планирования, создан ряд оригинальных методов решения этих задач, наметились существенные связи оптимального планирования с другими дисциплинами [3, 13, 9, 47].
По своей сути задачи оптимального планирования являются экстремальными задачами и не являются
новыми в математике. Принципиально новым в этих задачах считается, во-первых, многомерность области, в которой ищется решение, и, во-вторых, сложная (в большинстве случаев) форма этой области.
Граница области
допустимых решений в общем случае является кусочно-гладкой и не обязательно связной гиперповерхностью. Принадлежность точки
к области
может быть определена предикатом
Используя
-конъюнкцию
а у вместо системы (5.1) можно записать одно неравенство:
Семейство гиперповерхностей, определяемое уравнением
при
включает границу области допустимых решений (
; при
гиперповерхности содержатся внутри области
а при
охватывают эту область.
Рис. 35.
Таким образом, приходим к следующей формулировке задачи оптимального планирования: в области
определяемой неравенством (5.3), необходимо найти точку, которой соответствует наименьшее (или наибольшее) значение функции цели.
Уравнение
является уравнением семейства гиперповерхностей уровня функции цели
Относительно области
это семейство может располагаться по-разному, вследствие чего точка, в которой достигается оптимальное
решение, может располагаться как внутри
(рис. 35, а), так и на ее границе (рис. 35, б, в).
Задача оптимального планирования может иметь бесчисленное множество решений (рис. 35, в). Точка
является точкой локального экстремума в том смысле, что для всех точек некоторой окрестности этой точки, принадлежащих одновременно области
выполняется неравенство
В общем случае задача оптимального планирования может иметь несколько локальных экстремумов внутри области
и на ее границе.