Геометрические соображения могут быть полезными при решении задач линейного программирования со многими переменными, а именно, когда в рассматриваемой задаче линейного программирования число переменных больше числа ограничений, записанных в форме равенств, не более чем на 2. Пусть, например, дана задача линейного программирования в следующей постановке.
f (x) = 
(2.10)
на множестве X = { x 
, i = 1,…,l; x j 
0, j = 1,…, n.}, (2.11)
где n – l = 2, причем ранг матрицы А = // a m+i j // равен l. i = 1,…,l; j = 1,…, n
Тогда, используя метод Жордана–Гаусса (метод исключения неизвестных), производим в системе ограничений-равенств
, i = 1,…,l,
l исключений, в результате которых l =n – 2 переменных выразятся через оставшиеся две переменные, скажем через x1 и x2, т. е.
x j= pj1 x1 + pj2 x2+bi, j =3,4,…,n, (2.12)
где pj 1, pj 2, bi - некоторые числа. Подставляя эти выражения в целевую функцию f и систему ограничений – неравенств
, i = 1,…, m,
получаем уже задачу линейного программирования с двумя переменными:
(2.13)
на множестве 
, i =1,…, m; pj1 x1+ pj2 x2 + βj ≥ 0, j=3,4,…, n; x1≥ 0, x2≥ 0.}, где α i1 ,α i2, θ i (i = 1,…, m), γ1, γ2, δ – некоторые числа.
Далее с помощью геометрических построений находим ее решение (x1*, x2*). Затем подставляем эти числа в (2.12) и (2.13), в результате получаем оптимальное решение и значение целевой функции исходной задачи (2.10) - (2.11).
Описанный метод исключения переменных, конечно, применим и в том случае, если в задаче (2.10) - (2.11) n-l=1. Тогда все сводится к описанию решения элементарной задачи линейного программирования с одной переменной. Если в задаче (2.10) - (2.11) на все переменные xj, j=1,…,n, наложено условие неотрицательности, то это приводит к уменьшению числа ограничений вида pj1 x1+pj2x2+βj ≥ 0.
Пример 2. 5. 1.
На металлургическом заводе производится чугун из материала треx видов, отличающихся друг от друга содержанием серы, фосфора, марганца и стоимостью:
Таблица 6
| Вид шиxтового материала | Содержание в 1 ед. шиxтового материала компонента (%) | Стоимость 1 ед. шиxтового материала | ||
| сера | фосфор | марганец | ||
| А1 | ||||
| А2 | ||||
| А3 |
Остальные 5 % шиxтового материала каждого вида составляют другие компоненты. Определить оптимальный набор шиxтового материала, при котором можно получить с наименьшими затратами чугун, содержащий не менее 12 % серы, не более 28 % фосфора и не более 60 %марганца.
Математическая формулировка задачи
Обозначим через xj, j = 1, 2, 3, количество шиxтового материала вида А j,необxодимое для получения 1ед. чугуна. Тогда математическая модель приведенной задачи запишется в виде:
минимизируется стоимость 1 ед. чугуна
f (x) = 10 x1+ 15 x2 +12 x3 → min
на множестве ограничений на содержание компонентов в чугуне
15× x 1 +10× x2+ 8× x3 ≥ 12
30× x 1 + 25× x2 + 17× x3 
28
50× x 1 +60× x2 + 70× x3 
60
x 1+ x2+ x3 = 1
xj ≥ 0, j = 1,2,3
Замечаем, что в данной модели число переменных равно n=3, и имеется ограничение – равенство, следовательно, n–1=2. Поэтому из имеющихся равенств выражаем одну переменную, например, x1=1-x2–x3≥0. Затем подставляем полученное значение переменной x1 в целевую функцию f(x) и в оставшиеся неравенства множества X.
f(x)=10-10×х2-10×х3+15×х2+12×х3=10+5×х2+2×х3 
min
х1=1-х2-х3
15-15×х2-15×х3+10×х2+8×х3³ 12 или 5х2+7х3£ 3
30-30×х2-30×х3+25×х2+17×х3 £ 28 или 5х2+13х3 ³ 2
50-50×х2-50×х3+60×х2+70×х3£ 60 или 10х2+20х3 £10
х2+х3£ 1
Последнее неравенство получено из условия, что х1³ 0.
В результате получаем задачу линейного программирования уже с двумя переменными x2 и x3:
min
на множестве:
5 x2+7x3 £ 3 (1)
5 x2+13x3 ³ 2 (2)
x2+2x3 £ 1 (3)
x2+x3 £ 1 (4)
x 2³ 0; x 3³ 0
Построим допустимое множество и линии уровня целевой функции 
в системе координат x2 x3 (рис10). На рисунке видно, что линейная функция принимает минимальное значение в вершине А ОДР ABCD. Координаты этой вершины отыскиваем, решая систему уравнений граничных прямых 5 x2+13x3 =2
x2=0
Отсюда x2* = 0; x3* = 2/13, т.е. А (0;2/13), и минимальное значение функции f * = 
(x2*; x3*)= 10+5×0+2× 
= 
($) 
Рис.10. Графическое решение задачи
Определяем оставшуюся компоненту оптимального решения исходной задачи X* = (x 1*, x 2*, x 3*):
x 1* = 1- x 2* -x 3* =1-0- = 
Таким образом, для получения 1 ед. чугуна с наименьшей себестоимостью, равной 
долл., необходимо использовать ед. шихтового материала вида А1 и единиц шихтового материала вида А3. Использование же шихтового материала вида А2 является экономически невыгодным. При этом полученный чугун будет содержать:
14% серы;
28% фосфора; 
53% марганца.
Пример 2. 5. 2.
В течение квартала планируется выпуск двух видов продукции. Фирма может оплатить материалы и труд (себестоимость) из двух источников – собственных и заемных средств. Собственные средства фирмы составляют 30000$. Банк может ссудить до 20000$ под 5% с условием погашения ссуды в конце квартала. Производственные мощности фирмы, цены и себестоимость продукции содержатся в таблице:
Таблица 7
| Вид про-дукции | Цена реализации ед. продукции | Себестоимость ед. продукции | Трудозатраты на технологические операции (час на 1 ед.) | ||
| Операция А | Операция В | Операция С | |||
| 14$ | 10$ | 0,5 | 0,3 | 0,2 | |
| 11$ | 8$ | 0,3 | 0,4 | 0,1 | |
| Ресурсы фирмы (час в квартал) |
Определить объемы выпуска продукции 1 и 2 и объем заемных средств, максимизирующих прибыль, если известно, что отношение объемов выпуска продукции 1 и 2 равно 2:1.
Математическая формулировка задачи
Обозначим через хi – количество продукции вида i (i=1,2),
х3 – объём заёмных средств.
Целевая функция:
f (x) = (14 – 10) х1 + (11- 8) х2 – 1,05 х3= 4х1+3х2-1,05х3 → max.
Затраты на материалы и труд:
10 х1 + 8 х2 ≤30 000+х3 (1)
Величина заемных средств:
х3 ≤ 20 000 (2)
Производственные ограничения (в часах):
0,5 х1 + 0,3 х1 ≤ 540 (3)
0,3 х1 + 0,4 х2 ≤ 500 (4)
0,2 х1 + 0,1 х2 ≤ 350 (5)
Объемы выпуска
х1 = 2 х2 (6)
хi ≥ 0, i=1,2,3
С учетом ограничения х1=2х2 придем к задаче с двумя неизвестными:
f (x) = 4х1+3х2–1,05х3=4×2х2+3х2–1,05х3= 11х2–1,05 х3 → max.
28х2–х3 ≤ 30000 (1) при х2=0 х3=-30000;
при х3=0 х2=1071,4
х3 ≤ 20000 (2) х3=20000
1,3х3 ≤ 540 (3) х3=415,4
х2 ≤ 500 (4) х2=500
0,5х2 ≤ 350 (5) х2=700
хi ≥ 0, i=2,3
В целевой функции коэффициент при х3 отрицательный, требуется max прибыль, т.е. в оптимальном решении х3=0.
При х3=0, достигается max прибыль в т.А (рис.11)
х1*=830,8
х2*=415,4
х3*=0
max f (х*)= 11. 415,4-1,05. 0=4569,4
Рис.11. Графическое решение задачи
Пример 2. 5. 3.
Менеджер желает приобрести акции трех ведущих предприятий, которые могут дать месячный доход, равный соответственно 11%, 15% и 8%. Риски при вложении капитала для приобретения данных акций определены рынком и равны соответственно 1; 1,2; 0,9. Требуется, чтобы средняя взвешенная этих рисков была не более 1,1. Менеджеру необходимо определить такие доли вложения своего капитала при покупке акций, которые приведут к получениию максимального дохода.
Математическая формулировка задачи
Обозначим: хi – количество акций i –го предприятия;
рi - вероятность получения дохода;
Математическое ожидание месячного дохода f:
f= 
x1+x2+x3=1 (1)
x1+1,2x2+0,9x3£ 1,1 (2)
xi³ 0 i=1,...,3
Выразим из (1) х1=1-х2-х3³0.
Тогда f(x)=11-11x1-11x3+15x2+8x3=11+4x2-3x3® max
Так как коэффициент при х3 отрицательный, то в оптимальном решении х3=0. Убедимся в этом решив задачу графическим методом (рис.12)
Так как х1³0, то получим: 1-х2-х3³ 0 Þ
х2+х3£ 1 (1)
1-х2-х3+1,2х2+0,9х3 £ 1,1 или 0,2х2-0,1х3£ 0,1 (2)
х2, х3³0
max f = f(C), т.е. оптимальный доход достигается в точке С с координатами (0,5;0).
Тогда f(C)= 11+4. 0,5 – 3. 0 = 13, оптимальный план Х*= (0,5;0,5;0).
Рис. 12. Графическое решение задачи