Модифицированный геометрический  метод

Линия уровня целевой функции – линия, вдоль которой f сохраняет свое значение при переменных х₁, х₂. Для линейной функции (n=2) семейство линий уровня – семейство параллельных прямых.

Из курса высшей математики известно, что градиент функции всегда перпендикулярен линии уровня f(x₁,x₂) =const и показывает направление возрастания функции f

, где ,  – единичные орты, ориентированные вдоль соответствующих осей.

 

                                                  Алгоритм метода:         

1),2) Аналогично алгоритму графического метода.

3) Строим линию уровня целевой функции для произвольной константы.

4) Определяем направление градиента.

5) Перемещаем линию уровня параллельно самой себе вдоль ОДР по направлению градиента при поиске max целевой функции (при поиске min f по направлению антиградиента). Последняя точка касания линии уровня с ОДР и даст оптимальную вершину.

6) Рассчитать координаты оптимальной вершины.

 

 

Риc. 7. Решение задачи модифицированным графическим методом

 

Построим линию уровня для примера 2.3.1.

df dx2

           20 ×х₁+11 ×х₂=220 (220 – произвольное значение константы)

при   х₁=0,  х₂=20

х₂=0,  х₁=11

Изобразим на линии уровня градиент, выбрав произвольную точку N.

               

По оси х₁ откладываем 20, по оси х₂ откладываем 11. И строим вектор grad f, как сумму двух векторов. Градиент направлен слева–направо вверх. По grad f продвигаем линию уровня параллельно самой себе до последней точки касания ОДР, т.е. в данном случае это точка В, она и будет оптимальна.

Пример 2.4.1.

Мясокомбинатвыпускает два вида продукции А₁ и А₂. Продукт А₁ изготовляется с помощью механизма В₁, продукт А₂ с помощью механизма В₂. Затем оба продукта упаковываются на специальном оборудовании. Производительность механизма В₁ равна 4 т/ч, потери сырья при этом составляют 15%, суточная же производительность механизма В₂ равна 3,5 т/ч, потери сырья достигают 20%. В течение суток механизмы В₁ и В₂ могут работать не более 18 час и 20 час соответственно; 1 час работы этих механизмов обходится мясокомбинату в 300 и 250 долларов. Специальное оборудование может работать не более 10 час. в сутки, упаковывая за 1 час 12 т продукта А₁ или 10 т продукта А₂. Один час его использования обходится мясокомбинату в 200 долл. Стоимость 1 кг сырья равна 3 долл. Упаковка продукта А₁ весом 4/5 кг продается на рынке по 6 долл., упаковка же продукта А₂ весом 3/5 кг – по 5 долл. Необходимо порекомендовать мясокомбинату такие суточные потребления сырья для производства продукции А₁ и А₂, при которых чистая прибыль была бы максимальной. Предполагается, что рынок сбыта для каждого вида продукции практически неограничен.

 

 

Рис. 8. Технологическая схема производства

Математическая формулировка задачи

Обозначим:

(т) – количество продукта А₁ и А₂ соответственно;

 – количество упаковок продукта вида А₁;

 – количество упаковок продукта вида А₂;

– время работы механизма В₁;  – время работы механизма В₂.

 - время работы специального оборудования.

100% +15% в долях равна 1,15 – кол-во сырья для механизма В₁,

100% + 20% в долях равна 1,2 – кол-во сырья для механизма В₂,

Чистая прибыль f равна доходу от продажи упаковок продуктов А₁ и А₂ за вычетом стоимости сырья и работы механизмов В₁ и В₂ и специального оборудования.

Математическая модель:

 при ограничениях:

                                             ≤ 18                           (1)

                                                          ≤ 20                          (2)

                                                          ≤ 10                  (3)

                                                            х _i≥0 i=1,2

или после несложных преобразований:

                                                          х₁ ≤ 72                               (1)

  х₂ ≤ 70                              (2)

                                                          5 ×х₁ + 6 ×х₂ ≤ 600            (3)

Находим отрезки, отсекаемые по осям координат прямой 5 ×х₁ + 6 ×х₂ =600 (ограничение 3):

при х₁ = 0, х₂ = 100

при х₂ = 0, х₁ = 120

Рис.9. Графическое решение задачи

Находим координаты вершин ОДР из решения системы прямых, образующих этих вершины.

