Завдання 1
При продажу двох видів товарів (А і В) торгове підприємство використовує чотири види ресурсів. Норми затрат ресурсів на 1 од. товару, об’єм ресурсів наведені в таблиці. Дохід від реалізації 1 од. товару А складає 2 грн., товару В – 3 грн.
Ресурси Норма витрат ресурсів на 1 од. тов. Запас ресурсів А В 1 2 2 12 2 1 2 8 3 4 0 16 0 0 4 12 Дохід, грн. од. 2 3
Визначити оптимальний план реалізації товарів, що забезпечує для торгового підприємства максимальний прибуток.
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість товарів 1-ї моделі, що реалізує підприємство за деяким планом, а через х2 кількість товарів 2-ї моделі. Тоді прибуток, отриманий підприємством від реалізації цих товарів, складає
∫ = 2х1+3х2.
Витрати ресурсів при продажу такої кількості товарів складають відповідно:
CI =2х1 + 2х2,
CII =1х1 + 2х2,
CIII =4х1 + 0х2,
CIV =0х1 + 4х2,
Оскільки запаси ресурсів обмежені, то повинні виконуватись нерівності:
2х1 + 2х2 ≤ 12
1х1 + 2х2 ≤ 8
4х1 ≤ 16
4х2≤ 12
Оскільки, кількість товарів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2 такі, що функція ∫ = 2х1+3х2 досягає максимуму при системі обмежень:
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексної таблиці.
Визначимо максимальне значення цільової функції F (X) = 2x1 + 3x2 за таких умов-обмежень.
2x1 + 2x2≤12
x1 + 2x2≤8
4x1≤16
4x2≤12
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми). Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
2x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 12
1x1 + 2x2 + 0x3 + 1x4 + 0x5 + 0x6 = 8
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 4x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x5, x6,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,12,8,16,12)
План Базис B x1 x2 x3 x4 x5 x6 0 x3 12 2 2 1 0 0 0 x4 8 1 2 0 1 0 0 x5 16 4 0 0 0 1 0 x6 12 0 4 0 0 0 1 Індексний рядок F(X0) 0 -2 -3 0 0 0 0
Переходимо до основного алгоритму симплекс-методу.
План Базис B x1 x2 x3 x4 x5 x6 min 1 x3 12 2 2 1 0 0 0 6 x4 8 1 2 0 1 0 0 4 x5 16 4 0 0 0 1 0 - x6 12 0 4 0 0 0 1 3 Індексний рядок F(X1) 0 -2 -3 0 0 0 0 0
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідної змінної x2, тому, що це найбільший коефіцієнт по модулю.
Обчислимо значення Di по рядках як частку від ділення:
і з них виберемо найменше:
min (12 : 2 , 8 : 2 , - , 12 : 4 ) = 3
Отже, 4-ий рядок є провідним.
Дозвільний елемент дорівнює (4) і стоїть на перетині ведучого стовпця і головного рядка.
Формуємо наступну частину симплексної таблиці.
Замість змінної x в план 1 Замість змінної x2 .
Рядок, відповідної змінної x2 в планi 1, отриманий в результаті поділу всіх елементів рядка x6 плану 0 на дозвільний елемент ДE=4
На місці дозвільного елемента в плані 1 отримуємо 1.
В інших клітинах стовпця x2 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнені рядок x2 і стовпець x2 .
Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозвільний елемент ДE.
НE = СE - (А*В)/ДE
СДE - елемент старого плану, ДЕ - дозволяє елемент (4), А i В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДE.
План Базис B x1 x2 x3 x4 x5 x6 min 2 x3 6 2 0 1 0 0 -1/2 3 x4 2 1 0 0 1 0 -1/2 2 x5 16 4 0 0 0 1 0 4 x2 3 0 1 0 0 0 1/4 - Індексний рядок F(X2) 9 -2 0 0 0 0 3/4 0
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
В якості ведучого виберемо стовпець, відповідної змінної x1, Так як це найбільший коефіцієнт по модулю.
Обчислимо значення Di по рядках як частка від ділення:
і з них виберемо найменше:
min (6 : 2 , 2 : 1 , 16 : 4 , - ) = 2
Отже, 2-ий рядок є провідним.
Дозвільний елемент дорівнює (1) і стоїть на перетині ведучого стовпця і головною рядка.
Формуємо наступну частину симплексної таблиці.
Замість змінної x в план 2 Замість змінної x1 .
Рядок, відповідної змінної x1 в планi 2, отриманий в результаті поділу всіх елементів рядка x4 плану 1 на дозвільний елемент ДE=1
На місці дозвільного елемента в плані 2 отримуємо 1.
В інших клітинах стовпця x1 плану 2 записуємо нулі.
Таким чином, у новому плані 2 заповнені рядок x1 і стовпець x1 .
Всі інші елементи нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Для цього вибираємо зі старого плану чотири числа, які розташовані в вершинах прямокутника і завжди включають дозвільний елемент ДE.
НE = СE - (А*В)/ДE
СДE - елемент старого плану, ДЕ - дозвільний елемент (1), А i В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДE.
Оскільки в останньому стовпці присутні кілька мінімальних елементів 4, то номер рядка вибираємо за правилом Крек.
Метод Крек полягає в наступному. ............
