Лабораторна робота 11. Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт з Математичні методи дослідження операцій. Робота № 525417

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

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

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

Рік:

2024

Тип роботи:

Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт

Предмет:

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

Завантажити

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

Цілоцислові задачі лінійног програмування – метод Гоморі Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці. Визначимо максимальне значення цільової функції F (X) = - 3x1 + 5x2 + 4x3 за таких умов-обмежень. 5x1 + 3x3≤13 4x1 - 2x2 + x3≤7 6x1 + 4x2≤15 Для побудови першого опорного плану систему нерівностей зведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми). В 1-ій нерівності (≤) -вводимо базисну змінну x4. В 2-ій нерівності (≤) - вводимо базисну змінну x5. В 3-ій нерівності (≤) - вводимо базисну змінну x6. 5x1 + 0x2 + 3x3 + 1x4 + 0x5 + 0x6 = 13 4x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 = 7 6x1 + 4x2 + 0x3 + 0x4 + 0x5 + 1x6 = 15 Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд: Базисні змінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом. Вирішимо систему рівнянь відносно базисних змінних: x4, x5, x6. Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план: X1 = (0, 0, 0, 13, 7, 15) Базисне рішення називається допустимим, якщо воно невід'ємне. Переходимо до основного алгоритму симплекс-методу. Запишемо симплекс-таблицю (Т0) Базис B x1 x2 x3 x4 x5 x6 x4 13 5 0 3 1 0 0 x5 7 4 -2 1 0 1 0 x6 15 6 4 0 0 0 1 F(X0) 0 3 -5 -4 0 0 0 Ітерація № 0. 1. Перевірка критерію оптимальності (правило А). Поточний опорний план неоптимальний, оскільки в індексному рядку F(X0) наявні від’ємні коефіцієнти:.-5; -4. 2. Визначення нової базисної змінної. В якості ведучого виберемо стовпець, який відповідає змінній x2, - на це вказує найбільший по модулю від’ємний коефіцієнт: -5 в рядку F(X0). 3. Визначення нової вільної змінної (правило В). Обчислимо додатні значення Di по рядках як частку від ділення: bi / ai2 і з них виберемо найменше: min (- , - , 15 : 4 ) = 33/4. Отже, 3-ій рядок є вивідним. Розв’язуючий елемент дорівнює (4) і стоїть на перетині ведучого стовпця і вивідного рядка. Базис B x1 x2 x3 x4 x5 x6 min x4 13 5 0 3 1 0 0 - x5 7 4 -2 1 0 1 0 - x6 15 6 4 0 0 0 1 33/4 F(X1) 0 3 -5 -4 0 0 0 0 4. Перерахунок симплекс-таблиці. Формуємо наступну частину симплексного таблиці. Замість змінної x6 в план Т1 увійде змінна x2 . Рядок, який відповідає змінній x2 в плані Т1, отриманий в результаті поділу всіх елементів даного рядка на розв’язуючий елемент РЕ=4. На місці розв’язуючого елемента в плані Т1 отримуємо 1, а в інших клітинах стовпця x2 плану Т1 записуємо нулі. Таким чином, у новому плані Т1 вже маємо заповнені рядок x2 і стовпець x2. Всі інші елементи нового плану Т1, включаючи елементи індексного рядка, визначаються за правилом прямокутника. Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають розв’язуючий елемент РЕ. НЕ = СЕ - (А * В) / РЕ СТЕ - елемент старого плану, РЕ - розв’язуючий елемент (4), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ. Розрахунок кожного елемента приведений у вигляді таблиці: B x 1 x 2 x 3 x 4 x 5 x 6 13-(15 • 0):4 5-(6 • 0):4 0-(4 • 0):4 3-(0 • 0):4 1-(0 • 0):4 0-(0 • 0):4 0-(1 • 0):4 7-(15 • -2):4 4-(6 • -2):4 -2-(4 • -2):4 1-(0 • -2):4 0-(0 • -2):4 1-(0 • -2):4 0-(1 • -2):4 15 : 4 6 : 4 4 : 4 0 : 4 0 : 4 0 : 4 1 : 4 0-(15 • -5):4 3-(6 • -5):4 -5-(4 • -5):4 -4-(0 • -5):4 0-(0 • -5):4 0-(0 • -5):4 0-(1 • -5):4 Отримуємо нову симплекс-таблицю (Т1): Базис B x1 x2 x3 x4 x5 x6 x4 13 5 0 3 1 0 0 x5 141/2 7 0 1 0 1 1/2 x2 33/4 11/2 1 0 0 0 1/4 F(X1) 183/4 101/2 0 -4 0 0 11/4 Ітерація № 1. 1. Перевірка критерію оптимальності (правило А). Поточний опорний план неоптимальний, оскільки в індексному рядку F(X0) наявний від’ємний коефіцієнт. 2. Визначення нової базисної змінної. В якості ведучого виберемо стовпець, який відповідає змінній x3, оскільки на це вказує від’ємний коефіцієнт: -4 в індексному рядку F(X1). 3. Визначення нової вільної змінної (правило В). Обчислимо значення Di по рядках як частка від ділення: bi / ai3 і з них виберемо найменше: min (13 : 3 , 141/2 : 1 , - ) = 41/3 . Отже, 1-ий рядок є вивідним. Розв’язуючий елемент дорівнює (3) і стоїть на перетині ведучого стовпця і вивідного рядка. Базис B x1 x2 x3 x4 x5 x6 min x4 13 5 0 3 1 0 0 41/3 x5 141/2 7 0 1 0 1 1/2 141/2 x2 33/4 11/2 1 0 0 0 1/4 - F(X2) 183/4 101/2 0 -4 0 0 11/4 0 4. Перерахунок симплекс-таблиці. Формуємо наступну частину симплексного таблиці. Замість змінної x4 в план Т2 увійде мінлива x3 . Рядок, який відповідає змінній x3 в плані Т2, отриманий в результаті поділу всіх елементів даного рядка на розв’язуючий елемент 3. На місці розв’язуючого елемента в плані Т2 отримуємо 1, а в інших клітинах стовпця x3 плану Т2 записуємо нулі. Таким чином, у новому плані Т2 вже маємо заповнені рядок x3 і стовпець x3. Всі інші елементи нового плануТ2, включаючи елементи індексного рядка, визначаються за правилом прямокутника. Розрахунок кожного елемента приведений у вигляді таблиці: B x 1 x 2 x 3 x 4 x 5 x 6 13 : 3 5 : 3 0 : 3 3 : 3 1 : 3 0 : 3 0 : 3 141/2-(13 • 1):3 7-(5 • 1):3 0-(0 • 1):3 1-(3 • 1):3 0-(1 • 1):3 1-(0 • 1):3 1/2-(0 • 1):3 33/4-(13 • 0):3 11/2-(5 • 0):3 1-(0 • 0):3 0-(3 • 0):3 0-(1 • 0):3 0-(0 • 0):3 1/4-(0 • 0):3 183/4-(13 • -4):3 101/2-(5 • -4):3 0-(0 • -4):3 -4-(3 • -4):3 0-(1 • -4):3 0-(0 • -4):3 11/4-(0 • -4):3 Отримуємо нову симплекс-таблицю (Т2): Базис B x1 x2 x3 x4 x5 x6 x3 41/3 12/3 0 1 1/3 0 0 x5 101/6 51/3 0 0 -1/3 1 1/2 x2 33/4 11/2 1 0 0 0 1/4 F(X2) 361/12 171/6 0 0 11/3 0 11/4 1. Перевірка критерію оптимальності (правило А). Серед значень індексного рядка немає від’ємних значень, тому ця таблиця визначає оптимальний план завдання. Оптимальний план можна записати так: x3 = 41/3 x5 = 101/6 x2 = 33/4 x1 = 0 F (X) = - 3x1 + 5x2 + 4x3 F (X) = - 3•0 + 5•33/4 +4•41/3 = 361/12 В отриманому оптимальному плані присутні дробові числа. Переходимо до застосовування методу Гоморі. За 3-ім рівнянням, де змінна x2 отримала нецілочисельне значення в оптимальному плані з найбільшою дробовою частиною 3/4, складаємо додаткове обмеження: q3 - q31•x1 - q32•x2 - q33•x3 - q34•x4 - q35•x5 - q36•x6≤0 q3 = b3 - [b3] = 33/4 - 3 = 3/4 q31 = a31 - [a31] = 11/2 - 1 = 1/2 q32 = a32 - [a32] = 1 - 1 = 0 q33 = a33 - [a33] = 0 - 0 = 0 q34 = a34 - [a34] = 0 - 0 = 0 q35 = a35 - [a35] = 0 - 0 = 0 q36 = a36 - [a36] = 1/4 - 0 = 1/4 Додаткове обмеження має вигляд: 3/4-1/2x1-1/4x6≤0 Перетворимо отриману нерівність в рівняння: 3/4-1/2x1-1/4x6 + x7 = 0, коефіцієнти якого введемо додатковим рядком в оптимальну симплексну таблицю. Базис B x1 x2 x3 x4 x5 x6 x7 x3 41/3 12/3 0 1 1/3 0 0 0 x5 101/6 51/3 0 0 -1/3 1 1/2 0 x2 33/4 11/2 1 0 0 0 1/4 0 x7 -3/4 -1/2 0 0 0 0 -1/4 1 F(X0) 361/12 171/6 0 0 11/3 0 11/4 0 1. Перевірка критерію оптимальності. План 0 в симплексній таблиці є псевдопланом, тому визначаємо вивідні рядок і стовпець. 2. Визначення нової вільної змінної. Серед від’ємних значень базисних змінних вибираємо найбільший за модулем. Вивідним буде 4-ий рядок, а змінну x7 слід вивести з базису. 3. Визначення нової базисної змінної. Мінімальне значення θ відповідає стовпцю з x6, тобто змінну x6 необхідно ввести в базис. На перетині вивідних рядка і стовпця знаходиться розв’язуючий елемент (РЕ), рівний (-1/4). Базис B x1 x2 x3 x4 x5 x6 x7 x3 41/3 12/3 0 1 1/3 0 0 0 x5 101/6 51/3 0 0 -1/3 1 1/2 0 x2 33/4 11/2 1 0 0 0 1/4 0 x7 -3/4 -1/2 0 0 0 0 -1/4 1 F(X) 361/12 171/6 0 0 11/3 0 11/4 0 θ 0 171/6 : (-1/2) = -341/3 - - - - 11/4 : (-1/4) = -5 - 4. Перерахунок симплекс-таблиці. Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса. Базис B x1 x2 x3 x4 x5 x6 x7 x3 41/3 12/3 0 1 1/3 0 0 0 x5 82/3 41/3 0 0 -1/3 1 0 2 x2 3 1 1 0 0 0 0 1 x6 3 2 0 0 0 0 1 -4 F(X0) 321/3 142/3 0 0 11/3 0 0 5 Розрахунок кожного елемента приведений у вигляді таблиці: B x 1 x 2 x 3 x 4 x 5 x 6 x 7 41/3-(-3/4 • 0):-1/4 12/3-(-1/2 • 0):-1/4 0-(0 • 0):-1/4 1-(0 • 0):-1/4 1/3-(0 • 0):-1/4 0-(0 • 0):-1/4 0-(-1/4 • 0):-1/4 0-(1 • 0):-1/4 101/6-(-3/4 • 1/2):-1/4 51/3-(-1/2 • 1/2):-1/4 0-(0 • 1/2):-1/4 0-(0 • 1/2):-1/4 -1/3-(0 • 1/2):-1/4 1-(0 • 1/2):-1/4 1/2-(-1/4 • 1/2):-1/4 0-(1 • 1/2):-1/4 33/4-(-3/4 • 1/4):-1/4 11/2-(-1/2 • 1/4):-1/4 1-(0 • 1/4):-1/4 0-(0 • 1/4):-1/4 0-(0 • 1/4):-1/4 0-(0 • 1/4):-1/4 1/4-(-1/4 • 1/4):-1/4 0-(1 • 1/4):-1/4 -3/4 : -1/4 -1/2 : -1/4 0 : -1/4 0 : -1/4 0 : -1/4 0 : -1/4 -1/4 : -1/4 1 : -1/4 361/12-(-3/4 • 11/4):-1/4 171/6-(-1/2 • 11/4):-1/4 0-(0 • 11/4):-1/4 0-(0 • 11/4):-1/4 11/3-(0 • 11/4):-1/4 0-(0 • 11/4):-1/4 11/4-(-1/4 • 11/4):-1/4 0-(1 • 11/4):-1/4 В отриманому оптимальному планізнову присутні дробові числа. За 2-им рівнянням, де змінна x5 отримала нецілочисельне значення в оптимальному плані з найбільшою дробовою частиною 2/3, складаємо додаткове обмеження: q2 - q21•x1 - q22•x2 - q23•x3 - q24•x4 - q25•x5 - q26•x6 - q27•x7≤0 q2 = b2 - [b2] = 82/3 - 8 = 2/3 q21 = a21 - [a21] = 41/3 - 4 = 1/3 q22 = a22 - [a22] = 0 - 0 = 0 q23 = a23 - [a23] = 0 - 0 = 0 q24 = a24 - [a24] = -1/3 + 1 = 2/3 q25 = a25 - [a25] = 1 - 1 = 0 q26 = a26 - [a26] = 0 - 0 = 0 q27 = a27 - [a27] = 2 - 2 = 0 Додаткове обмеження має вигляд: 2/3-1/3x1-2/3x4≤0 Перетворимо отриману нерівність у рівняння: 2/3-1/3x1-2/3x4 + x8 = 0, коефіцієнти якого введемо додатковим рядком в оптимальну симплекс таблицю. Базис B x1 x2 x3 x4 x5 x6 x7 x8 x3 41/3 12/3 0 1 1/3 0 0 0 0 x5 82/3 41/3 0 0 -1/3 1 0 2 0 x2 3 1 1 0 0 0 0 1 0 x6 3 2 0 0 0 0 1 -4 0 x8 -2/3 -1/3 0 0 -2/3 0 0 0 1 F(X0) 321/3 142/3 0 0 11/3 0 0 5 0 1. Перевірка критерію оптимальності. План 0 в симплексній таблиці є псевдопланом, тому визначаємо вивідні рядок і стовпець. 2. Визначення нової вільної змінної. Серед від’ємних значень базисних змінних вибираємо найбільший за модулем. Вивідним буде 5-ий рядок, а змінну x8 слід вивести з базису. 3. Визначення нової базисної змінної. Мінімальне значення θ відповідає 4-му стовпцю, тобто змінну x4 необхідно ввести в базис. На перетині вивідних рядка і стовпця знаходиться розв’язуючий елемент (РЕ), рівний (-2/3). Базис B x1 x2 x3 x4 x5 x6 x7 x8 x3 41/3 12/3 0 1 1/3 0 0 0 0 x5 82/3 41/3 0 0 -1/3 1 0 2 0 x2 3 1 1 0 0 0 0 1 0 x6 3 2 0 0 0 0 1 -4 0 x8 -2/3 -1/3 0 0 -2/3 0 0 0 1 F(X) 321/3 142/3 0 0 11/3 0 0 5 0 θ 0 142/3 : (-1/3) = -44 - - 11/3 : (-2/3) = -2 - - - - 4. Перерахунок симплекс-таблиці. Виконуємо перетворення симплексної таблиці методом Жордана-Гаусса. Базис B x1 x2 x3 x4 x5 x6 x7 x8 x3 4 11/2 0 1 0 0 0 0 1/2 x5 9 41/2 0 0 0 1 0 2 -1/2 x2 3 1 1 0 0 0 0 1 0 x6 3 2 0 0 0 0 1 -4 0 x4 1 1/2 0 0 1 0 0 0 -11/2 F(X0) 31 14 0 0 0 0 0 5 2 Розрахунок кожного елемента приведений у вигляді таблиці: B x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 41/3-(-2/3 • 1/3):-2/3 12/3-(-1/3 • 1/3):-2/3 0-(0 • 1/3):-2/3 1-(0 • 1/3):-2/3 1/3-(-2/3 • 1/3):-2/3 0-(0 • 1/3):-2/3 0-(0 • 1/3):-2/3 0-(0 • 1/3):-2/3 0-(1 • 1/3):-2/3 82/3-(-2/3 • -1/3):-2/3 41/3-(-1/3 • -1/3):-2/3 0-(0 • -1/3):-2/3 0-(0 • -1/3):-2/3 -1/3-(-2/3 • -1/3):-2/3 1-(0 • -1/3):-2/3 0-(0 • -1/3):-2/3 2-(0 • -1/3):-2/3 0-(1 • -1/3):-2/3 3-(-2/3 • 0):-2/3 1-(-1/3 • 0):-2/3 1-(0 • 0):-2/3 0-(0 • 0):-2/3 0-(-2/3 • 0):-2/3 0-(0 • 0):-2/3 0-(0 • 0):-2/3 1-(0 • 0):-2/3 0-(1 • 0):-2/3 3-(-2/3 • 0):-2/3 2-(-1/3 • 0):-2/3 0-(0 • 0):-2/3 0-(0 • 0):-2/3 0-(-2/3 • 0):-2/3 0-(0 • 0):-2/3 1-(0 • 0):-2/3 -4-(0 • 0):-2/3 0-(1 • 0):-2/3 -2/3 : -2/3 -1/3 : -2/3 0 : -2/3 0 : -2/3 -2/3 : -2/3 0 : -2/3 0 : -2/3 0 : -2/3 1 : -2/3 321/3-(-2/3 • 11/3):-2/3 142/3-(-1/3 • 11/3):-2/3 0-(0 • 11/3):-2/3 0-(0 • 11/3):-2/3 11/3-(-2/3 • 11/3):-2/3 0-(0 • 11/3):-2/3 0-(0 • 11/3):-2/3 5-(0 • 11/3):-2/3 0-(1 • 11/3):-2/3 Рішення вийшло цілочисловим. Оптимальний цілочисловий план можна записати так: x3 = 4 x5 = 9 x2 = 3 x6 = 3 x4 = 1 x1 = 0 F (X) = - 3x1 + 5x2 + 4x3 F (X) = - 3•0 + 5•3 + 4•4 F(X) = 31

Методичні вказівки до виконання дипломних та магістерських кваліфікаційних робіт Математичні методи дослідження операцій

tinysinjka

27.12.2013 02:12-

Коментарі

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

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

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

поділитись