т. A (0,70); т. D (72,0)

Координаты вершины С определяем из системы:

5 ×х₁ + 6 ×х₂ ≤ 600

х₁=72,          

отсюда С (72;40)   

Координаты вершины В находим из системы:

                             5 ×х₁ + 6 ×х₂ ≤ 600

х₁=70,                          

отсюда В(36;70)

Рассчитаем значения целевой функции в вершинах:

f(A)=3958,4 × 0+4642 × 70=324940

 f(В)=3958,4 × 36+4642 × 70=467442,4

 f(C)=3958,4 × 72+4642 × 40=470684,8               max f

 f(D)=3958,4 × 72+4642 × 0=285004,8

Получаем, что оптимальной вершиной будет С (72,40), то есть для получения максимальной прибыли на механизм В₁ следует подать 1,15 ×72 =82,8 (т) сырья, на механизм В₂ – 1,24 ×40= 48 (т)

2.5.     Геометрический метод решения задач линейного программирования со многими переменными

Геометрические соображения могут быть полезными при решении задач линейного программирования со многими переменными, а именно, когда в рассматриваемой задаче линейного программирования число переменных больше числа ограничений, записанных в форме равенств, не более чем на 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 переменных выразятся через оставшиеся две переменные, скажем через x₁ и x₂, т. е.

x _j= p_j1 x₁ + p_j2 x₂+ b _i, j =3,4,…,n,                                 (2.12)

где p_{j 1,} p_{j 2}, b _i - некоторые числа. Подставляя эти выражения в целевую функцию f и систему ограничений – неравенств

, i = 1,…, m,

получаем уже задачу линейного программирования с двумя переменными:

                                     (2.13)

на множестве , i =1,…, m; p_j1 x₁+ p_j2 x₂ + β_j ≥ 0, j=3,4,…, n; x₁≥ 0, x₂≥ 0.}, где α _i1 , α _i2, θ _i (i = 1,…, m), γ_1, γ₂, δ – некоторые числа.

Далее с помощью геометрических построений находим ее решение (x₁^*, x₂^*). Затем подставляем эти числа в (2.12) и (2.13), в результате получаем оптимальное решение и значение целевой функции исходной задачи (2.10) - (2.11).

Описанный метод исключения переменных, конечно, применим и в том случае, если в задаче (2.10) - (2.11) n- l=1. Тогда все сводится к описанию решения элементарной задачи линейного программирования с одной переменной. Если в задаче (2.10) - (2.11) на все переменные x_j, j= 1,…, n, наложено условие неотрицательности, то это приводит к уменьшению числа ограничений вида  p_j1 x₁+ p_j2 x₂+ β_j ≥ 0.

Пример 2. 5. 1.

На металлургическом заводе производится чугун из материала треx видов, отличающихся друг от друга содержанием серы, фосфора, марганца и стоимостью:

Таблица 6

Вид шиxтового материала	Содержание в 1 ед. шиxтового материала компонента (%)			Стоимость 1 ед. шиxтового материала
	сера	фосфор	марганец
А1	15	30	50	10
А2	10	25	60	15
А3	8	17	70	12

Остальные 5 % шиxтового материала каждого вида составляют другие компоненты. Определить оптимальный набор шиxтового материала, при котором можно получить с наименьшими затратами чугун, содержащий не менее 12 % серы, не более 28 % фосфора и не более 60 %марганца.

Математическая формулировка задачи

Обозначим через x_j, j = 1, 2, 3, количество шиxтового материала вида А _j,необxодимое для получения 1ед. чугуна. Тогда математическая модель приведенной задачи запишется в виде:

минимизируется стоимость 1 ед. чугуна

                     f (x) = 10 x₁+ 15 x₂ +12 x₃ → min

на множестве ограничений на содержание компонентов в чугуне

15 × x ₁ +10 × x₂+ 8 × x₃ ≥ 12

30 × x ₁ + 25 × x₂ + 17 × x₃  28

50 × x ₁ +60 × x₂ + 70 × x₃  60

x ₁+ x₂+ x₃ = 1

x_j ≥ 0, j = 1,2,3

