Міністерство освіти і науки України
Дніпропетровський Національний Університет
Факультет електроніки, телекомунікацій та комп'ютерних систем
Кафедра АСОІ
Розрахункова завдання № 3
«Дослідження математичних операцій»
Виконав:
Ст. групи РС-05
Перевірив:
Доцент кафедри АСОІ
Саликов В.А.
м. Дніпропетровськ
2007р.
Умова задачі
Рішення завдання
r = R 1 + R 2 + ... R i ;
min = Min (r);
R i = 1,2, ....
Отримане на 1 етапі оптимальне базисне рішення використовується в якості початкового рішення вихідної задачі.
Основні етапи реалізації двоетапного методу (як і інших методів штучного базису) такі:
1. Будується штучний базис. Знаходиться початкова неприпустиме рішення. Виконується перехід від початкового неприпустимого рішення до деякого допустимому рішенню. Цей перехід реалізується шляхом мінімізації (зведення до нуля) штучної цільової функції, що представляє собою суму штучних змінних.
2. Виконується перехід від початкового допустимого рішення до оптимального рішення.
Всі обмеження потрібно перетворити в рівності. Для цього в обмеження «більше або дорівнює» (перше і друге) необхідно ввести надлишкові змінні. В обмеження «менше або дорівнює» (четверте) додається залишкова змінна. В обмеження «дорівнює» не потрібно вводити ніяких додаткових змінних. Крім того, потрібно перейти до цільової функції, що підлягає максимізації. Для цього цільова функція Е множиться на -1. Математична модель задачі в стандартній формі має такий вигляд:
Перший етап (пошук допустимого рішення)
1. У всі обмеження, де немає базисних змінних, вводяться штучні базисні змінні.
Примітка. Штучна цільова функція завжди (в будь-якій задачі) підлягає мінімізації.
2 штучних цільова функція виражається через небазисних змінні. Для цього спочатку потрібно висловити штучні змінні через небазисних:
3 Для приведення всієї завдання до стандартної форми виконується перехід до штучної цільової функції, що підлягає максимізації. Для цього вона помножується на -1:
4.Определяется початкове рішення. Всі вихідні, а також надлишкові змінні завдання є небазисних, тобто приймаються рівними нулю. Штучні, а також залишкові змінні утворюють початковий базис: вони рівні правим частинам обмежень.
5 складає вихідна симплекс-таблиця. Вона відрізняється від симплекс-таблиці, використовуваної для звичайного симплекс-методу тільки тим, що в неї додається рядок штучної цільової функції. У цьому рядку зазначаються коефіцієнти штучної цільової функції (приведеної до стандартної форми, тобто підлягає максимізації) із зворотними знаками, як і для звичайної цільової функції.
6.Виполняется перехід від початкового неприпустимого рішення, що міститься у вихідній симплекс-таблице, до деякого допустимому рішенню. Для цього за допомогою звичайних процедур симплекс-метода виконується мінімізація штучної цільової функції. При цьому змінні, що включаються в базис, вибираються за рядком штучної цільової функції. Всі інші дії виконуються точно так само, як в звичайному симплекс-методі. В результаті мінімізації штучна цільова функція - повинна прийняти нульове значення. Всі штучні змінні при цьому також стають рівними нулю (виключаються з базису), так як штучна цільова функція являє собою їх суму.
Двоетапний метод
1 крок
2 крок
, Де
В ході перетворень маємо:
Будуємо симплекс таблицю:
Ітерація 0
Базис | | | | |