Общая задача линейного программирования

из "Математическое оптимальное программирование в экономике "

После того как мы подробно рассмотрели частный случай задачи линейного программирования, задачу раскроя, уместно познакомиться и с ее общей постановкой. [c.27]
Выбор плана означает указание интенсивностей использования различных технологических способов, т. е. план определяется вектором х = (х, х2,. .., xs) с неотрицательными компонентами. [c.28]
Положительные компоненты означают объемы производства, а отрицательные — объемы затрат соответствующих ингредиентов в плане. [c.28]
задача состоит в отыскании минимума линейной функции при линейных ограничениях, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Выше указывалось, что этот минимум обязательно достигается в одной или нескольких вершинах многогранника. Уточним так дело обстоит, если многогранник ограничен. В противном случае решение задачи может и не существовать. Для решения задачи необходимо иметь возможность устанавливать, оптимален ли план без непосредственного сравнения с планами, соответствующими остальным вершинам многогранника. Эта возможность и дается признаком оптимальности плана, формулируемым в виде такой теоремы. [c.29]
Очень важно отметить, что вектор оценок у, соответствующий оптимальному плану, сам является решением упоминавшейся уже экстремальной задачи, подобной исходной, получившей название двойственной задачи линейного программирования. [c.30]
Читатель, внимательно ознакомившийся с объяснением то-то, как составлялась двойственная задача к задаче раскроя, без труда сможет установить экономический смысл этих соотношений. [c.30]
Связь между прямой и двойственной задачами линейного программирования характеризуется следующим положением. [c.30]
Это утверждение носит название теоремы двойственности. [c.31]
Замечание отметим, что решение прямой и двойственной задач линейного программирования всегда может быть сведено к отысканию оптимальных смешанных стратегий двух игроков в прямоугольной игре с нулевой суммой. Таким образом, методы теории игр могут применяться при решении задач линейного программирования и, наоборот, аппарат линейного программирования может применяться в теории игр. [c.31]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 было продемонстрировано решение задачи о раскрое с помощью метода последовательного улучшения плана. Близко к нему примыкает симплекс-метод, разработанный американским математиком. Дж. Данцигом. Здесь мы приведем лишь краткое описание этого метода. [c.31]
Из критерия оптимальности ясно, что план х оптимален тогда и только тогда, когда Ск ак для всех К. [c.33]
Действительно, если для какого-нибудь К выполняется неравенство ак Ск. то план неоптимален и способ ак целесообразно ввести в новый базис. Если таких К несколько, то естественно ввести один из них, например, тот, для которого разность ак — Ск максимальна. Пусть он соответствует K=S. [c.33]
Важно отметить, что Л / неотрицательны. Это ясно из выбора 0. По аналогичным формулам можно преобразовать всю симплексную таблицу. [c.34]
Читателю рекомендуется после ознакомления с описанием симплекс-метода применить его к рассмотренному выше примеру. [c.34]
Заметим, что описанный ранее метод последовательного улучшения плана более эффективен, чем симплекс-метод, если число переменных в задаче превосходит число ограничений. [c.35]
Описанный вариант симплекс-метода не является единственным. На практике обычно употребляется более совершенный вариант — модифицированный симплекс-метод, связанный с использованием двойственной задачи (оценок) и по существу близкий к описанному выше методу последовательного улучшения плана. [c.35]

Вернуться к основной статье