Постановка задач линейного программирования

⇐ ПредыдущаяСтр 8 из 10Следующая ⇒

Методы линейного программирования оказываются весьма эффективными при исследовании операций, в том числе технологических процессов. Термин " программирование" в данном случае следует понимать как планирование, и это определяет характер принимаемых решений и рассматриваемых задач.

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

Рассмотрим постановку задачи линейного программирования на конкретном примере.

Упражнение №7. Предприятие производит две модели набора для ванной комнаты из природного декоративного камня. Назовем их соответственно моделями А и Б. Производство моделей ограничено сырьем и временем машинной обработки. Для каждого комплекта модели А требуется 3 м² полированного камня, для модели Б – 4 м². Предприятие может получить от поставщиков не более 1700 м² камня в неделю. Для каждого комплекта модели А требуется 12 минут машинного времени, модели Б – 30 минут. В неделю можно использовать не более 160 часов машинного времени. Сколько комплектов моделей А и Б следует выпускать предприятию в неделю, если каждая модель А приносит 2 тысячи рублей прибыли, а каждая модель Б приносит 4 тысячи.

Обозначим через Х₁ и Х₂ количество моделей А и Б, которые следует выпускать в неделю. Решение задачи как раз и состоит в том, чтобы найти их наилучшие (оптимальные) значения

Очевидно, что оптимальными для данных условий задачи будут значения Х₁ и Х₂, которые максимизируют еженедельную прибыль предприятия Р=2Х₁+4Х₂, то есть в качестве целевой функции выступает еженедельная прибыль предприятия.

Как же можно решать задачи подобного типа?

Если вспомнить классическую теорию оптимизации функций нескольких переменных, то для этого необходимо найти значения аргументов, при которых производная от функции по переменным равна нулю или не существует. В нашем случае этого явно недостаточно, так как первые производные функции прибыли по переменным X₁ и X₂ постоянны и равны двум и четырем. Чтобы увеличить прибыль, следует увеличивать одновременно как Х₁, так и Х₂. Но (а в этом и заключается вся проблема) – значения переменных нельзя увеличивать неограниченно из-за лимитов сырья и машинного времени.

Поскольку Х₁ и Х₂ выражают недельные объемы производства, то

Х₁≥ 0, Х₂≥ 0. (28)

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

· ограничение на машинное время: (12/60)X₁+(30/60)X₂≤ 160,

или

0, 2X₁+0, 5X₂≤ 160,

или

2Х₁+5Х₂≤ 1600. (29)

· Ограничение на сырье:

3Х₁+4Х₂≤ 1700. (30)

Следовательно, задача состоит в том, чтобы найти значения Х₁ и Х₂, удовлетворяющие условиям (28 – 30) и максимизирующие целевую функцию

Р=2Х₁+4Х₂.

Так формулируется типичная двумерная (двух переменных) задача линейного программирования, признаками которой являются:

· целевая функция является линейной относительно своих переменных,

· ограничения на решение задачи также линейны.

Для двумерной задачи наглядным является графическое ее решение (рис. 7).

Рис. 7. Область допустимых значений для упражнения № 7

Условия неотрицательности переменных позволяют рассматривать только положительный квадрант, границы допустимых решений в котором определяются прямыми: 2Х₁+5Х₂=1600; 3Х₁+4Х₂=1700. При оптимальном решении ограничения (28-30) превращаются в равенства, что означает полное использование сырья и машинного времени. Стрелки на прямых указывают, в какую сторону от прямых выполняются ограничения.

Область OABC содержит все допустимые решения, для которых соблюдаются граничные условия. Штриховыми линиями на рис. 7 показаны прямые 2Х₁+4Х₂=200 и 2X₁+4Х₂=800. Эти прямые параллельны (предлагается читателю самостоятельно доказать это) и представляют собой линии уровня равных значений прибыли (изолинии) со значениями 200 и 800 соответственно.

Из рис. 7 ясно, что прибыль возрастает по мере того, как изолинии удаляются от начала координат. Иными словами, вектор с компонентами (2, 4) (значения производных от прибыли по обеим переменным) указывает направление возрастания целевой функции: вектор перпендикулярен изолиниям прибыли. Изолиния с максимальным значением прибыли, имеющая хотя бы одну точку с допустимой областью OABC, является прямой, проходящей через точку В, в которой Р=1400.Точка В (Х₁=300, Х₂=200) соответствует оптимальному решению задачи. Значения переменных Х₁ и Х₂ могут быть найдены из совместного решения равенств:

2Х₁+5Х₂=1600,

3Х₁+4Х₂=1700.

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

Общая задача линейного программирования состоит в максимизации (минимизации) линейной функции

Z=c₁X₁+c₂X₂+...+c_nX_n (31)

от n переменных X₁, X₂,.., X_n, удовлетворяющих условиям неотрицательности

X₁≥ 0,..., X_n≥ 0 (32)

и m линейными ограничениями

a₁₁X₁+a₁₂X₂+...+a_1nX_n≤ (=, ≥ ) b₁

a₂₁X₁+a₂₂X₂+...+a_2nX_n≤ (=, ≥ ) b₂ (33)

.....................................……………

a_m₁X₁+a_m₂X₂+...+a_m_nX_n≤ (=, ≥ ) b_m

Значения a_ij, b_i, c_i предполагаются известными.

⇐ Предыдущая 1 2 3 4 5 6 789 10 Следующая ⇒