126046 (690845), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

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

Пример: Найти максимум функции

L=2x₁+3x₂-5x₃;

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

2x₁+x₂-x₃7,

x₁+2x₂+x₃6,

x₁+4x₂=8,

x_j0

Вводим в систему три искусственные переменные: x₆, x_7, x₈, позволяющие получить начальный базис.

Для исключения из базиса этих переменных последние вводятся в целевую функцию с большим отрицательным коэффициентом М (в задаче минимизации – с положительным М)

L=LM*x₆M*x₇M*x₈max

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

2x₁+x₂x₃x₄+x₆=7,

x₁+2x₂+x₃x₅+x₇=6,

x₁+4x₂+x₈=8,

x_j0

Выбрав в качестве начального базиса векторы A_6, A₇, A₈, решаем полученную задачу с помощью табличного симплекс-метода.

Если в оптимальном решении такой задачи нет искусственных переменных, это и есть оптимальное решение исходной задачи.

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

Табл 0		0	2	3	-5	0	0	-M	-M	-M
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7	A8
-M	A6	7	2	1	-1	-1	0	1	0	0	7
-M	A7	6	1	2	1	0	-1	0	1	0	3
-M	A8	8	1	4	0	0	0	0	0	1	2min
		-21M	-4M -2	-7M -3	5	M	M	0	0	0
				min

Элемент a₈₂=4 является направляющим (в таблице выделен зеленым цветом).

Столбцы, соответствующие искусственным переменным по мере вывода из базиса из расчета исключаются.

Табл 1		0	2	3	-5	0	0	-M	-M
Csi	базис	A0	A1	A2	A3	A4	A5	A6	A7
-M	A6	5	7/4	0	-1	-1	0	1	0	20/7min
-M	A7	2	1/2	0	1	0	-1	0	1	4
3	A2	2	1/4	1	0	0	0	0	0	8
		-7M+6	-9М/4–3/4	0	M+5	M	M	0	0
			min

Элемент a₆₁=7/4 является направляющим (в таблице выделен зеленым цветом).

Табл 2		0	2	3	-5	0	0	-M
Csi	базис	A0	A1	A2	A3	A4	A5	A6
2	A1	20/ 7	1	0	-4/ 7	-4/ 7	0	0	–
-M	A7	4/ 7	0	0	9/ 7	2/ 7	-1	1	4/9min
3	A2	9/ 7	0	1	1/ 7	1/ 7	0	0	9
		-4M/ 7 +67/ 7	0	0	-9M/ 7 +30/ 7	2M/ 7 -5/ 7	M	0
					min

Направляющий элемент a₇₃=9/ 7 (в таблице выделен зеленым цветом).

Табл 3		0	2	3	-5	0	0
Csi	базис	A0	A1	A2	A3	A4	A5
2	A1	28/9	1	0	0	0	-4/9
-5	A3	4/9	0	0	1	2/9	-7/9
3	A2	11/9	0	1	0	-1/9	1/9
		23/3	0	0	0	23/9	30/9

Найдено оптимальное решение, так как все оценки неотрицательные и в базисе нет искусственных переменных:

x₁=28/9, x₂=11/9, x₃=4/9, x₄=0, L=23/3.

Список литературы

1. Разработка САПР. В 10 кн. Под ред. А.В. Петрова – М.: Высш. шк., 1990.

2. Системы автоматизированного проектирования: Учебн. пособие для ВУЗов: В 9 кн. / Под ред. И.П. Норенкова. – М.: Высш. шк., 1986. – 159 с.

3. Основы построения систем автоматизированного проектирования / А.И. Петренко, О.И. Семенков. – 2-е изд., стер. – К.: Вища шк. Головное изд-во, 1985 – 294 с.

4. Справочник по САПР/ А.П. Будя, А.Е. Кононюк, К.П. Куценко и др.; Под ред. В.И. Скурихина. – К.: Техника, 1988. – 375 с.

5. Вермишев Ю.Х. Основы автоматизации проектирования. – М.: Радио и связь, 1988 – 288 с.

6. САПР изделий и технологических процессов в машиностроении / Р.А. Аллик, В.И. Бородянский, А.Г. Бурин и др. Под общ. ред. Р.А. Аллика. – Л.: Машиностроение, 1986. – 319 с.

7. Бойко В.В., Савинков В.М. Проектирование баз данных информационных систем. 2-е изд., перераб. и доп. – М.: Финансы и статистика, 1989. – 351 с.

8. Грувер М., Зиммерс Э. САПР и автоматизация производства: Пер. с англ. – М.: Мир, 1987. – 528 с.

9. Гардан И., Люка М. Машинная графика и автоматизация конструирования: Пер. с франц. – М.: Мир, 1987. – 272 с., ил.

10. Корячко В.П. и др. Теоретические основы САПР: Учебник для ВУЗов. – М.: Энергоатомиздат, 1987. – 400 с., ил.

11. Робототехника и гибкие автоматизированные производства. В 9 кн. Учебное пособие для ВУЗов / Ю.М. Соломинцев и др. Под ред. И.М. Макарова. – М.: Высш. шк., 1986.

12. Хирн Д., Бейкер М. Микропроцессорная графика: Пер. с англ. – М.: Мир, 1987. – 352 с.

Характеристики

Список файлов курсовой работы