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

из "Оптимальные решения в экономике "

Если Ь 1 0, то неравенство означает, что имеется потребность в ингредиенте в размере bt если bt 0, то неравенство означает, что имеется ресурс данного ингредиента в размере — Ъ = Ь4 . [c.33]
удовлетворяющий условиям (1) и (2), является допустимым, а если в нем, кроме того, достигается минимум целевой функции, то этот план оптимальный. [c.34]
задача состоит в отыскании минимума линейной функции при линейных ограничениях, или, иначе говоря, минимума этой функции на выпуклом многограннике допустимых планов. Признак оптимальности плана формулируется в виде такой теоремы. [c.34]
Компоненты вектора у можно рассматривать как о. о оценки для всех видов ингредиентов. На языке этих оценок все условия теоремы имеют прозрачный экономический смысл (1) оценка каждого ингредиента неотрицательна (2) для каждого возможного способа получаемый эффект, который выражается алгебраической суммой оценок произведенных и затраченных ингредиентов, не превосходит h — расхода, связанного с применением способа (3) в оптимальный план могут включаться только такие технологические способы, для которых суммарная алгебраическая-оценка получаемой продукции равна расхо-ДУ h (4) ингредиенты, получаемые в оптимальном плане с избытком, имеют нулевые оценки. [c.35]
Очень важно отметить, что вектор оценок у, соответствующий оптимальному плану, сам является решением двойственной задачи линейного программирования, которая формулируется следующим образом. [c.35]
Читатель, внимательно ознакомившийся с объяснением того, как составлялась двойственная задача к задаче раскроя (см. стр.2 — 23), без труда сможет установить экономический смысл этих отношений. [c.36]
Это утверждение носит название теоремы двойственности. [c.36]
Использование теоремы двойственности и связанного с ней признака оптимальности допустимого плана лежит в основе большинства эффективных методов решения задач линейного программирования. В 2 был описан один из них — метод последовательного улучшения плана. Близко к нему примыкает симплекс-метод,. разработанный американским математиком Дж. Данцигом. Приведем краткое описание этого метода. [c.36]
Предположим, что уже имеется допустимый план х, причем такой, что способы, используемые в нем, являются базисными векторами (такой план называется опорным) . Можно считать, что базис состоит из первых т векторов av a2,. .., ат, так как этого всегда можно добиться изменением нумерации способов. Поскольку всякий вектор m-мерного пространства можно разложить по этому базису, найдем разложения всех векторов способов и вектора ограничений. Коэффициенты этих разложений объединены в табл. 3 (так называемая симплексная таблица). [c.37]
Мы говорим, что m векторов m-мерного векторного пространства образуют базис, если они линейно независимы, т. е. ни один H.I них не может быть выражен через другие. Тогда всякий вектор х пространства может быть единственным образом выражен через векторы базиса х = iai -f- i aa +. . . + mam, где величины 5 — коэффициенты разложения. [c.37]
Процедура симплекс-метода состоит из двух этапов. [c.38]
Из критерия оптимальности ясно, что план х оптимален тогда и только тогда, когда k ak для всех k. Действительно, если для какого-нибудь k выполняется неравенство ak k, то план неоптимален и способ а целесообразно ввести в новый базис. Если таких k несколько, то естественно ввести один из них, например, тот, для которого разность ak — 0% максимальна. Пусть он соответствует k = S. [c.39]
Эта задача отличается от рассматривавшейся задачи линейного программирования в канонической форме тем, что в ней требуется отыскать максимум, а не минимум. Понятно, что план ж такой задачи оптимален тогда и только тогда, когда k I ak для всех k. Начнем с выбора допустимого начального плана. Сразу видно, что допустимым является план хг =1, ж2 =1, х3 =0. Этот план опорный, так как векторы а, и 2 линейно независимы — образуют базис. [c.41]
Построим симплексную таблицу (табл. 4), найдя разложения по этому базису векторов аз и Ь. [c.41]
Разность а3 — С3 = — 1 — 1 = — 2 i 0, следовательно, исходный план неоптимален. Для того чтобы его улучшить, необходимо ввести в базис вектор а3. Так как мы хотим, чтобы и новый план был опорным, один из прежних векторов базиса должен быть из него исключен. [c.41]

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