Замечаем, что в данной модели число переменных равно n=3, и имеется ограничение – равенство, следовательно, n–1=2. Поэтому из имеющихся равенств выражаем одну переменную, например, x₁=1-x₂–x₃≥0. Затем подставляем полученное значение переменной x₁  в целевую функцию f(x) и в оставшиеся неравенства множества X.

f(x)=10-10 ×х₂-10 ×х₃+15 ×х₂+12 ×х₃=10+5 ×х₂+2 ×х₃ min

 х₁=1-х₂-х₃

15-15 ×х₂-15 ×х₃+10 ×х₂+8 ×х₃ ³ 12 или 5х₂+7х₃ £ 3

30-30 ×х₂-30 ×х₃+25 ×х₂+17 ×х₃ £ 28   или 5х₂+13х₃ ³ 2

50-50 ×х₂-50 ×х₃+60 ×х₂+70 ×х₃ £ 60       или 10х₂+20х₃ £10

х₂+х₃ £ 1

Последнее неравенство получено из условия, что х₁ ³ 0.

В результате получаем задачу линейного программирования уже с двумя переменными x₂ и x₃:

min

на множестве:

                                                          5 x₂+7 x₃ £ 3 (1)

5 x₂+13 x₃ ³ 2 (2)

x₂+2 x₃ £ 1 (3)

x₂+ x₃ £ 1    (4)

x ₂ ³ 0; x ₃ ³ 0

Построим допустимое множество и линии уровня целевой функции  в системе координат x₂ x₃ (рис10). На рисунке видно, что линейная функция принимает минимальное значение в вершине А ОДР ABCD. Координаты этой вершины отыскиваем, решая систему уравнений граничных прямых                                            5 x₂+13 x₃ =2

                                             x₂=0

Отсюда x₂^* = 0; x₃^* = 2/13, т.е. А (0;2/13), и минимальное значение функции   f ^* = (x₂^*; x₃^*)= 10+5 ×0+2 × = ($)

Рис.10. Графическое решение задачи

Определяем оставшуюся компоненту оптимального решения исходной задачи   X^* = (x ₁^*, x ₂^*, x ₃^*):

x ₁^* = 1- x ₂^* - x ₃^* =1-0- =

Таким образом, для получения 1 ед. чугуна с наименьшей себестоимостью, равной долл., необходимо использовать  ед. шихтового материала вида А₁ и  единиц шихтового материала вида А₃. Использование же шихтового материала вида А₂ является экономически невыгодным. При этом полученный чугун будет содержать:

14% серы;

28% фосфора; 53% марганца.

Пример 2. 5. 2.

В течение квартала планируется выпуск двух видов продукции. Фирма может оплатить материалы и труд (себестоимость) из двух источников – собственных и заемных средств. Собственные средства фирмы составляют 30000$. Банк может ссудить до 20000$ под 5% с условием погашения ссуды в конце квартала. Производственные мощности фирмы, цены и себестоимость продукции содержатся в таблице:

Таблица 7

Вид про-дукции	Цена реализации ед. продукции	Себестоимость ед. продукции	Трудозатраты на технологические операции (час на 1 ед.)
			Операция  А	Операция  В	Операция С
1	14$	10$	0,5	0,3	0,2
2	11$	8$	0,3	0,4	0,1
Ресурсы фирмы (час в квартал)			540	500	350

 

Определить объемы выпуска продукции 1 и 2 и объем заемных средств, максимизирующих прибыль, если известно, что отношение объемов выпуска продукции 1 и 2 равно 2:1.

Математическая формулировка задачи

  Обозначим через х _i – количество продукции вида i (i=1,2),

х₃ – объём заёмных средств.

Целевая функция:

f (x) = (14 – 10) х₁ + (11- 8) х₂ – 1,05 х₃= 4х₁+3х₂-1,05х₃ → max.

Затраты на материалы и труд:

10 х₁ + 8 х₂ ≤30 000+х₃                         (1)

Величина заемных средств:

х₃ ≤ 20 000                                           (2)

Производственные ограничения (в часах):

0,5 х₁ + 0,3 х₁  ≤ 540                           (3)

0,3 х₁ + 0,4 х₂ ≤ 500                               (4)

0,2 х₁ + 0,1 х₂ ≤ 350                                (5)          

Объемы выпуска

  х₁ = 2 х₂                                                   (6)

х _i ≥ 0, i=1,2,3

С учетом ограничения х₁=2х₂ придем к задаче с двумя неизвестными:

