Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Лабораторна робота № 2 з дисципліни «Математичні методи дослідження операцій» Симплекс-метод розв’язку задач лінійного програмування Львів – 2008 Мета роботи: набуття навиків розв’язування задач лінійного програмування (ЗЛП) симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях у середовищі Еxcel Порядок роботи: Заповнити початкову симплекс-таблицю ЗЛП згідно заданого варіанту завдання. Використовуючи засоби роботи з адресацією в Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування. Знайти оптимальний розв’язок і максимальне та мінімальне значення цільової функції. Проінтерпретувати отримані результати для вихідної задачі. Оформити звіт для захисту лабораторної роботи за зразком: назва роботи; мета роботи; порядок виконання роботи; короткі теоретичні відомості; алгоритм побудови розв’язку задачі; малюнки відповідних таблиць; одержані результати, їх аналіз і висновки. Короткі теоретичні відомості про симплекс-метод розв’язування ЗЛП. Симплекс-метод, який відомий ще як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, причому так, що значення цільової функції зростають. Оптимальний розв’язок знаходиться при цьому за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також відповісти на запитання: чи може бути взагалі розв’язаною конкретна задача лінійного програмування. Методикою побудови розв’язку, яка найкраще піддається формалізації й алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць. Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, причому всі вільні члени мають бути додатні: Ap = [A1, ..., An, e1, ..., em, A0]. (1) До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення. Алгоритм розв’язування задачі лінійного програмування, наприклад, задачі максимізації методом симплекс-таблиць складатиметься з наступних кроків: Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді C   c1 
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. Напрямний рядок вибирається за умовою:
. (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. При розв’язуванні задач мінімізації в базис вводиться вектор з найбільшою додатньою оцінкою.
Індивідуальне завдання 9. F(x1х2) = 3x1 * 3x2 –> max; x1 + x2<=4; 3x1 + x2>=4; xl+5x2>=4, 3>=x1>=0; 3>=х2>=0.
Висновок: У цій лабораторній роботі я набув навиків розв’язку задачі лінійного програмування симплекс-методом, вивчив та оволодів навичками адресації та роботи з формулами в таблицях в Еxcel