Завдання лінійного програмування (стр. 2 из 2)
Припустимо, що обмеження завдання зведені до такого виду, що в матриці Ає одинична підматриця й всі вільні члени позитивні. Іншими словами, нехай матриця обмежень має вигляд
A1x1+.+Anxn+e1xn+e1xn+1+.+emxn+m=A0=[ai0], (1.3)
Перетворення Гауса називають симплексним перетворенням, коли напрямний (базисний) елемент визначають за наступними правилами:
a) напрямний стовпець jвибирають із умови, що в ньому є хоча б один позитивний елемент;
б) напрямний рядок івибирають так, щоб відношення було мінімально за умови що aij>0
При такому перетворенні в базис вводиться вектор Aj і виводиться вектор Аi. Тепер треба визначити, як вибрати вектор, що вводить у базис, щоб при цьому значення цільової функції збільшилося.
Для цього використають так називані оцінки векторів:
(1.4)
де Iб – множина індексів базисних векторів;
xij- визначають із умови
(1.5)
Величини {∆j } рівні симплекс-різницям для змінних {xj} із протилежним знаком. Отже, для того щоб значення цільової функції збільшилося, необхідно вибрати напрямний стовпець Аj з найбільшою по модулі негативною оцінкою, тобто
(1.6)
Для рішення завдання симплексом-методом на кожній ітерації заповнюють симплекс-таблицю.
5. Приклад 2
Вирішимо отримане двовимірне завдання лінійного програмування за допомогою симплекс-таблиць:Цільова функція F(x)=5x1+6x2 → min
Обмеженняx1+3x2≥15, 3x1+x2≥25
Складемо першу симплекс-таблицю.
У верхніх частинах осередків запишемо коефіцієнт цільової функції й обмежень:
Таблиця 1
| Змінна | Вільний член | Вільна змінна | |
| X1 | X2 | ||
| Y1 | 15 | 1 | 3 |
| Y2 | 25 | 3 | 1 |
| F | 0 | -5 | -6 |
1. Вибираємо стоку в таблиці один з негативним вільнимчленом, потім стовпець при вільній змінній з негативним членом. Якщо їх декілька то з них потрібно вибрати той елемент який дає мінімальне відношення до вільного члена. Цей елемент називається дозволеним. Він позначає дозволений рядок і стовпець у таблиці в якій перебувати замінні змінні;
Таблиця 1’
| Змінна | Вільний член | Вільна змінна | |
| X1 | X2 | ||
| Y1 | 155 | 11/3 | 31/3 |
| Y2 | 25-25/3 | 3-1/3 | 1-1/3 |
| F | 0 30 | -52 | -62 |
2. Обчислюємо зворотну величину λ=1/ан= 1/3 заносимо внижній правий кут осередку.
3. Всі елементи дозволеного рядка крім дозволеного елементу множимо на λ і результат записуємо в нижній правий кут осередків.
4. Всі елементи дозволеного стовпця крім дозволеного множеннимо на -λ і заносимо в нижній кут осередків. Підкреслимо отримані (нижні) числа в дозволеному стовбці й верхні числа в дозволеному рядку.
5. Запис у правому нижньому куті осередків таблиці 1
проводиться під позначеними рисою числами які перебувають в рядку й стовпці в якій перебуває розглянутий осередок.
6. Переписуємо таблицю 1’ з урахуванням заміни x2 на y1 у таблицю 2.
Таблиця 2’
| Змінна | Вільний член | Вільна змінна | |
| X1 | Y1 | ||
| X2 | 515 | 1/33 | 1/31 |
| Y2 | 50/3-120 | 8/3-8 | -1/3-8 |
| F | 30 45 | -39 | 29 |
Елементи дозволеного рядка й стовпців заповнюються числами відповідно таблиці, що знаходиться в правому нижньому куті таблиці 1. Всі інші осередки таблиці 2 заповнюємо числами представленими сумою чисел записаних у нижньому й верхньому кутах таблиці1.
1. Аналізуючи таблицю 2’ встановлюємо, що один з коефіцієнтів цільової функції позитивний, а один негативний, що вказує на відсутність оптимальних рішень завдання. Продовжуємо заміну змінних, щоб знайти рішення. У даному прикладі послідовний елемент позитивний у стовпці один. Це дозволений стовпець. Дозволений рядок, той в якому мінімальна частка вільного члена й позитивного числа дозволеного стовпця.
Таблиця 3
| Змінна | Вільний член | Вільна змінна | |
| X2 | Y1 | ||
| X1 | 15 | 3 | 1 |
| Y2 | 310/3 | -8 | -25/3 |
| F | 75 | 9 | 11 |
Получаємо
x1=15
x2=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 с.