f (x) = 4х₁+3х₂–1,05х₃=4 ×2х₂+3х₂–1,05х₃= 11х₂–1,05 х₃ → max.

28х₂–х₃ ≤ 30000   (1) при х₂=0 х₃=-30000;

                                        при х₃=0 х₂=1071,4

х₃ ≤ 20000              (2) х₃=20000

1,3х₃ ≤ 540             (3)     х₃=415,4

х₂ ≤ 500                   (4) х₂=500

0,5х₂ ≤ 350             (5) х₂=700

х _i ≥ 0, i=2,3

В целевой функции коэффициент при х₃ отрицательный, требуется max прибыль, т.е. в оптимальном решении х₃=0.

При х₃=0, достигается max прибыль в т.А (рис.11)

х₁*=830,8

х₂*=415,4      

х₃*=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=

                  x₁+x₂+x₃=1                                    (1)

                   x₁+1,2x₂+0,9x₃ £ 1,1                     (2)

                   x_i ³ 0 i=1,...,3

Выразим из (1) х₁=1-х₂-х₃ ³0.  

Тогда f(x)=11-11 x₁-11 x₃+15 x₂+8 x₃=11+4 x₂-3 x₃ ® max

Так как коэффициент при х₃ отрицательный, то в оптимальном решении х₃=0. Убедимся в этом решив задачу графическим методом (рис.12)

Так как х₁ ³0, то получим: 1-х₂-х₃ ³ 0 Þ

  х₂+х₃ £ 1                                                                                 (1)

1-х₂-х₃+1,2х₂+0,9х₃ £ 1,1  или 0,2х₂-0,1х₃ £ 0,1             (2)

х₂, х₃³0

max f = f(C), т.е. оптимальный доход достигается в точке С с координатами (0,5;0).

Тогда f(C)= 11+4^. 0,5 – 3^. 0 = 13, оптимальный план Х^*= (0,5;0,5;0).

Рис. 12. Графическое решение задачи

Виды оптимальных решений

Тот факт, что оптимальное решение находится в вершине ОДР, дал нам возможность сформулировать метод решения задач линейного программирования. Но из этого же факта можно сделать еще два очень важных вывода. Во-первых, если оптимальным решением являются координаты вершины ОДР, значит, столько оптимальных решений может иметь задача. Во-вторых, поскольку чем больше ограничений, тем больше вершин, то, следовательно, чем больше ограничений, тем больше оптимальных решений. Как видно из рис.14.а, вершина, координаты которой являются оптимальным решением, определяется углом наклона прямой, описывающей целевую функцию. Значит, каждая вершина будет соответствовать оптимальному решению для некоторой целевой функции.

 

 

Рис. 13

Поясним это на примере. Пусть для двух видов продукции П₁ и П₂ требуются трудовые, материальные, финансовые ресурсы. Наличие ресурсов каждого вида и их нормы расхода, необходимые для выпуска единицы продукции, приведены в табл.8.

Таблица 8

Характеристика	Вид продукции		Располагаемый  ресурс
	П1	П2
Резервы: Трудовые Материальные Финансовые Выпуск Прибыль План	1 3 6 1 4 х1	4 4 2 1 8,5 х2	14 18 27 _ _ _

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

х₁+4 × х₂ £ 14;

3 × х₁+4 × х₂ £ 18;

6 × х₁+2 × х₂ £ 27;

х₁ ³ 0; х₂ ³ 0;

Найдем оптимальные решения для пяти целевых функций:

максимизация суммарного выпуска            f ₁ = х₁+ х₂ ma х

максимизация выпуска продукции П₂   f ₂ = х₂ ma х

максимизация выпуска продукции П₁                f ₃ = х₁ ma х

максимизация прибыли                                   f ₄ =4 х₁+8,5 х₂ ma х

минимизация используемых ресурсов        f ₅ =(1+3+6) × х₁+(4+4+2) х₂ min

                                                            т.е. f₅=10 х₁+10 х₂ min

Для каждой приведенной целевой функции можно построить линию целевой функции и определить вершину, в которой целевая функция будет иметь оптимальное значение. Результаты решения задачи по пяти целевым функциям сведены в таблицу 9, из анализа которой можно сделать вывод: координаты каждой вершины могут быть оптимальным решением задачи в некотором принятом смысле.

Так, вершина С дает максимальный суммарный выпуск, вершина А – максимальный выпуск продукции П₂ и т.д.

Таблица 9

Целевая  Функция	Вершина	х1	х2	х1+ х2	Прибыль	Используе-мый ресурс
f1= х1+ х2 мах	C	4	1,5	5,5	28,75	55
f2= х2 мах	A	0	3,5	3,5	29,75	35
f3= х1 мах	D	4,5	0	4,5	18	45
f4=4х1+8,5х2 мах	B	2	3	5	33,5	50
f5=10х1+10х2 min	F	0	0	0	0	0

Рассмотрим далее, как влияет на оптимальное решение введение дополнительных ограничений. Пусть дана задача, которая графически представлена на рис 14,а

 

Рис. 14,а

Принимаем, что при максимизации оптимальное решение находится в вершине В и имеет значения х₁⁰, х₂⁰, f₀. Рассмотрим, как влияют на оптимальное решение дополнительные ограничения, например, применительно к х₁.

Таблица 10

Номер рисунка	х зад	Дополнительное ограничение	мах f
рис.14,б	х зад< х1^0	х1  х зад	f1< f0
рис.14,в	х зад< х1^0	х1  х зад	f2= f0
рис.14,г	х зад> х1^0	х1  х зад	f3< f0
рис.14,д	х зад> х ма x	х1  х зад	Нет

 

 

Из рис 14 и табл.10 видно следующее: дополнительное ограничение ухудшило целевую функцию (рис 14,б), оптимальное решение не изменилось (рис 14,в), оптимальное решение ухудшилось (рис 14,г), характерно появились несовместности (рис 14,д), которое привело к тому, что задача вообще не имеет решения.

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

Значит, если мы хотим улучшать принятую целевую функцию, т.е. результат работы, мы должны стремиться к тому, чтобы иметь как можно меньше ограничений.

2.7.   Основы анализа модели на чувствительность

Анализ моделей на чувствительность - это процесс, реализуемый после того, как оптимальное решение задачи получено. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. При таком анализе всегда рассматривается некоторая совокупность линейных оптимизационных моделей, то есть по существу, некоторая модель исследования операций. Это придает модели определенную динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение.

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

Пример 2.7.1.

Небольшая фабрика одной из фирм изготавливает два вида красок: для внутренних (I) и для наружных (E) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта A и B. Максимально возможные суточные запасы этих продуктов составляют 6 т и 8 т соответственно. Расходы продуктов A и B на 1 т соответствующих красок приведены в таблице:

 

 

Таблица11

Исходный Продукт	Расход исходного продукта на 1т краски		Мах ресурс
	Краска Е	Краска I
А	1	2	6
В	2	1	8
Оптовая цена 1 тонны краски, тыс. $	3	2

 

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску E более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки.

 Какое количество краски вида E и I должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Обозначим: х _E - суточный объем производства краски E (т).

х _I - суточный объем производства краски I (т).

При допущении независимости объемов сбыта каждой из красок общий доход f₀   равен сумме двух слагаемых 3х _E + 2х _I.

В целом математическая модель

f₀=3х _E+2х _I ® max

при ограничениях:      х _E +2х _I £ 6       (1)- на расход продукта А

2х _E+х _I £ 8       (2)- на расход продукта В

х _I -х _E £ 1          (3)- соотношение спросов на краски

х _I £ 2               (4)- спрос на краску I

х _I ³ 0; х _E ³ 0

 

Данная математическая модель является линейной, так как целевая функция f₀ и все ограничения линейны. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности.

Пропорциональность ‑ означает, что вклад каждой переменной х _I и х _E в целевую функцию f₀ и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной.

Если, например, фирма будет предоставлять потребителям скидку, продавая краску E по 2, 5 тыс. долларов за тонну при объеме закупок свыше 2 тонн, то в этом случае прямой пропорциональности между доходом фирмы и величиной х _E нет.

 

Рис. 15.

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

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

На рис.15 данная задача решена графическим методом. Максимальное значение прибыли достигается в вершине D при плане выпуска:

х_Е = (т) и х_I =  (т),

max f = 12  тыс.$

Первая задача анализа на чувствительность

Позволяет определить статус ресурсов и допустимые пределы изменения ресурсов.

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

