Методи оптимізації в телекомунікаціях та радіотехніці

Ім'я файлу: Вирішення задач сімплекс-методом..docx
Розширення: docx
Розмір: 45кб.
Дата: 10.01.2024
скачати
Пов'язані файли:
Тести В1.docx
Екзотичні фрукти.pptx
текст.docx
Зразок оформлення 2 емпіричної частини КР-1.docx

УКРАЇНСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ЗАЛІЗНИЧНОГО ТРАНСПОРТУ

Факультет «Інформаційно-керуючі системи та технології»

Кафедра «Транспортний зв’язок»

Звіт з практичних робіт

з навчальної дисципліни «Методи оптимізації в телекомунікаціях та радіотехніці »

Виконав:

студент 1 курсу, групи 216-ТКРТ-Д23

спеціальності

172 «Електронні комунікації та радіотехніка»

освітньої програми

«Телекомунікації та радіотехніка»

(підпис) Кліндухов Данило
Керівник:

доцент кафедри, док. техн. наук

Трубчанінова Карина
Харків − 2023 р.

Вирішення задач сімплекс-методом.

Симплекс-метод, приклади розв'язання задач

Тут наведено ручне (не аплетом) розв'язання двох задач симплекс-методом (аналогічним рішенню аплетом) з докладними поясненнями для того, щоб зрозуміти алгоритм вирішення задач симплекс-методом. Перше завдання містить знаки нерівності тільки "≤" (завдання з початковим базисом), друге може містити знаки "≥", "≤" або "=" (завдання зі штучним базисом), вони вирішуються по-різному.

Симплекс-метод, розв'язання задачі з початковим базисом

1) Симплекс-метод для завдання з початковим базисом (усі знаки нерівностей-обмежень " ≤ ").

Запишемо завдання канонічної формі, тобто. обмеження-нерівності перепишемо у вигляді рівностей, додаючи балансові змінні:

Ця система є системою з базисом (базис s1, s2, s3, кожна з них входить лише в одне рівняння системи з коефіцієнтом 1), x1 та x2 – вільні змінні. Завдання, при вирішенні яких застосовується симплекс-метод, повинні мати наступні дві властивості: - система обмежень повинна бути системою рівнянь з базисом; - вільні члени всіх рівнянь в системі повинні бути невід'ємні.

Отримана система - система з базисом та її вільні члени невід'ємні, тому можна застосувати симплекс-метод. Складемо першу симплекс-таблицу (Ітерація 0) на вирішення завдання симплекс-метод, тобто. таблицю коефіцієнтів цільової функції та системи рівнянь за відповідних змінних. Тут "БП" означає стовпець базисних змінних, "Рішення" - стовпець правих частин рівнянь системи. Рішення перестав бути оптимальним, т.к. у z – рядку є негативні коефіцієнти.

симплекс-метод ітерація 0

БП	x1	x2	s1	s2	s3	Рішення	Ставлення
z	-4	-6	0	0	0	0	-
s1	2	1	1	0	0	64	64/1 = 64
s2	1	3	0	1	0	72	72/3=24
s3	0	1	0	0	1	20	20/1 = 20

Для покращення рішення перейдемо до наступної ітерації симплекс-методу, отримаємо наступну симплекс-таблицю. Для цього треба вибрати стовпець, що дозволяє, тобто. змінну, яка увійде до базису на наступній ітерації симплекс-метода. Він вибирається за найбільшим за модулем негативним коефіцієнтом у z-рядку (у задачі на максимум) – у початковій ітерації симплекс-метода це стовпець x2 (коефіцієнт -6).

Потім вибирається роздільна здатність рядок, тобто. змінна, яка вийде з базису на наступній ітерації симплекс-метода. Вона вибирається за найменшим відношенням стовпця "Рішення" до відповідних позитивних елементів роздільного стовпця (стовпець «Ставлення») – у початковій ітерації це рядок s3 (коефіцієнт 20).

Роздільний елементзнаходиться на перетині роздільного стовпця і рядка, його комірка виділена кольором, він дорівнює 1. Отже, на наступній ітерації симплекс-метода змінна x2 замінить в базисі s1. Зауважимо, що у z-рядку ставлення шукається, там ставиться прочерк " - " . Якщо є однакові мінімальні відносини, то вибирається будь-яке з них. Якщо в роздільному стовпці всі коефіцієнти менші або рівні 0, то розв'язання задачі нескінченне.

Заповнимо наступну таблицю «Ітерація 1». Її отримаємо з таблиці «Ітерація 0». Мета подальших перетворень - перетворити стовпець х2 в одиничний (з одиницею замість роздільного елемента і нулями замість інших елементів).

1) Обчислення рядка х2 таблиці "Ітерація 1". Спочатку ділимо всі члени роздільної здатності рядка s3 таблиці "Ітерація 0" на роздільний елемент (він дорівнює 1 в даному випадку) цієї таблиці, отримаємо рядок x2 в таблиці "Ітерації 1". Т.к. роздільна здатність елемент у цьому випадку дорівнює 1, то рядок s3 таблиці "Ітерація 0" буде збігатися з рядком х2 таблиці "Ітерація 1". Рядок x2 таблиці "Ітерації 1" ми отримали 010 0 1 20, інші рядки таблиці "Ітерація 1" будуть отримані з цього рядка та рядків таблиці "Ітерація 0" наступним чином:

