Системное програмирование

Допустимой  областью, изображенной на рис. 2.12, является четырехугольник FQRS. Два последних ограничения усиливают условия неотрицательности. Функция F убывает в направлении вектора

Минимальное значение функции F  = - 68 и достигается в точке R =(12, 8). Заметим, что, как и в примере разд. 1.1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является х₁= 12, х₂ = 8 с минимальным значением функции F =-68.

Иногда  задача имеет более чем одно оптимальное  решение.

Пример 2

Минимизировать  функцию F = -6х ₁ - 2х₂ 

рис. 2.13

при ограничениях х₁, х₂ ³  0,

2x₁ +4x₂ £ 9,

3x₁ + x₂ £ 6.

На рис. 2.13 четырехугольник ОАВС изображает допустимую область  = -6, = -2, и, таким образом, вектор указывает направление убывания функции F. Любая точка на отрезке ВС является оптимальным решением. В частности, в вершинах B = (l , l ) и С = (2, 0) достигаются оптимальные решения, соответствующие одному и тому же минимальному значению функции F = -12.

Любая точка на отрезке ВС представляется формулой

q( l , l ) + (l - q) (2,0) = (2 - q, l q),

где 0 £ q £ 1.

Для каждой такой точки значение функции  F равно -6(2 - q) -2(l ) = -12. Функция F имеет единственное минимальное значение.

Иногда  решение задачи не ограничено.

Пример 3

Минимизировать  функцию F = х₁ + х₂ при ограничениях х₁ ³  0, х₂ ³  0,

х₁ - х₂ ³  1,

х₂ £ 2. 

рис. 2.14

 Допустимая  область, изображенная на рис. 2.14, не ограничена в направлении, в котором функция  F возрастает, т. е. в допустимой области не существует конечной точки, в которой функция F достигала бы максимума. Решение, как и максимальное значение функции F, не ограничено. Однако некоторые задачи с неограниченными допустимыми областями имеют конечные решения. Например, задача максимизации функции _г при ограничениях из примера 3 имеет конечное решение.

Разумеется, если бы задача состояла в минимизации  функции F = х₁ + х₂ при тех же ограничениях, то минимум достигался бы в единственной точке (F (min) = 1 в вершине допустимой области х₁ = 1, х₂ = 0).

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

Пример 4

Минимизировать  функцию F = 2х₁ + 3х₂

при ограничениях х ₁, х₂ ³  0,

x₁ + х₂ ³  10,

3х₁ + 5х₂ £ 15.

Ограничения задачи противоречивы, поэтому нет  допустимых решений (рис. 1.5).

 

рис. 2.15

Пример  5. Найдите максимум и минимум линейной функции F = (-2х₁ + 4х₂)

при условиях-ограничениях:

6х₁ - 2х₂ £ 12,

- х₁ + 2х₂ £  5,

X₁ +Х₂ ³ 1,

Х₁, х₂ ³ 0.

  Решение. Построим на плоскости Х₁ОХ₂ многоугольник решений (рис. 3.1). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств, заменим на знаки точных равенств.

6х₁ - 2х₂ = 12, (1)

-х₁ + 2х₂ = 5, (2)

х₁+х₂=1, (3)

х₁ = 0, (4)

х₂ = 0. (5)

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

  Многоугольником решений задачи является пятиугольник АВСДЕ, координаты точек которого удовлетворяют  условию неотрицательности переменных и неравенствам системы ограничений задачи.

Рис. 3.1. Построение многоугольника решений

 Для нахождения точек экстремума построим начальную прямую F = -2х₁ + 4х₂ = 0 и вектор N(-2,4). Передвигая прямую F = 0 в направлении вектора N, найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значение. Так как точка С получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых:

6х₁ - 2х₂ = 12,

-х₁ + 2х₂ = 5.

  Решив систему уравнений, получим: х₁ = 3,4; х₂ = 4,2; откуда найдем максимальное значение целевой функции