Вернемся к рассмотренному примеру о фирме, выпускающей краски Е и I. В нашем примере связывающие ограничения (1) и (2), они лимитируют запасы исходных продуктов (ресурсов) А и В.

Если ограничение является связывающим, то логично отнести соответствующий ресурс к разряду дефицитных ресурсов, так как он используется полностью. Ресурс, с которым ассоциировано несвязывающее ограничение, следует отнести к разряду не дефицитных ресурсов, потому что часть этого ресурса остается неиспользованной.

При анализе модели на чувствительность по правым частям ограничений определяют:

1) предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение max f₀;

2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее max f₀.

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

Может возникнуть вопрос: не следует ли проанализировать, как повлияет на оптимум:

1. увеличение объема ресурсов, имеющихся в избытке.

2. сокращение объема дефицитных ресурсов.

Ответ на первый пункт очевиден, т.е. в этом случае мы сделаем избыточный ресурс еще более избыточным, что никак не повлияет на полученное ранее решение. По второму пункту покажем, что сокращение дефицитного ресурса никогда не улучшает значение целевой функции.

На рис. 16 нарисуем ограничение х _E+2х _I £ 4. В этом случае оптимальной является (1¢) вершина N, координаты вершины определяют из совместного решения:

 

х _E+2х _I = 4      х _E=4‑2х _I                   х_Е^{( N)}=4

2х _E+х _I = 8      8- 4х _I+х _I=8     х _I^{( N)}= 0         f₀(N)=12,

то есть оптимальное значение целевой функции уменьшилось с уменьшением запаса дефицитного ресурса (продукта А).

Рассмотрим теперь увеличение ресурса А, при этом прямая (1) (или отрезок СД) переместится вверх параллельно самой себе. Имеет смысл увеличить запас продукта так, чтобы прямая (1) прошла через вершину К. Большее увеличение продукта А приведет к тому, что ресурс (1) станет избыточным. В точке К ограничения (2) и (4) становятся связывающими. Оптимальное решение при этом достигается в вершине К, а ОДР становится многоугольник ОАВКЕ. Координаты вершины К:

2 ×х _E+х _I=8                                        (2)                                    

х _I=2                                                  (4)

х _E= =3 Þ К(3;2)

         f₀(К)= 3 ×х _E+2 ×х _I = 3 ×3+2 ×2= 9+4 =13.

Для определения предельного запаса ресурса А следует координаты вершины К подставить в левую часть ограничения (1). Тогда новое значение запаса продукта А равно: х _E+2 ×х _I=3+2 ×2=7, т.е. следует увеличить запас продукта А на D₁=7-6=1 (т), где 6 – это старое значение запаса продукта А.

 

Рис. 16.

Рассмотрим вопрос о целесообразности увеличения запаса дефицитного ресурса (2) (исходный продукт В). Запас продукта В следует увеличить так, чтобы прямая (2) прошла через вершину N.

Новой оптимальной вершиной становится точка N, где пересекаются прямая (1) и ось абсцисс (х _I=0) тогда

х _E+2х _I=6

х _I=0               

х _E=6

f(N)= f(6;0)=18

Для нахождения величины запаса продукта В, который гарантирует прибыль f=18 тыс.$, подставим координаты вершины N в ограничение (2):

2х _E^{( N)}+ х _I^{( N)}=2 ×6=12.

Тогда абсолютный прирост запаса продукта В: D ₂=12-8=4 (т)

Рассмотрим теперь вопрос об уменьшении правой части несвязывающих ограничений. Ограничение (4) (отрезок ВС) опускаем вниз до пересечения с оптимальной вершиной Д, так как координаты точки Д:

                                х _E^(Д)=3 ;       х _I^(Д)=1

то уменьшение спроса на краску I до величины  х_I^(Д)=  никак не повлияет на оптимальность ранее полученного решения.

Сокращение спроса:

D ₄=  – 2 =  

(знак ¢-¢ свидетельствует об уменьшении запаса ресурса).

 Сокращение спроса адекватно уменьшению представительства на рынке, посредством которого реализуется краска вида I.

Рассмотрим ограничение (3), х _E+х _I £ 1, которое представляет соотношение между спросом на краску I и спросом на краску Е. И в этом случае правую часть огранич