Пример графического решения 1 страница

Х1 0 Х1

ОДР Z А В

Z

В

ОДР А

Х1 0 Х1

Z С Z В

А ОДР ОДР А

Min – нет Max – нет

A – max Min – нет

A – min Max – нет

В – max В

A – min

Рисунок 1.1 Особенности графического решения

Существуют следующие особенности ОДР:

1. Если одно из ограничений в системе является уравнением, то ОДР вырождается в отре-зок прямой линии;

2. Совокупность неравенств, входящих в состав системы ограничений, может образовы-вать как замкнутую, так и незамкнутую ОДР.

Дана следующая математическая модель задачи линейного программирования. Z = x − 2× x 2

ì

ï

10 x + 7 x 2£ 35

í

ï x + x 2³1. (1.1)

ï

ï− x + x 2£2î x ³0 x 2 ³0

Необходимо найти минимум и максимум целевой функции Z.

Решение.

Строим ОДР. Граничные прямые проходят по точкам: 1-ая прямая – (3,5; 0) и (0; 5); 2-ая прямая – (1; 0) и (0; 1); 3-я прямая – (–2; 0) и (0; 2). Стрелками показываем полуплос-кости, которые удовлетворяют неравенствам. Также учитываем полуплоскости, отвечаю-щие требованию неотрицательности переменных (x ³ 0 x 2³ 0), т.е. ОДР ограничена пер-вым квадрантом. По совокупности полуплоскостей в первом квадранте получаем много-угольник ABCDE, который является областью допустимых решений (рис.1.2).

ì

x

.

í

Строим вектор градиента целевой функции из начала координат в точку, соответст-вующую коэффициентам целевой функции (1; –2)

1 Х2

3 5

2 3 А

2 E

1 DОДР

С B

-3 -2 -1 0 1 2 3 4 Х1 -1 Z

-2

Рисунок 1.2 Графическое решение задачи

Перпендикулярно вектору градиента проводим нормаль и определяем:

− при перемещении нормали по направлению градиента последней встретилась т.В. Следовательно, в точке В целевая функция достигает максимума;

− при перемещении нормали против направления градиента последней встретилась точка А. Следовательно, в точке А целевая функция достигает минимума.

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

Точка В лежит на оси 0 Х 1 с известными координатами: т. В (3,5; 0). Подсчитываем максимальное значение для функции цели

Z max = x 2× x 2 3,5− 2×0 3,5

Точка А лежит на пересечении прямых № 1 и 3. Следовательно, нужно решить сле-дующую систему уравнений (1.2):

10 1+ 7 x 2= 35 î− x + x 2= 2

(1.2)

r

Для этого записываем в ячейках электронных таблиц исходные данные (рис.1.3). За-тем решаем систему методом обратной матрицы. Согласно данному методу система ли-нейных алгебраических уравнений записывается в следующей форме

r

A × x = B. (1.3) Решение системы определяется так

x = A −1× B. (1.4)

Сначала с помощью функции МОБР из категории Математические в ячейках В6:С7 (рис.1.3) находим обратную матрицу А –1 коэффициентов левой части системы (1.2). Затем в ячейках Е6:Е7 находим векторно-матричное произведение обратной матрицы А –1 на зна-

чения правой части системы A −1 × с помощью функции МУМНОЖ, где первым массивом

ì

ï

í

ì

ï

í

x

ï

í

x

ï

í

x

ï

x

í

x

ï

í

ï

ï

í

x

ï

í

x

ï

x

í

ï

ï

í

ì

ï

í

ï

x

í

x

ï

x

í

ï

í

ï

í

ï

í

является обратная матрица, а вторым – вектор правой части системы линейных алгебраи-ческих уравнений.

Рисунок 1.3 Решение системы уравнений

Точка А имеет координаты (1,2353; 3,2353). Значение функции цели составляет Z min = x − 2 x 2 =1,2353 2×3.2353 = −5,2353

Вариантызаданий

№ вар.	Задачи
	7 15 29 34
	3 13 22 39
	10 11 26 33
	6 20 21 39
	9 15 24 32
	7 17 21 33
	5 16 29 34
	9 14 30 40

Задачи 1–40

