Основы систем автоматизированного проектирования (стр. 6 из 6)
Для базисных переменных оценки всегда равны нулю.
Значение критерия для данного начального базиса будет равно нулю:
L=åciai0=0*2+0*6=0;
Так как имеются Dj<0 приступаем к улучшению плана.
Первая итерация
В базис вводим вектор A1, которому соответствует минимальное значение Dj. Из базиса выводим вектор A3, так как минимальное q достигается при i=3.
Таким образом, элемент a31 будет направляющим (в таблице выделен зеленым цветом).
Заполняем таблицу, соответствующую новому базисному решению.
Все элементы aijтаблицы определяются по следущему рекуррентному соотношению:
где akr- направляющий элемент, l– номер итерации
| Табл. 1 | 0 | 3 | 2 | 0 | 0 | q | ||
| i | Csi | базис | A0 | A1 | A2 | A3 | A4 | |
| 1 | 3 | A1 | 2 | 1 | -1 | 1 | 0 | – |
| 2 | 0 | A4 | 2 | 0 | 3 | -2 | 1 | 2/3Ümin |
| D | 6 | 0 | -5 | 3 | 0 | |||
| Z | 6 | 3 | -3 | 3 | 0 | |||
| Ýmin | ||||||||
Приведем расчет нескольких элементов таблицы:
Элемент a42=3 является направляющим (в таблице выделен зеленым цветом).
Так как в строке оценок полученного нового плана имеется отрицательное значение Dj, приступаем ко второй итерации, продолжая улучшать план.
Вторая итерация
| Табл. 2 | 0 | 3 | 2 | 0 | 0 | q | ||
| i | Csi | базис | A0 | A1 | A2 | A3 | A4 | |
| 1 | 3 | A1 | 8/3 | 1 | 0 | 1/3 | 1/3 | 8 |
| 2 | 2 | A2 | 2/3 | 0 | 1 | -2/3 | 1/3 | – |
| D | 28/3 | 0 | 0 | -1/3 | 5/3 | |||
| Z | 28/3 | 3 | 2 | -1/3 | 5/3 | |||
| Ýmin | ||||||||
Элемент a13 =1/3 является направляющим (в таблице выделен зеленым цветом).
Третья итерация
| Табл. 3 | 0 | 3 | 2 | 0 | 0 | ||
| i | Csi | базис | A0 | A1 | A2 | A3 | A4 |
| 1 | 0 | A3 | 8 | 3 | 0 | 1 | 1 |
| 2 | 2 | A4 | 6 | 2 | 1 | 0 | 1 |
| D | 12 | 1 | 0 | 0 | 2 | ||
| Z | 12 | 4 | 2 | 0 | 2 | ||
Поскольку все 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, решаем полученную задачу с помощью табличного симплекс-метода.
Если в оптимальном решении такой задачи нет искусственных переменных, это и есть оптимальное решение исходной задачи.
Если же в оптимальном решении данной задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача не разрешима.
| Табл 0 | 0 | 2 | 3 | -5 | 0 | 0 | -M | -M | -M | q | |
| 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 | 2Ümin |
| D | -21M | -4M-2 | -7M-3 | 5 | M | M | 0 | 0 | 0 | ||
| Ýmin |
Элемент a82=4 является направляющим (в таблице выделен зеленым цветом).
Столбцы, соответствующие искусственным переменным по мере вывода из базиса из расчета исключаются.
| Табл 1 | 0 | 2 | 3 | -5 | 0 | 0 | -M | -M | q | |
| Csi | базис | A0 | A1 | A2 | A3 | A4 | A5 | A6 | A7 | |
| -M | A6 | 5 | 7/4 | 0 | -1 | -1 | 0 | 1 | 0 | 20/7Ümin |
| -M | A7 | 2 | 1/2 | 0 | 1 | 0 | -1 | 0 | 1 | 4 |
| 3 | A2 | 2 | 1/4 | 1 | 0 | 0 | 0 | 0 | 0 | 8 |
| D | -7M+6 | -9М/4–3/4 | 0 | M+5 | M | M | 0 | 0 | ||
| Ýmin |
Элемент a61=7/4 является направляющим (в таблице выделен зеленым цветом).
| Табл 2 | 0 | 2 | 3 | -5 | 0 | 0 | -M | q | |
| 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/9Ümin |
| 3 | A2 | 9/ 7 | 0 | 1 | 1/ 7 | 1/ 7 | 0 | 0 | 9 |
| D | -4M/ 7+67/ 7 | 0 | 0 | -9M/ 7+30/ 7 | 2M/ 7-5/ 7 | M | 0 | ||
| Ýmin |
Направляющий элемент a73=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 |
| D | 23/3 | 0 | 0 | 0 | 23/9 | 30/9 |
Найдено оптимальное решение, так как все оценки неотрицательные и в базисе нет искусственных переменных:
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 с.