2) Обчислення z-рядка таблиці "Ітерація 1". На місці-6у першому рядку (z-рядку) у стовпці х2 таблиці "Ітерація 0" має бути 0 у першому рядку таблиці "Ітерація 1". Для цього усі елементи рядка х2 таблиці "Ітерація 1" 010 0 1 20 помножимо на 6, отримаємо 060 0 6 120 і складемо цей рядок з першим рядком (z - рядком) таблиці "Ітерація 0" -4-60 0 0 0, отримаємо -400 0 6 120. У стовпці x2 з'явився нуль0, мета досягнута. Елементи роздільної здатності стовпця х2 виділені червоним кольором.

3) Обчислення рядка s1 таблиці "Ітерація 1". На місці1у s1 рядку таблиці "Ітерація 0" має бути 0 у таблиці "Ітерація 1". Для цього усі елементи рядка х2 таблиці "Ітерація 1" 010 0 1 20 помножимо на -1, отримаємо 0-10 0 -1 -20 і складемо цей рядок з s1 - рядком таблиці "Ітерація 0" 211 0 0 64, отримаємо рядок 201 0 -1 44. У стовпці х2 отримано необхідне 0.

4) Обчислення рядка s2 таблиці "Ітерація 1". На місці3у s2 рядку таблиці "Ітерація 0" має бути 0 у таблиці "Ітерація 1". Для цього усі елементи рядка х2 таблиці "Ітерація 1" 010 0 1 20 помножимо на -3, отримаємо 0-30 0 -3 -60 і складемо цей рядок з s1 - рядком таблиці "Ітерація 0" 1 3 0 1 0 72, отримаємо рядок 100 1 -3 12. У стовпці х2 отримано необхідний 0. Стовпець х2 у таблиці "Ітерація 1" став одиничним, він містить одну 1 та інші 0.

Рядки таблиці «Ітерація 1» отримуємо за таким правилом:

Новий рядок = Старий рядок – (Коефіцієнт роздільної здатності стовпця старого рядка)*(Новий рядок).

Наприклад для z-рядка маємо:

Старий z-рядок (-4-60 0 0 0)-(-6)*Новий вирішальний рядок -(0
-60 0 -6 -120) = Новий z-рядок (-4
00 0 6120).

Для наступних таблиць перерахунок елементів таблиці робиться аналогічно, тому ми його опускаємо.

симплекс-метод ітерація 1

БП	x1	x2	s1	s2	s3	Рішення	Ставлення
z	-4	0	0	0	6	120	-
s1	2	0	1	0	-1	44	44/2=22
s2	1	0	0	1	-3	12	12/1 = 12
x2	0	1	0	0	1	20	-

Розв'язуючий стовпець х1, роздільна здатність s2, s2 виходить з базису, х1 входить у базис. Абсолютно аналогічно отримаємо інші симплекс-таблиці, поки не буде отримана таблиця з усіма позитивними коефіцієнтами в z-рядку. Це ознака оптимальної таблиці.симплекс-метод ітерація 2

БП	x1	x2	s1	s2	s3	Рішення	Ставлення
z	0	0	0	4	-6	168	-
s1	0	0	1	-2	5	20	20/5 = 4
x1	1	0	0	1	-3	12	-
x2	0	1	0	0	1	20	20/1 = 20

Роздільний стовпець s3, роздільна здатність s1, s1 виходить з базису, s3 входить у базис.

симплекс-метод ітерація 3

БП	x1	x2	s1	s2	s3	Рішення	Ставлення
z	0	0	6/5	8/5	0	192	-
s3	0	0	1/5	-2/5	1	4	-
x1	1	0	3/5	-1/5	0	24	-
x2	0	1	-1/5	2/5	0	16	-

У z-рядку всі коефіцієнти невід'ємні, отже отримано оптимальне рішення x1 = 24, x2 = 16, zmax = 192.

Симплекс-метод, розв'язання задачі зі штучним базисом

2) Вирішимо симплекс-методом завдання зі штучним базисом (хоча б один знак нерівностей-обмежень "≥" або "=").

Запишемо завдання в канонічній формі (у вигляді системи рівнянь, що вимагає симплекс-метод), для цього введемо дві змінні х3 ≥ 0 і х4 ≥ 0 отримаємо:

Система обмежень пропонує тільки одну допустиму базисну змінну x4, тільки вона входить тільки в одне рівняння в третє з коефіцієнтом 1, тому в перше і друге рівняння додаємо штучні змінні R1 ≥ 0 і R2 ≥ 0 Щоб можна було застосувати симплекс-метод система рівнянь-обмежень мусить бути системою з базисом, тобто. у кожному рівнянні має бути змінна з коефіцієнтом 1, яка входить тільки в одне рівняння системи, у нашому випадку це R1, R2 та x4. Отримали так звану М-завдання:

