Геометрическая интерпретация задачи линейного программирования.
Каждой паре чисел х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 | n2 | C | (III) | |||||||||||
2 | (II) | |||||||||||||
1 | n1 | 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. Для точного определения координат точки С рассмотрим уравнения прямых, пересечение которых ее образовало.
Получаем систему из двух уравнений:
2х1 + 1х2 = 12,
2х1 + 3х2 = 18,
решив которую получим точные значения х1=4.5; х2=3.
Метод решения системы линейных уравнений может быть использован любой, однако, в целях сокращения объема вычислений при дальнейшем изложении предлагается метод Крамера.
Напомним кратко его суть:
Для решения системы
a11 х1 + a12 х2 = b1,
a21 х1 + a22 х2 = b2,
вычисляем D = a11 a22 - a12 a21,
D1 = b1a22 - a12 b2,
D2 = a11 b2 - b1a21,
и затем х1 = D1 / D; х2 = D2 / D.
В нашем примере: D=2´3 – 1´2 = 4,
D1 = 12´3 – 1´18 = 18,
D2 = 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 | 1.5 | ||
Концентраты (х2) | 2.5 | |||
Норматив |
Под нормативом понимается необходимый минимум питательных веществ суточного рациона. В этой задаче необходимо найти такие объемы кормов х1, х2 , чтобы обеспечить содержание в них кормовых единиц, белка и кальция не менее нормативного при минимальной стоимости. Опять же предполагая, что количество полезных веществ, а также стоимость пропорциональны объемам кормов, получаем следующую математическую модель задачи:
(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.
Сделаем аналитическую проверку:
D=0.5´2 – 1´10 = –9,
D1 = 20´2 – 1´100 = –60,
D2 = 0.5 ´100 – 20 ´10 = –150.
Откуда х1 = –60 / –9 = 6.67, х2 = –150 / –9 = 16.67.
Дата добавления: 2020-10-25; просмотров: 443;