F_max = - 2•3,4 + 4•4,2 = 10.

  По  условию задачи начальная прямая параллельна прямой (2), так как  коэффициенты при переменных х₁, х₂ пропорциональны: -2/—1 = 4/2 = 2. Следовательно, начальная прямая займет положение опорной прямой в точках В, С и в любой точке отрезка ВС, в которых F принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений:

   Þ 

  Максимальное  значение целевой функции в точке В равно: F = -2•0 + 4•2,5 = 10.

  Запишем множество оптимальных решений  как линейную выпуклую комбинацию углов  точек отрезка ВС:

где 0 £ a £ 1.

Подставив координаты угловых точек, получим:

= a •3,4 + (1 -a)•0 = 3,4a

= a •4,2 + (1 - a)•2,5 = 2,5 + 1,7a.

Тогда Х = {3,4a; 2,5 + 1,7a}, где 0 £ a £ 1.

  Подставляя  любые значения a от 0 до 1, получим координаты множества точек отрезка ВС, в каждой из которых целевая функция принимает максимальное значение, равное 10.

  Для нахождения минимального значения целевой  функции задачи перемещаем начальную прямую в направлении, противоположном вектору N(c_1t с₂). Начальная прямая займет положение опорной прямой в вершине Д, где x₁ = 2, х₂ = 0, а минимальное значение целевой функции равно:

F_min = -2•2 + 4•0 = -4.

Пример  6. Коммерческому отделу поручили проанализировать совместную деятельность подразделений фабрики по изготовлению и продаже двух видов краски для внутренних (В) и наружных (Н) работ, которая поступила в продажу по цене 3 тыс. тг. и 2 тыс. тг. за 1 т. Для производства красок используют два вида сырья А и В, максимально возможные суточные запасы которых составила 3 т и 4 т. Расходы сырья на производство 1 т красок приведены в табл. 2.1.

Таблица 2.1

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

  Так как модель имеет только две переменные, то данную задачу можно решить геометрическим методом.

  Построим  на плоскости Х_]ОХ₂ (рис. 3.2) многоугольник допустимых решений задачи. Для этого в неравенствах системы ограничений знаки неравенств, заменим на знаки точных равенств:

0,5х_Н + х_В £ 3, (1) 0,5х_Н + х_В = 3, (1)

х_Н + 0,5х_В £ 4, (2) х_Н + 0,5х_В = 4, (2)

х_В-х_Н £ 1,5, (3) =>       х_В - х_Н = 1,5, (3)

х_В  £ 2, (4) х_В = 2, (4)

х_Н ³ 0,25, (5) х_Н = 0,25, (5)

х_В ³ 0,5 (6) х_В = 0,5 (6)

F = 2х_Н + 3х_В F = 2х_Н + 3х_В = 0.

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

  Направление стрелок от каждой граничной прямой определяется путем непосредственной подстановки в неравенство координат произвольно взятой точки, например (0,0), и при удовлетворении данного неравенства направляем стрелки в сторону контрольной точки, в противном случае — наоборот.

Полученное  пространство решений есть многоугольник  ABCDEF.

Рис. 3.2. Построение области допустимых решений

  Угловые точки многоугольника решений имеют  следующие координаты: А(0,25; 0,5), В(0,25; 1,75), С(0,5; 2), D(2; 2), E(3'/₃; l'/з). F(3,75;0,5).

  Для нахождения минимума и максимума  целевой функции строим начальную прямую и вектор-градиент N(2; 3) (рис. 3.3). Координатами вектора N являются коэффициенты целевой функции при переменных х_H и х_B. Для построения графика целевой функции задаем произвольное значение F(Х). Если F(Х) = 0, то прямая проходит через начало координат. Для ее построения, полагая х_H = 1, получим х_B= -²/₃, а при х_B = 1, получим х_H = -³/₂ (рис. 3.3). Полагая F = 6, таким же образом построим линию целевой функции.