Завдання лінійного програмування

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

Завдання лінійного програмування

Контрольная работа

Компьютеры, программирование

Другие контрольные работы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией
анні максимуму (мінімуму) функції. Якщо так, то завдання не має рішення.

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

Симплекс-метод гарантує закінчення процесу пошуку оптимального рішення завдання лінійного програмування або після виконання пункту 1, або пункту 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

ЗміннаВільний членВільна зміннаX1X2Y11513Y22531F0-5-6

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

 

Таблиця 1

ЗміннаВільний членВільна зміннаX1X2Y115

51

1/33

1/3Y225

-25/33

-1/31

-1/3F0

30-5

2-6

2

  1. Обчислюємо зворотну величину λ=1/ан= 1/3 заносимо в нижній правий кут осередку.
  2. Всі елементи дозволеного рядка крім дозволеного елементу множимо на λ і результат записуємо в нижній правий кут осередків.
  3. Всі елементи дозволеного стовпця крім дозволеного множеннимо на -λ і заносимо в нижній кут осередків. Підкреслимо отримані (нижні) числа в дозволеному стовбці й верхні числа в дозволеному рядку.
  4. Запис у правому нижньому куті осередків таблиці 1

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

  1. Переписуємо таблицю 1 з урахуванням заміни x2 на y1 у таблицю 2.

 

Таблиця 2

ЗміннаВільний членВільна зміннаX1Y1X25

151/3

31/3

1Y250/3

-1208/3

-8-1/3

-8F30

45-3

92

9

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

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

 

Таблиця 3

ЗміннаВільний членВільна зміннаX2Y1X11531Y2310/3-8-25/3F75911

Получаємо

 

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 с.

Похожие работы

< 1 2