Геометрическая интерпретация задачи линейного программирования
Каждой паре чисел х 1 и х 2 поставим в соответствие точку плоскости (2-мерного пространства) с координатами х 1 и х 2, тогда каждое ограничение (2.2.1) задает полупространство, а вся система (2.2.1) определяет многоугольник (в n -мерном пространстве – многогранник), полученный в результате их пересечения. В общем случае многогранник может быть неограниченным или пустым (система неравенств противоречива). В примере 2.2.1 множество допустимых планов соответствует на плоскости множеству точек многоугольника OABCD(рис 2.2.1.). Целевая функция F=5 х 1 + 6 х 2 определяет на плоскости семейство прямых линий (в n -мерном пространстве – плоскостей), параллельных друг другу, причем, чем дальше прямая от точки О, тем большее значение принимает целевая функция. Таким образом, оптимальное решение будет в точке многоугольника OABCD, где целевая функция касается этого многоугольника при удалении от точки О. х 2 11 (I) 10 9 8 7F 6 n 5A B 4 3 n 2 C (III) 2 (II) 1 n 1 2 3 4 5 D 6 7 8 9 10 11 12 14 15 O Рис.2.2.1. Графическое представление задачи 2.2.1. х 1
В нашем примере это будет вершина многоугольника С с координатами (примерно) х 1=4.5; х 2=3. Для точного определения
97 координат точки С рассмотрим уравнения прямых, пересечение которых ее образовало. Получаем систему из двух уравнений: 2 х 1 + 1 х 2 = 12, 2 х 1 + 3 х 2 = 18, решив которую получим точные значения х 1=4.5; х 2=3. Метод решения системы линейных уравнений может быть использован любой, однако, в целях сокращения объема вычислений при дальнейшем изложении предлагается метод Крамера. Напомним кратко его суть: Для решения системы
a 11 х 1 + a 12 х 2 = b 1,
a 21 х 1 + a 22 х 2 = b 2, вычисляем Δ = a 11 a 22 − a 12 a 21, Δ1 = b 1 a 22 − a 12 b 2, Δ2 = a 11 b 2 − b 1 a 21, и затем х 1 = Δ1 / Δ; х 2 = Δ2 / Δ. В нашем примере: Δ=2×3 – 1×2 = 4, Δ1 = 12×3 – 1×18 = 18, Δ2 = 2 ×18 – 12 ×2 = 12, откуда х 1 = 18/4 = 4.5, х 2 = 12/4 = 3 (совпало с первоначальным приближением). Вычислим значение целевой функции в точке С:
F = 5 × 4.5 + 6 ×3 = 40.5. Таким образом мы решили поставленную задачу, нашли объемы производства х 1 первого и х 2 второго вида продукции, удовлетворяющие ограничениям (2.2.1) и доставляющие максимальное значение целевой функции F = 40.5 усл.ед. Пример 2.2.2. Рассмотрим еще одну задачу (ее часто называют задачей о диете, хотя аналогичной математической моделью можно описывать задачи, ничего общего с диетой не имеющие). Таблица 2.2.2 Содержание в 1 кг Виды кормов Кормовых ед.Белок (г)Кальций (г) Себестоимость 1 кг (усл. ед). Сено ( х 1) 0.5 50 10 1.5 Концентраты ( х 2) 1 200 2 2.5 Норматив 20 2000 100 Под нормативом понимается необходимый минимум питательных веществ суточного рациона. В этой задаче необходимо найти такие объемы кормов х 1, х 2 , чтобы обеспечить содержание в них
98 кормовых единиц, белка и кальция не менее нормативного при минимальной стоимости. Опять же предполагая, что количество полезных веществ, а также стоимость пропорциональны объемам кормов, получаем следующую математическую модель задачи: (I) 0.5 х 1 + 1 х 2 ≥ 20 (II) 50 х 1 + 200 х 2 ≥ 2000 (III) 10 х 1 + 2 х 2 ≥ 100 (2.2.2)
х 1 ≥ 0, х 2 ≥ 0,
F =1.5 х 1 + 2.5 х 2→ min. Геометрическую интерпретацию данной задачи приведем на рис.2.2.2. х 2 50 A (II) 40 35 30 F n 20 B (III) 10 (I) 5 C 5 10 15 20 25 30 35 40 х 1 Рис.2.2.2. Графическое представление задачи 2.2.2 В данном случае множество допустимых планов представляет собой неограниченный многоугольник, заштрихованный на рис.2.2.2. Целевая функция принимает наименьшее значение в точке В. Визуально на графике координаты этой точки х 1 ≅ 7, х 2 ≅ 17. Сделаем аналитическую проверку: Δ=0.5×2 – 1×10 = –9, Δ1 = 20×2 – 1×100 = –60, Δ2 = 0.5 ×100 – 20 ×10 = –150. Откуда х 1 = –60 / –9 = 6.67, х 2 = –150 / –9 = 16.67.
Ви переглядаєте статтю (реферат): «Геометрическая интерпретация задачи линейного программирования» з дисципліни «Математична економіка»
