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

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

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

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

ЗІ

Кафедра:

Не вказано

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

Рік:

2013

Тип роботи:

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

Предмет:

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

Завантажити

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

Цілоцислові задачі лінійног програмування – метод Гоморі Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці. Визначимо максимальне значення цільової функції 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:50

Коментарі

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

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

поділитись