2. Линейное программирование (ЛП) Методы линейного программирования оказались эффективным средством решения задач области исследования операций. Слово «программирование» здесь соответствует слову «планирование». Методами ЛП можно решить многие задачи эффективного использования ресурсов. Рассмотрим простой пример задачи планирования производства.P = 2x1 + 4x2 max (максимизация прибыли),3x1 + 4x2 1700 (ограничение на ресурс досок) (1)2x1 + 5x2 1600 (ограничение на ресурс машинного времени). Здесь: x1,x2- количество выпускаемых в неделю двух видов полок; коэффициенты первого ограничения - затраты количества досок на единицу продукции каждого вида; коэффициенты второго ограничения - затраты количество машинного времени; правые части ограничений максимальное возможное количество ресурсов (досок и машинного времени); Функция P - еженедельная общая прибыль, коэффициент который - прибыль от единицы продукции каждого вида. Это типичная двухмерная задача ЛП. Рис. 1 На рис.1. границы ограничений определяются прямыми3x1 + 4x2 = 1700 (2)2x1 + 5x2 = 1600. Стрелки указывают с какой стороны прямой выполняется ограничения. Неотрицательность переменных даёт неравенства x1 0, x2 0. Допустимая область заштрихована. Штриховыми линиями изображены прямые 2x1+4x2=0, 2x1+4x2=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 максимальную прибыль.