1 1 1 1

Решить математическую модель графически на максимум и минимум функции цели. Z =12 x − 2 x 2 Z = 9 x −7 x 2 Z 4 x − 2 x 2 Z = 5 x − x 2

11 x −17 x 2 £ 66 1) ï− x +11 x 2 £14

x

ï

ï5 1 −3 x 2 ³ 2 î x ³ 0, x 2 ³ 0

11 x +8 x 2 £ 72 2) ï− x +11 x 2 ³ 20

x

ï

ï5 1 −3 x 2 ³ 6 î x ³ 0, x 2 ³ 0

ì1 +3 x 2 £10 3) ï4 x + 2 x 2 ³ 4

x

ï

ï5 1 −13 x 2 £17 î x ³ 0, x 2 ³ 0

ì9 1 +11 x 2 £ 46 4) ï5 x + 4 x 2 ³ 20

ï

ï− x +13 x 2 ³ 4 î x ³ 0, x 2 ³ 0

Z = x + 4 x 2 Z =11 x + 7 x 2 Z = 7 x − x 2 Z = 8 x 2 x 2

ì−8 1 +5 x 2 £18 5) ï2 1 + 4 x 2 ³1

x

ï

ï7 1 +3 x 2 £ 27 î x ³ 0, x 2 ³ 0

ì5 1 −5 x 2 ³10 6) ï x − 2 x 2 £ 4

x

ï

ï3 1 + 4 x 2 £ 20 î x ³ 0, x 2 ³ 0

ì x + 2 x 2 ³ 5 7) 8 x + 4 x 2 £ 29

x

ï

ï

8 1 −6 x 2 ³ 9 î x ³ 0, x 2 ³ 0

ì2 1 +11 x 2 ³ 7 8) ï2 x −3 x 2 £ 6

x

ï

ï6 1 −13 x 2 ³ 4 î x ³ 0, x 2 ³ 0

Z = 6 x + 4 x 2 Z = 7 x x 2 Z = 6 x 4 x 2 Z = 7 x + x 2

ì9 1+11 x 2£ 48 9) ï7 1−5 x 2³10

ï

x

ï−3 x +13 x 2³ 6 î1³ 0, x 2³ 0

ì 2 x 2£10 10) 8 x + 2 x 2³16

ï

x

8 x −6 x 2£12 ï1³ 0, x 2³ 0

12 x +8 x 2³ 48 11) ï−11 x + 6 x 2£ 44

ï

ï−3 x + 6 x 2³ 6 î x ³ 0, x 2³ 0

ì x +3 x 2³ 2 12) ï4 1− 2 x 2³ 4

ï

x

ï5 x −13 x 2£18 î1³ 0, x 2³ 0

î

Z = 3 x + 2 x 2 Z = 7 x 2 x 2 Z = −6 x − 4 x 2 Z = 7 x + x 2

ì−31+2 x 2£613) ï5 1+ 4 x 2³ 20

x

ï

x

ï21−4 x 2£4î 1 ³0, x 2 ³0

ì− 4 x + x 2£ 4 14) ï6 x +3 x 2³18

x

ï

x

ï3 1−5 x 2£ 5 î1³ 0, x 2³ 0

ì− 2 x +3 x 2£ 8 15) ï7 x +3 x 2³15

ï

ï3 x −5 x 2£ 3 î x ³ 0, x 2³ 0

ì−5 x +3 x 2£ 5 16) ï2 x + x 2³ 2

x

ï

ï1−3 x 2£ 3 î x ³ 0, x 2³ 0

x

ï

x

í

ï

x

í

ï

í

x

ï

x

í

x

ï

x

í

ì

ï

x

í

ì

ï

í

x

ï

í

x

ï

x

í

ï

x

í

ï

í

x

ï

ï

í

ì

x

ï

í

x

ï

x

í

ï

í

x

ï

í

x

ï

x

í

í

í

x

ï

x

í

ï

í

ï

ï

í

x

ï

x

í

ï

í

ï

Z = 6 x − 4 x 2 Z = 5 x 2 x 2 Z = 6 x 4 x 2 Z = 7 x −3 x 2

Дата добавления: 2014-11-25