Табличний симплекс-метод

4. Табличний симплекс-метод

Основна ідея симплекс-методу складається в переході від одного припустимого базисного рішення до іншого таким чином, що значення цільової функції при цьому безупинно зростають (для завдань максимізації).

Послідовність рішення симплексом-методом наступна:

1.За певним правилом знаходимо будь яку вершину, що належить множині припустимих рішень. Перевіряємо, чи не відповідає дана вершина оптимальному значенню цільової функції. Якщо так, то завдання вирішене.

2.Якщо завдання не вирішене, то за певним правилом перевіряємо, чи не можна на даному кроці затверджувати, що цільова функція не обмежена зверху (знизу) на множині припустимих рішень при відшуканні максимуму (мінімуму) функції. Якщо так, то завдання не має рішення.

3. Якщо завдання має рішення, то за певним правилом знаходимо нову вершину, у якій цільова функція має більш оптимальне значення. Далі рішення здійснюємо відповідно до пункту 1, приймаючи в якості вихідної знову обрану вершину.

Симплекс-метод гарантує закінчення процесу пошуку оптимального рішення завдання лінійного програмування або після виконання пункту 1, або пункту 2 за кінцеве число кроків (ітерацій), тому що при цьому здійснюється послідовний оптимальний перехід від даної, розглянутої на кожному кроці, вершини до кращого.

Припустимо, що обмеження завдання зведені до такого виду, що в матриці А є одинична підматриця й всі вільні члени позитивні. Іншими словами, нехай матриця обмежень має вигляд

A₁x₁+.+A_nx_n+e₁x_n+e₁x_n+1+.+e_mx_n+m=A₀=[a_i0], (1.3)

Перетворення Гауса називають симплексним перетворенням, коли напрямний (базисний) елемент визначають за наступними правилами:

a) напрямний стовпець j вибирають із умови, що в ньому є хоча б один позитивний елемент;

б) напрямний рядок івибирають так, щоб відношення було мінімально за умови що a_ij>0

При такому перетворенні в базис вводиться вектор A_j і виводиться вектор А_i. Тепер треба визначити, як вибрати вектор, що вводить у базис, щоб при цьому значення цільової функції збільшилося.

Для цього використають так називані оцінки векторів:

 (1.4)

де I_б – множина індексів базисних векторів;

x_ij- визначають із умови

 (1.5)

Величини {∆_j } рівні симплекс-різницям для змінних {x_j} із протилежним знаком. Отже, для того щоб значення цільової функції збільшилося, необхідно вибрати напрямний стовпець А_j з найбільшою по модулі негативною оцінкою, тобто

 (1.6)

Для рішення завдання симплексом-методом на кожній ітерації заповнюють симплекс-таблицю.

5. Приклад 2

Вирішимо отримане двовимірне завдання лінійного програмування за допомогою симплекс-таблиць: Цільова функція F(x)=5x₁+6x₂ → min

Обмеження x₁+3x₂≥15, 3x₁+x₂≥25

Складемо першу симплекс-таблицю.

У верхніх частинах осередків запишемо коефіцієнт цільової функції й обмежень:

Таблиця 1

Змінна	Вільний член	Вільна змінна
		X1	X2
Y1	15	1	3
Y2	25	3	1
F	0	-5	-6

1.  Вибираємо стоку в таблиці один з негативним вільним членом, потім стовпець при вільній змінній з негативним членом. Якщо їх декілька то з них потрібно вибрати той елемент який дає мінімальне відношення до вільного члена. Цей елемент називається дозволеним. Він позначає дозволений рядок і стовпець у таблиці в якій перебувати замінні змінні;

Таблиця 1’

Змінна	Вільний член	Вільна змінна
		X1	X2
Y1	15 5	1 1/3	3 1/3
Y2	25 -25/3	3 -1/3	1 -1/3
F	0 30	-5 2	-6 2

2.  Обчислюємо зворотну величину λ=1/а_н= 1/3 заносимо в нижній правий кут осередку.

3.  Всі елементи дозволеного рядка крім дозволеного елементу множимо на λ і результат записуємо в нижній правий кут осередків.

4.  Всі елементи дозволеного стовпця крім дозволеного множеннимо на -λ і заносимо в нижній кут осередків. Підкреслимо отримані (нижні) числа в дозволеному стовбці й верхні числа в дозволеному рядку.

5.  Запис у правому нижньому куті осередків таблиці 1

проводиться під позначеними рисою числами які перебувають в рядку й стовпці в якій перебуває розглянутий осередок.

6.  Переписуємо таблицю 1’ з урахуванням заміни x₂ на y₁ у таблицю 2.

Таблиця 2’

Змінна	Вільний член	Вільна змінна
		X1	Y1
X2	5 15	1/3 3	1/3 1
Y2	50/3 -120	8/3 -8	-1/3 -8
F	30 45	-3 9	2 9

Елементи дозволеного рядка й стовпців заповнюються числами відповідно таблиці, що знаходиться в правому нижньому куті таблиці 1. Всі інші осередки таблиці 2 заповнюємо числами представленими сумою чисел записаних у нижньому й верхньому кутах таблиці1.

1.  Аналізуючи таблицю 2’ встановлюємо, що один з коефіцієнтів цільової функції позитивний, а один негативний, що вказує на відсутність оптимальних рішень завдання. Продовжуємо заміну змінних, щоб знайти рішення. У даному прикладі послідовний елемент позитивний у стовпці один. Це дозволений стовпець. Дозволений рядок, той в якому мінімальна частка вільного члена й позитивного числа дозволеного стовпця.

Таблиця 3

Змінна	Вільний член	Вільна змінна
		X2	Y1
X1	15	3	1
Y2	310/3	-8	-25/3
F	75	9	11

Получаємо

x₁=15

x₂=0

F(x)=5*15+6*0=75

Література

1. Системы автоматизированного проектирования. В 9-ти кн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.

2. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. Учебное пособие для вузов. - М.: Высш. шк., 1986.

3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.

4. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

5.Системы автоматизированного проектирования в радиоэлектронике. Справочник. М.: Радио и связь, 1986.

6. Погребной В.К. О декомпозиции графов на классы изоморфных подграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд. ТГУ, 1979, с. 82-96.

7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. - 295 с.

8. Ильин В.Н.. Основы автоматизации схемотехнического проектирования. Г.: Энергия, 1979. - 392 с.

9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во «Наука», 1966. - 664 с.

10.Разевиг В.Д. Система сквозного проектирования электронных устройств DesignLab 8.0.- М.: Изд-во «Солон»,1999. - 698 с.