Основы систем автоматизированного проектирования

Поскольку все Dj³0, то план представленный в данной таблице будет оптимальным.

Ответ: x1 =0; x2=6; x3=8; x4=0; L=12;

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

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

L=2x1+3x2-5x3;

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

2x1+x2-x3³7,

x1+2x2+x3³6,

x1+4x2=8,

xj³0

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

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

L¢=L-M*x6-M*x7-M*x8®max

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

2x1+x2-x3-x4+x6=7,

x1+2x2+x3-x5+x7=6,

x1+4x2+x8=8,

xj³0

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

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

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

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

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

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

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

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

x1=28/9, x2=11/9, x3=4/9, x4=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 с.