Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 51


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

1) Равенства называются линейно независимыми, если никакое из них нельзя получить из других путем умножения на какие-то коэффициенты и суммирования, т. е. никакое из них не является следствием остальных.)

§ 9. Существование решения ОЗЛП в способы его нахождения

Рассмотрим основную задачу линейного программирования (ОЗЛП): найти неотрицательные значения переменных х1, x2, ..., хn, удовлетворяющие т условиям-равенствам:

            (9.1)

и обращающие в максимум линейную функцию этих переменных:

L = с1х1

+ с2х2 + … + сnxn => max.       (9.2)

Для простоты предположим, что все условия (9.1) линейно независимы (r = m), и будем вести рассуждения в этом предположении 1).

Назовем допустимым решением ОЗЛП всякую совокупность неотрицательных значений х1, х2,..., xn, удовлетворяющую условиям (9.1). Оптимальным назовем то из допустимых решений, которое обращает в максимум функцию (9.2). Требуется найти оптимальное решение.

Всегда ли эта задача имеет решение? Нет, не всегда. Во-первых, может оказаться, что уравнения (9.1) вообще несовместны (противоречат друг другу).

1) Если среди условий-равенств (9.1) есть некоторые лишние, вытекающие из других, то это обнаружится автоматически в процессе решения ОЗЛП (см. [4, 6]).

Может оказаться и так, что они совместны, но не в области неотрицательных решений, т. е. не существует ни одной совокупности чисел х1

 0, х2

 0, ..., хn
 0, удовлетворяющей условиям (9.1). Наконец, может быть и так, что допустимые решения ОЗЛП существуют, но среди них нет оптимального: функция L в области допустимых решений не ограничена сверху. Все эти опасности подстерегают нас, главным образом, в «придуманных», искусственно поставленных задачах, хотя иногда легкомысленное планирование (неполный учет имеющихся ресурсов) приводит к неразрешимым задачам линейного программирования.




Содержание  Назад  Вперед