Графический способ решение задачи по линейному программированию

Графический способ решение задачи по линейному  программированию

 

Задание 1

Для сохранения нормальной жизнедеятельности человек  должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров - не менее 70 и витаминов- не менее 10 усл. ед. Содержание их в каждой единице  продуктов П₁, и П₂ равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П₁ - 2 руб., П₂   -3 руб.

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

Решение.

Обозначим x₁ и x₂ количество продуктов типа П₁ и П₂ соответственно. Очевидно, x₁, x₂ ³ 0 и целые.

Содержание  белка в продуктах типа П₁ и П₂ составит 0,2x₁ + 0,1x₂ , эта величина не должна быть меньше 120 усл. ед. Следовательно, должно выполняться неравенство 0,2x₁ +0,1 x₂ ≥ 120.

Содержание  жиров в продуктах типа П₁ и П₂ составит 0,075x₁ + 0,1x₂ , эта величина не должна быть меньше 70 усл. ед. Следовательно, должно выполняться неравенство 0,075x₁ +0,1 x₂ ≥ 70.

Содержание  витаминов в продуктах типа П₁ и П₂ составит 0x₁ + 0,1x₂ , эта величина не должна быть меньше 10 усл. ед. Следовательно, должно выполняться неравенство 0,1 x₂ ≥ 10.

Общая стоимость продуктов типа П₁ и П₂ составит    
f(X) = 2x₁ + 3x₂ руб. и она должна быть наименьше (минимальной).

Получаем  математическую модель задачи:

Найти минимум функции f(X) = 2x₁ + 3x₂ ® min

при заданных ограничениях

0,2x₁ +0,1 x₂ ≥ 120

0,075x₁ +0,1 x₂ ≥ 70

0,1 x₂ ≥ 10

x₁, x₂ ³ 0, целые.

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

Построим  множество допустимых решений задачи.

Прямые  ограничения x₁ ³ 0 , x₂ ³ 0 выделяют первую четверть плоскости.

Проведем  прямую (1): 0,2x₁ +0,1 x₂ = 120 через точки (0; 1200) и     (400; 400). Подставим в неравенство (1) координаты точки (800; 800):    0,2×800 +0,1×800 = 240 > 120, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем  прямую (2): 0,075x₁ +0,1 x₂ = 70 через точки (400; 400) и (600; 0). Подставим в неравенство (2) координаты точки (800; 800):       0,075×800 +0,1×800 = 140 > 120, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем  прямую (3): 0,1 x₂ = 10 через точки (800; 100) и (0; 100). Подставим в неравенство (3) координаты точки (800; 800): 0,1×800 = 80 > 10, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

 

Множество допустимых решений – это открытый многоугольник ABСDE.

Построим  линию нулевого уровня целевой функции f(X) = 2x₁ + 3x₂

2x₁ + 3x₂ = 0 через точки (0; 0 ) и (300; -200).

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

Из  чертежа видно, что наименьшее значение целевой функции будет на линии уровня, проходящей через точку D, являющейся пересечением прямых (2) и (3).

Координаты  этой точки найдем из системы

0,075 x₁ + 0,1 x₂ = 70

0,1 x₂ = 10

 x₂ = 100

0,075x₁ +10= 70

 x₂ = 100,

  0,075x₁ = 60

x₂ = 100

x₁ = 800

Таким образом, получаем x₁=800 и x₂=100. f_min =2 ×800 + 3 ×100=1900 рублей.

Полученное  оптимальное решение оказалось  целым, следовательно, это решение  поставленной задачи.

Таким образом, необходимо потреблять продуктов типа П₁ – 800 единиц и продуктов типа П₂ - 100 единиц. При этом стоимость их составит 1900 рублей и она будет минимальной (наименьшей).