Лекция 2

РЕШЕНИЕЗАДАЧИ ЛП ГРАФИЧЕСКИМ СПОСОБОМ

Область

Допустимых

решений

Направление

градиента

Целевая

функция

11

РЕШЕНИЕЗАДАЧИ ЛП ГРАФИЧЕСКИМ СПОСОБОМ

Область

Допустимых

решений

Целевая Направление функция градиента

12

РЕШЕНИЕЗАДАЧИ ЛП ГРАФИЧЕСКИМ СПОСОБОМ

		ОТВЕТ:
		Корма 1-го вида –
	Область	22,5 кг.,
		корма 2-го вида –
	Допустимых
		48 кг.
	решений
		Стоимость
		составит 301 руб.

Х2 ≈ 48 кг.

Целевая

функция

Х1 ≈ 22,5 кг.

13

АЛГОРИТМ ГРАФИЧЕСКОГО СПОСОБА РЕШЕНИЯЗАДАЧИ ЛП

•Формализованное описание задачи (переход от словесного описания к формулам);

•Преобразование формул к виду, удобному для построения графиков(выражаем одну переменную через другую);

•Строим графики ограничений и находим область допустимыхрешений;

•Подбираем вручную значение целевой функции, чтобы ее графиккоснулся области допустимыхрешений в зависимости отзадания: min или max;

•Находим значения переменных;

•Определяем границы устойчивостиполученного решения.

14

	РЕЗУЛЬТАТЫ РЕШЕНИЯ ЗАДАЧИ ЛП
60				•	не иметь ни одного оптимального решения
						– допустимойобластине существует– система
30
						ограниченийне совместна
40							z= max(x1+x2|x1+5x2 1, x1+x2 5, x1 0, x2 0)
20
x2 x2
						– допустимаяобластьсуществует,но не
10
20						ограничиваетцелевую функцию
0	10	20	30		40	50	z= max(2x		+x	|0.1x +0.1x 5, x		1	0, x	2	0)
							60	1	2	1	2
5500	20		40	•	60
4.6746.67		x1	x1		иметьодно оптимальное решение
4.33							z= max(x1+x2|0.1x1+0.2x2 5, x1 0, x2 0)
43.33
440
3. 7
36.67							x1=50,x2 =0;z = 50
3. 3
33.33
330
				•	иметьбесконечно много оптимальных решений
22.67.67
x2
22.33.33							z= max(x1+x2|0.1x1+0.1x2 5, x1 0, x2 0)
220
1.167.67
11.33.33							x1=50,x2 =0;z = 50 … x1=0, x2 =50;z = 50
110
0.6.677
0.3.333
000.3.3033.6.767110113.331.3316.67.6722022.33.3322.67.67330333.33.333.67.6744044.334.334.67.67550															15
		x1x1

РЕШЕНИЕЗАДАЧИ ЛП В НАДСТРОЙКЕ MS EXCEL «ПОИСК РЕШЕНИЯ»

5x1 4x2 min

5x1 3x2 2552.5x1 3x2 150x1 3.3x2 180

16

НАСТРОЙКА «ПАКЕТА АНАЛИЗА»

В Word 2003:

Сервис – Надстройки – Поиск решения

В Word 2007 и

выше:

Кнопка Office –

Параметры Excel – Надстройки – Поиск решения

17

РЕЗУЛЬТАТЫ РЕШЕНИЯ ЗАДАЧИ В НАДСТРОЙКЕ MS EXCEL «ПАКЕТ АНАЛИЗА»

	Количество	Количество	Стоимость	Количество	Количество
	корма 1-го	корма 2-го
			кормов	элемента А	элемента В
	вида	вида

Количество элемента С

Отчеты будут рассмотрены позже

18

ФОРМУЛИРОВКА ЗАДАЧИ О ДИЕТЕ (РАЦИОНЕ,СМЕСЯХ) В ОБЩЕМ ВИДЕ:

Составить дневной рацион из n видов продуктов в количестве xj (j = 1, 2, …, n), стоимостью сj каждый. Содержание пищевых элементов i= 1, 2, …, m в дневном рационе должно быть не меньше bi. В единице каждого j–го продукта содержится aij единиц i-го пищевого элемента.

Содержание пищевых элементов в рационе должно удовлетворять следующим

условиям:		a12x2					a1nxn b1
a11x1
		a22x2					a2nxn b2
a21x1
............................................
a	x a		m2	x	2	...	a	mn	x	n	b
	m1 1										m
x1 0 x2 0									xn 0

Целевая функция принимает минимальное значение:

F c1x1 c2x2 ... cnxn min

19

РАЗЛИЧНЫЕ ФОРМЫ ЗАПИСИ ЗАДАЧИ ЛП

F c1x1 c2x2 cnxn max(min)

	a11x1 a12 x2	a1n xn{ , , }b1	Развернутая
	a21x1 a22 x2	a2n xn{ , , }b2	формазаписи
			задачиЛП.
		amn xn{ , , }bm
am1 x1 am2 x2
	xj 0,	j 1,2...n

	Стандартнаяматричная	max (min) cx
		Ax { , , } b
	формазаписи задачи ЛП.
		x 0

20