2. Линейное программирование (ЛП)

Вид материала

Документы

Подобный материал:

• Введение в линейное программирование линейное программирование (ЛП), 139.72kb.
• Линейное программирование, 346.17kb.
• Программа дисциплины Линейное программирование Семестр, 17.93kb.
• Аттестационное тестирование в сфере профессионального образования, 72.49kb.
• Контрольная работа по темам «Линейное программирование на Паскале» и«Условный оператор», 4.21kb.
• Федеральное агентство по образованию, 124.95kb.
• Курс является базовым как для изучения других математических дисциплин, так и для более, 39.9kb.
• Введение в линейное программирование Задача планирования производства, 90.61kb.
• В. В. Панферов, 64.65kb.
• Содержание, 1344.25kb.

2. Линейное программирование (ЛП)

Методы линейного программирования оказались эффективным средством решения задач области исследования операций. Слово «программирование» здесь соответствует слову «планирование». Методами ЛП можно решить многие задачи эффективного использования ресурсов.

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

P = 2x₁ + 4x₂  max (максимизация прибыли),

3x₁ + 4x₂  1700 (ограничение на ресурс досок) (1)

2x₁ + 5x₂  1600 (ограничение на ресурс машинного времени).

Здесь: x₁,x₂ - количество выпускаемых в неделю двух видов полок; коэффициенты первого ограничения - затраты количества досок на единицу продукции каждого вида; коэффициенты второго ограничения - затраты количество машинного времени; правые части ограничений максимальное возможное количество ресурсов (досок и машинного времени); Функция P - еженедельная общая прибыль, коэффициент который - прибыль от единицы продукции каждого вида.

Э
то типичная двухмерная задача ЛП.

Рис. 1

На рис.1. границы ограничений определяются прямыми

3x₁ + 4x₂ = 1700 (2)

2x₁ + 5x₂ = 1600.

Стрелки указывают с какой стороны прямой выполняется ограничения. Неотрицательность переменных даёт неравенства x₁  0, x₂  0. Допустимая область заштрихована. Штриховыми линиями изображены прямые 2x₁+4x₂=0, 2x₁+4x₂=800, обозначенные a и b соответственно. Эти прямые параллельны и представляют собой две линии уровня функции P со значениями 0 и 800. Градиент  P = (2,4)^Т указывает направление возрастания.

Линией уровня с наибольшим значением P, имеющей хотя бы одну общую точку с допустимой областью, является прямая С, проходящая через вершину B. Вершину B можно найти, как точку пересечения двух прямых, решая систему уравнений (2) B=(300,200). Подставляя решение в P найдем P= 2 x 300 + 4 x 200 = 1400 максимальную прибыль.