Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Симплекс-метод розв’язку задач лінійного програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Лабораторна робота № 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
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора