Симплекс-метод розв’язку задач лінійного програмування. Лабораторна робота з Методи оптимізації та дослідження операцій. Робота № 522983

Перехід до торгівельного партнера Binance

Симплекс-метод розв’язку задач лінійного програмування

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Інститут комп’ютерних наук та інформаційних технологій

Факультет:

Не вказано

Кафедра:

Кафедра автоматизованих систем управління

Інформація про роботу

Рік:

2007

Тип роботи:

Лабораторна робота

Предмет:

Методи оптимізації та дослідження операцій

Група:

ВП

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління Симплекс-метод розв’язку задач лінійного програмування Лабораторна робота № 3, 4 з дисципліни " Методи оптимізації та дослідження операцій" Львів –2007 Лабораторна робота №3 Симплекс-метод розв’язку задач лінійного програмування Мета роботи: набуття навиків розв’язку задачі лінійного програмування симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel Порядок роботи: Заповнити початкову симплекс-таблицю задачі лінійного програмування згідно заданого варіанту. Використовуючи засоби роботи з адресацією Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування. Знайти максимальне та мінімальне значення цільової функції та оптимальний розвязок. Проінтерпретувати отримані результати для вихідної задачі. Оформити звіт для захисту лабораторної роботи за зразком назва роботи мета роботи порядок роботи короткі теоретичні відомості алгоритм розв’язку задачі малюнки відповідних таблиць аналіз отриманих результатів та висновки Короткі теоретичні відомості Симплекс-метод розв’язку задач лінійного програмування Симлекс-метод, відомий також як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, при тому так, що значення цільової функції зростають. У результаті, оптимальне розв’язок знаходиться за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також встановити, чи може бути задача лінійного програмування розв’язаною, взагалі. Методикою, яка найкраще піддається формалізації і алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць. Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, а всі вільні члени додатні: Ap = [A1, ..., An, e1, ..., em, A0]. (1) До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення . Тоді, алгоритм розв’язку задачі лінійного програмування (задачі максимізації) методом симплекс-таблиць складатиметься з наступних кроків: 1. Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді C c1 C2 c3 . . . cj . . . cn Bx ai0 A1 A2 A3 . . . Aj . . . An c1 x1 a10 A11 a12 a13 . . . a1j . . . a1n c2 x2 a20 A21 a22 a23 . . . a2j . . . a2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ci xi ai0 Ai1 ai2 ai3 . . . aij . . . ain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . cm xm am0 Am1 am2 am3 . . . amj . . . Amn ( a00 A01 a02 a03 . . . a0j . . . a0n 2. За направляючий вибирають стовпець Aj для якого . (2) 3. Направляючий рядок Ai вибирається за умовою: . (3) 4. Виконується крок симплекс-перетворення з направляючим елементом aij використовуючи співвідношення: а) для елементів направляючого рядка , l = 0, 1, ..., n; (4) б) для елементів направляючого стовпця ; r = 1, 2, ..., m, при чому r ( i; ; (5) в) для решти елементів матриці , l ( j, r ( i. (6) г) для елементів індексного рядка , , l = 1, 2, ..., n. (7) Правильність обчислень перевіряється за формулами , . (8) У стовпці Bx замінити xi на xj, а в стовпці C ci на cj. 5. Якщо, всі , l = 1, 2, ..., n, то новий базисний розв’язок , оптимальний. У протилежному випадку переходиться на крок 2 і виконується наступна ітерація. 6. Другий, третій і четвертий кроки повторюються до тих пір, доки одна з ітерацій не завершиться одним з двох результатів: а) всі , l = 1, 2, ..., n. Умова оптимальності базису останньої таблиці; б) знайдеться такий a0j = (j < 0, що всі елементи цього стовпця a0j ( 0, r = 1, 2, ..., m. Це ознака необмеженості цільової функції на множині допустимих розв’язків. Особливості застосування табличного симплекс-методу. 1. Якщо за початковий, вибрано базис з вільних змінних, для яких ci = 0, то оцінки для всіх небазисних змінних рівні a0j = - cj, а відповідне значення цільової функції a00 = 0. 2. Відсутність векторів з від’ємними оцінками (при розв’язуванні задачі максимізації) є ознакою оптимальності відповідного базисного розв’язку. 3. Якщо, є хоч одна від’ємна оцінка для небазисного вектора, а його стовпець містить тільки невід’ємні елементи, то в області допустимих розв’язків цільова функція не обмежена. 4. При рішенні задач мінімізації в базис вводиться вектор з найбільшою додатньою оцінкою. Індивідуальне завдання (варіант №2) F(x1,x2) = 3x1 + 3x2 max ; x1 + x2 8, 3x1 + 7x2 21, x1 + 2x2 6, 1x1 0, 1 x2 0. Розв’язок задачі лінійного програмування в системі MathCAD Вводимо цільову функцію. Вводимо матрицю коефіцієнтів системи обмежень. Для цього: задайте ім’я матриці, наприклад А, і знак присвоєння, натиснувши комбінацію клавіш Shift+:; натисніть Ctrl+M. Появиться діалогову вікно, у якому потрібно вказати кількість рядків (Rows) та стовпців (Columns) матриці. Натисніть кнопку OK. Появиться шаблон матриці; введіть відповідні коефіцієнти системи нерівностей. Введіть вектор коефіцієнтів правої частини системи нерівностей, для цього: задайте ім’я вектора, наприклад В, і знак присвоєння. натисніть Ctrl+M. У поле Columns введіть число 1. введіть відповідні значення елементів вектора. Для розв’язку задачі у системі MathCAD: введіть початкове значення хоча б одного шуканого параметра; введіть ключове слово Given; введіть систему нерівностей у матричному вигляді: ; введіть граничні умови: ; введіть ім’я шуканого вектора оптимальних параметрів, наприклад xopt, знак присвоєння та ім’я вбудованої функції максимізації чи мінімізації:xopt:=maximize(f,x) або xopt:=minimize(f,x). Після цього система MathCAD може визначити шукані оптимальні значення, для цього введіть ім’я шуканого вектора оптимальних параметрів (у нашому випадку xopt) та натисніть клавішу = (дорівнює). Результат виконання лабораторної роботи в системі Mathcad. Висновок: я набув навиків розв’язку задачі лінійного програмування симплекс-методом, вивчив та оволодів навичками адресації та роботи з формулами в таблицях в Еxcel.

Лабораторна робота Методи оптимізації та дослідження операцій

31.03.2013 16:03-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись