Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Лабораторна робота № 2 з дисципліни «Математичні методи дослідження операцій» Симплекс-метод розв’язку задач лінійного програмування Львів – 2008 Мета роботи: набуття навиків розв’язування задач лінійного програмування (ЗЛП) симплекс-методом, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях у середовищі Еxcel Порядок роботи: Заповнити початкову симплекс-таблицю ЗЛП згідно заданого варіанту завдання. Використовуючи засоби роботи з адресацією в Еxcel та роботу з формулами, заповнити таблиці, що відповідають ітераціям симплекс методу задачі лінійного програмування. Знайти оптимальний розв’язок і максимальне та мінімальне значення цільової функції. Проінтерпретувати отримані результати для вихідної задачі. Оформити звіт для захисту лабораторної роботи за зразком: назва роботи; мета роботи; порядок виконання роботи; короткі теоретичні відомості; алгоритм побудови розв’язку задачі; малюнки відповідних таблиць; одержані результати, їх аналіз і висновки. Короткі теоретичні відомості про симплекс-метод розв’язування ЗЛП. Симплекс-метод, який відомий ще як метод послідовного покращення плану, дозволяє послідовно переходити від одного базисного розв’язку до другого, причому так, що значення цільової функції зростають. Оптимальний розв’язок знаходиться при цьому за cкінчену кількість кроків. Алгоритми симплекс-методу дозволяють також відповісти на запитання: чи може бути взагалі розв’язаною конкретна задача лінійного програмування. Методикою побудови розв’язку, яка найкраще піддається формалізації й алгоритмізації для реалізації на обчислювальній техніці, є метод симплекс-таблиць. Основою для методу симплекс-таблиць є розширена матриця обмежень. Вона характеризується наявністю одиничної підматриці, причому всі вільні члени мають бути додатні: Ap = [A1, ..., An, e1, ..., em, A0]. (1) До такого вигляду можна привести довільну початкову матрицю обмежень застосувавши відомі перетворення. Алгоритм розв’язування задачі лінійного програмування, наприклад, задачі максимізації методом симплекс-таблиць складатиметься з наступних кроків: Розрахувати і заповнити початкову таблицю з одиничним базисом у вигляді 2. За напрямний стовпець Aj вибирають той, для якого  EMBED Equation.2 
. (2) 3. Напрямний рядок вибирається за умовою:  EMBED Equation.2 
. (3) 4. Виконується крок симплекс-перетворення з напрямним елементом aij, використовуючи співвідношення: а) для елементів напрямного рядка  EMBED Equation.2 
, l = 0, 1, ..., n; (4) б) для елементів напрямного стовпця  EMBED Equation.2 
; r = 1, 2, ..., m, причому r  i;  EMBED Equation.2 
; (5) в) для решти елементів матриці  EMBED Equation.2 
, l  j, r  i. (6) г) для елементів індексного рядка  EMBED Equation.2 
,  EMBED Equation.2 
, l = 1, 2, ..., n. (7) Правильність обчислень перевіряється за формулами  EMBED Equation.2 
,  EMBED Equation.2 
. (8) Нарешті, в стовпці Bx треба замінити xi на xj, а в стовпці C замінити ci на cj. 5. Якщо, всі елементи симплекс-рядка  EMBED Equation.2 
, l = 1, 2, ..., n, то новий базисний розв’язок  EMBED Equation.2 
,  EMBED Equation.2 
є оптимальним. У випадку, коли ця умова не виконується, переходиться на крок 2 і виконується наступна ітерація. 6. Другий, третій і четвертий кроки повторюються до тих пір, доки одна з ітерацій не завершиться одним із двох результатів: а) всі  EMBED Equation.2 
, l = 1, 2, ..., n. Умова оптимальності базису останньої таблиці; б) знайдеться такий a0j = j < 0, що всі елементи цього стовпця a0j  0, r = 1, 2, ..., m. Це ознака необмеженості цільової функції  EMBED Equation.2 
 на множині допустимих розв’язків. Особливі випадки застосування табличного симплекс-методу. 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