3 Область определения систем линейных неравенств.

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

Решение задач оптимизации следует начинать с выяснения области определения системы.

1. Дано уравнение:

1) 5

2. Дано неравенство:

2)

3. Имеем математическую модель задачи в виде системы из четырех уравнений:

Вначале рассмотрим уравнение (1) и изобразим его на плоскости (смотри рисунок 7). Допустимым решением уравнения (1) является точка начала координат.

Рисунок 7 - Уравнение 5

Множеством допустимых решений неравенства (2) является выпуклое, незамкнутое множество АВС с одной угловой точкой и 1-м базисным решением А(0;3/8) (смотри рисунок 8)

Рисунок 8 - Неравенство

Множеством допустимых решений математической модели в виде системы из четырёх уравнений (3) является отрезок AB. Все точки этого отрезка удовлетворяют одновременно всем неравенствам ,(смотри рисунок 9).

Рисунок 9-Координаты точек А(0;0); В(2;0)

Решение задач планирования выпуска продукции.

Таблица 3- Исходные данные:

Ресурсы:	Вид продукции		Располагаемые ресурсы
	П1	П2
Трудовые	9	13		65
Материальные	11	12		74
Финансовые	8	11		81
Границы:
Верхняя	9	8		-
Нижняя	1	-		-
Прибыль	5	2		-

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

F₁ = 5Х₁ + 2Х₂ max

Математическая модель задачи принимает вид системы неравенств:

1) 9Х₁ + 13Х₂ 65; 4) Х₁ 9

2) 11Х₁ + 12Х₂ 74; 5) Х₂ 8

3) 8Х₁ + 11Х₂ 81; 6) Х₁ 1

Определим графически множество решений каждого неравенства этой системы.

1) Х₁ = 0 Х₂ 5; 3) Х₁ = 0 Х₂ 81/11;

Х₂ = 0 Х₁ 65/9; Х₂ = 0 Х₁ 81/8;

2) Х₁ = 0 Х₂ 37/6; 4) Х₁ 9;

Х₂ = 0 Х₁ 74/11; 5) Х₂ 8

6) Х₁ 1

Область определения системы представляет собой многоугольник АBCD с четырьмя угловыми точками, соответствующими пяти базисным решениям А(1;0) ; В(1;4,3); С(5,2;1,4) ; D(6,72;0) (смотри рисунок 10).

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

1. Целевая функция вида: F₁ = 5Х₁ + 2Х₂ max

Решением задачи является самая удаленная точка, это точка D.

Решение: Х₁ =6,72; Х₂ = 0;

Тогда F₁ = 6,72·5 + 0·2 = 33,6.

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

9·6,72+ 13·0 = 60,48; 11·6,72 + 12·0= 73,92; 8·6,72 + 11·0 = 53,76;

2. Целевая функция вида: F₂ = Х₁ max

Максимуму функции соответствует наиболее удаленная точка D с координатами Х₁ = 6,72; Х₂ = 0;

3. Целевая функция вида: F₃ = Х₂ max

Соответствующая прямая, расположенная в начале ординат, будет совпадать с осью Х₂. Решением задачи является наиболее удаленная точка B с координатами Х₁ = 1; Х₂ = 4,3

4. Целевая функция вида: F₄= Х₁ + Х₂ max

Решением задачи является наиболее удаленная точка B с координатами Х₁ = 1 и Х₂ = 4,3;

5. Целевая функция вида: F₅= 9Х₁ + 13Х₂ min

Решением задачи является наиболее удаленная точка A с координатами Х₁ = 1 и Х₂ = 0;

Результаты оптимальных решений для каждого из представленных вариантов приведены в таблице 4

Таблица 4 - Результаты расчётов

Целевая функция	Угловая точка	Число продуктов		Значе- ние целевой функции	Прибыль	Расход
		Х1	Х2			Трудовые	Материальные	Финансо- вые
F1	D	6,72	0	33,6	33,6	60,48	73,92	53,76
F2	D	6,72	0	6,72	33,6	60,48	73,92	53,76
F3	B	1	4,3	4,3	13,6	64,9	62,6	55,3
F4	B	1	4,3	5,3	13,6	64,9	62,6	55,3
F5	А	1	0	9	5	9	11	8