Ця система є системою з базисом, у якій R1, R2 і x4 базисні змінні, а x1, x2 і x3 вільні змінні, вільні члени всіх рівнянь невід'ємні. Отже, для вирішення задачі можна застосувати симплекс-метод. Запишемо початкову симплекс-таблицю:

симплекс-метод ітерація 0

БП	x1	x2	x3	R1	R2	x4	Рішення	Ставлення
z	-4	-16	0	0	0	0	0	-
R1	3	4	-1	1	0	0	6	6/4=3/2
R2	1	3	0	0	1	0	3	3/3=1
x4	2	1	0	0	0	1	4	4/1=4
Оцінка	-4	-7	1	-1	-1	0	-	-

У таблицю для завдань зі штучним базисом додано рядок «Оцінка». Вона виходить підсумовуванням відповідних коефіцієнтів рядків зі штучними змінними (R) зі зворотним знаком. Вона буде присутня в таблиці доти, доки хоча б одна зі штучних змінних є в базисі. За найбільшим за модулем негативним коефіцієнтом рядка "Оцінка" визначається роздільна здатність стовпець поки вона є в таблиці. Коли рядок "Оцінка" вийде з таблиці (у базисі немає штучних змінних) роздільна здатність стовпець визначатиметься по z-рядку, як і в задачі з початковим базисом. У цій таблиці вирішальний стовпець х2, він обраний найбільшою за модулем негативною оцінкою (-7). Розв'язувальний рядок R2 обраний за найменшим відношенням стовпця "Рішення" до відповідних позитивних елементів стовпця, що дозволяє, як і в задачі без штучних змінних. Це означає, що у наступній ітерації симплекс-метода змінна х2 з вільної перейде у базисну, а змінна R2 з базисної – у вільну. Запишемо наступну симплекс-таблицю:

симплекс-метод ітерація 1

БП	x1	x2	x3	R1	R2	x4	Рішення	Ставлення
z	4/3	0	0	0	16/30	0	16	-
R1	5/3	0	-1	1	-4/3	0	2	6/5
x2	1/3	1	0	0	1/3	0	1	3
x4	5/3	0	0	0	-1/3	1	3	9/5
Оцінка	-5/3	0	1	-1	4/3	0	-	-

Роздільний стовпець х1, роздільна здатність рядок R1, R1 виходить з базису, x1 входить в базис. Після цього в базисі не залишається штучних змінних, тому рядки «Оцінка» у таблиці немає:

симплекс-метод ітерація 2

БП	x1	x2	x3	R1	R2	x4	Рішення	Ставлення
z	0	0	4/5	-4/5	32/5	0	72/5	-
x1	1	0	-3/5	3/5	-4/5	0	6/5	-
x2	0	1	1/5	-1/5	3/5	0	3/5	-
x4	0	0	1	-1	1	1	1	-

Далі роздільний стовпець вибирається по z-рядку. У z-рядку всі коефіцієнти неотрицательны крім коефіцієнта при штучної змінної R1, який впливає оптимальність, коли штучні змінні вийшли з базису. Отже, симплекс-метод отримано оптимальне рішення x1 = 6/5; x2 = 3/5; zmax = 72/5.

Особливі випадки застосування симплекс-методу

1) Коли пряма (якщо розглядається двовимірна задача лінійного програмування, а в загальному випадку гіперплощина), що представляє цільову функцію паралельна прямій (гіперплощині), що відповідає одному з нерівностей-обмежень (яка в точці оптимуму виконується, як точна рівність) теж оптимальне значення на деякій множині точок кордону області допустимих рішень. Ці рішення називають альтернативними оптимальними рішеннями. Наявність альтернативних рішень можна визначити за оптимальною симплекс-таблицею. Якщо в z-рядку оптимальної таблиці є нульові коефіцієнти небазових змінних, тобто альтернативні рішення.

2) Якщо в роздільному стовпці симплекс-таблиці всі коефіцієнти менші або рівні нуль, то не можна вибрати роздільну здатність, в цьому випадку рішення необмежене.

3) Якщо обмеження задачі лінійного програмування несумісні (тобто. вони можуть виконуватися одночасно), то завдання немає допустимих рішень. Така ситуація може виникнути, якщо всі нерівності, складові систему обмежень, мають тип " ≤ " з неотрицательными правими частинами, т.к. у цьому випадку додаткові змінні можуть становити допустиме рішення. Для інших типів обмежень використовуються штучні змінні. Якщо завдання має рішення, то оптимальної таблиці в базисі немає штучних змінних (Ri). Якщо вони там є, то завдання немає рішень.

Список літератури

1.Барвінський А. Ф. та ін. Математичне програмування: Навч. посібник. – Львів: Національний університет “Львівська політехніка” (Інформаційно-видавничий центр “Інтелект+” Інституту післядипломної освіти) “Інтелект-Захід”, 2004.

2. Бартіш М. Я. Методи оптимізації: Навч. посібник. – Львів: Видавничий центр ЛНУ імені Івана Франка, 2006.

3.Наконечний С. І., Савіна С. С. Математичне програмування: Навч. посібник. – К.: КНЕУ, 2003.
скачати