Завдання 5
Один з цехів галантерейної фабрики випускає сумки двох видів А і В. Відомо, що на виготовлення сумки кожного виду можна використовувати штучну шкіру, однотонну тканину і тканину в клітку. Запаси цих матеріалів на фабриці відповідно складають d1, d2, d3 дм2. На виготовлення однієї сумки А витрати штучної шкіри становлять а1 дм2, однотонної тканини – а2 дм2, тканини в клітку – а3 дм2.
Аналогічні витрати матеріалу на виготовлення однієї сумки В складають відповідно b1, b2, b3 дм2. Від реалізації однієї сумки А фабрика одержує прибуток с1 грн., а від однієї сумки В – с2 грн. Визначити, скільки сумок кожного виду повинен виготовити цех, щоб одержати найбільший прибуток, якщо:
Матеріали |
Норми витрат матеріалів на одиницю продукції |
Запаси матеріалів | |
А |
В | ||
1 - штучна шкіра |
8 |
6 |
d1 = 105 |
2 - однотонна тканина |
3 |
6 |
d2 = 95 |
3 - тканина в клітку |
6 |
2 |
d3 = 110 |
Прибуток на одиницю продукції |
с1 = 4 |
с2 = 4 |
|
Задачу розв'язати графічно та методом Гоморі.
Розв'язання:
Припустимо, що буде виготовлено одиниць виробуА, одиниць виробу В. Тоді для виробництва такої кількості виробів потрібно затратити дм2 штучної шкіри. Так як фабрика забезпечена штучною шкірою в кількості 105 дм2, то повинна виконуватися нерівність:
Аналогічні міркування відносно забезпеченості фабрики сировиною другого та третього виду приведуть до наступних нерівностей:
При цьому, так як кількість виробів не може бути від'ємною, то
А також має бути забезпечений цілочисловий розв’язок.
Тоді прибуток від реалізації даних виробів складе
Математична модель вихідної задачі:
Знайдемо розв’язок сформульованої задачі, використовуючи її геометричну інтерпретацію. Спочатку визначимо багатокутник розв’язків. Для цього в нерівностях системи обмежень та умовах невід’ємності змінних знаки нерівностей поміняємо на знаки точних рівностей і накреслимо відповідні прямі:
На координатній площині будуємо графіки заданих прямих. Кожна з них ділить площину на дві півплощини. Координати точок однієї півплощини задовольняють вихідній нерівності, а іншої – ні. Щоб визначити шукану півплощину, потрібно взяти будь-яку точку, яка належить одній з півплощин, і перевірити, чи задовольняють її координати даній нерівності. Якщо координати вибраної точки задовольняють даній нерівності, то шуканою являється та півплощина, якій належить ця точка, в іншому випадку – друга півплощина.
Багатокутником розв’язків є OABD, як видно з рисунка:
Координати будь-якої точки, яка належить цьому чотирикутнику, задовольняють задану систему нерівностей та умови невід’ємності змінних. Тому сформульована задача буде розв’язана, якщо знайдемо точку даного чотирикутника, в якій функція досягає мінімального та максимального значення. Щоб знайти вказану точку, побудуємо векторі пряму, де- деяка постійна така, що дана пряма має спільні точки з багатокутником розв’язків.
Координати точки B (точка перетину (1) та (2) прямих) і визначають найбільше значення функції.
B:
Для пошуку цілочислового розв’язку визначаємо точки з цілими координатами, які наближені до цієї точки максимуму. Це чотири точки (1, 15), (2, 14), (3, 13) і (4, 12).
,
Всі ці точки є точками максимуму, значення функції в них одинакові.
Знайдемо розв'язок задачі методом Гоморі.
Спочатку знайдемо розв’язок симплекс–методом, нехтуючи умовою цілочисловості.
Запишемо цю задачу в канонічній формі задачі лінійного програмування. Для цього перейдемо від обмежень-нерівностей до обмежень-рівностей. Введемо три додаткові змінні, в результаті чого обмеження запишуться у вигляді системи рівнянь:
Ці додаткові змінні мають наступний економічний зміст – не використана при даному плані виробництва кількість сировини того чи іншого виду. Наприклад, - це невикористана кількість сировини першого виду.
Перетворену систему рівнянь запишемо у векторній формі:
де
Оскільки серед векторів є три одиничних вектори, для даної задачі можна безпосередньо записати опорний план: який визначається системою трьохмірних одиничних векторів , які утворюють базис трьохвимірного векторного простору.
Складаємо симплекс-таблицю для І ітерації, підраховуємо значення та перевіряємо вихідний опорний план на оптимальність:
- обчислюється скалярний добуток векторів та. А дляобчислюється скалярний добуток векторівта:
Для векторів базису
Симплекс-таблиця І ітерації:
і |
Базис |
4 |
4 |
0 |
0 |
0 | ||
1 |
0 |
105 |
8 |
6 |
1 |
0 |
0 | |
2 |
0 |
95 |
3 |
6 |
0 |
1 |
0 | |
3 |
0 |
110 |
6 |
2 |
0 |
0 |
1 | |
|
|
|
-4 |
-4 |
0 |
0 |
0 |
Як видно з таблиці, значення всіх основних змінних рівні нулю, а додаткові змінні приймають свої значення у відповідності з обмеженнями задачі. Цей план, звичайно, не буде оптимальним. Це видно ще й з 4-ого рядка таблиці, так як у ній є 2 однакових від’ємних числа.
Найбільш доцільним є включення в план виробництва виробів, яким відповідає максимальне за абсолютною величиною від’ємне число стоїть в 4-ому рядку стовпця вектора. Визначаємо вектор, який потрібно виключити з базису. Для цього знаходимодля, тобто –
Отже, вектор виключаємо з базису. Стовпчик вектора і перший рядок являються направляючими. Складаємо таблицю для ІІ ітерації.
Спочатку заповнюємо рядок вектора, введеного в базис, тобто рядок, номер якого співпадає з номером направляючого рядка. Отже, елементи 1-го рядка отримуються з відповідних елементів їх діленням на розв'язувальний елемент (тобто на 8). При цьому в стовпці записуємо коефіцієнт , який знаходиться в стовпці введеного в базис вектора.
Потім заповнюємо елементи стовпців для векторів, які входять в новий базис. В цих стовпцях на перетині рядків та стовпців однойменних векторів ставимо 1, а всі інші елементи – 0.
Для визначення інших елементів застосовуємо правило трикутника.
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Симплекс-таблиця ІІ ітерації.
і |
Базис |
4 |
4 |
0 |
0 |
0 | ||
1 |
4 |
13 1/8 |
1 |
3/4 |
1/8 |
0 |
0 | |
2 |
0 |
95-3*13 1/8=55 5/8 |
0 |
6-3*3/4= 3 3/4 |
0-3*1/8= -3/8 |
1 |
0 | |
3 |
0 |
110-6*13 1/8=31 1/4 |
0 |
2-6*3/4= -2 1/2 |
0-6*1/8= -3/4 |
0 |
1 | |
|
|
|
0 |
-1 |
1/2 |
0 |
0 |
Отже, кінцева таблиця ІІ ітерації готова:
і |
Базис |
4 |
4 |
0 |
0 |
0 | ||
1 |
4 |
13 1/8 |
1 |
3/4 |
1/8 |
0 |
0 | |
2 |
0 |
55 5/8 |
0 |
3 3/4 |
-3/8 |
1 |
0 | |
3 |
0 |
31 1/4 |
0 |
-2 1/2 |
-3/4 |
0 |
1 | |
|
|
|
0 |
-1 |
1/2 |
0 |
0 |
Цей план не буде оптимальним, це видно з 4-ого рядка таблиці, так як у ній є 1 від’ємне число.
Включаємо в план виробництва виріб В, оскільки від’ємне число стоїть в 4-ому рядку стовпця вектора . Визначаємо вектор, який потрібно виключити з базису. Для цього знаходимодля, тобто –
Отже, вектор виключаємо з базису. Стовпчик вектора і другий рядок являються направляючими. Складаємо таблицю для ІІI ітерації.
Спочатку заповнюємо рядок вектора, введеного в базис, тобто рядок, номер якого співпадає з номером направляючого рядка. Отже, елементи 2-го рядка отримуються з відповідних елементів їх діленням на розв'язувальний елемент (тобто на 3 3/4). При цьому в стовпці записуємо коефіцієнт , який знаходиться в стовпці введеного в базис вектора.
Потім заповнюємо елементи стовпців для векторів, які входять в новий базис. В цих стовпцях на перетині рядків та стовпців однойменних векторів ставимо 1, а всі інші елементи – 0.
Для визначення інших елементів застосовуємо правило трикутника.
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Значення в 4-ому рядку стовпця векторазнаходимо за формулою:
Симплекс-таблиця ІІI ітерації.
і |
Базис |
4 |
4 |
0 |
0 |
0 | ||
1 |
4 |
13 1/8-3/4*14 5/6=2 |
1 |
0 |
1/8-3/4* (-1/10)=1/5 |
0-3/4*4/15= -1/5 |
0 | |
2 |
4 |
14 5/6 |
0 |
1 |
-1/10 |
4/15 |
0 | |
3 |
0 |
31 1/4 +2 1/2*14 5/6=68 1/3 |
0 |
0 |
-3/4+2 1/2* (-1/10)= -1 |
0+2 1/2*4/15=2/3 |
1 | |
|
|
|
0 |
0 |
2/5 |
4/15 |
0 |
Отже, кінцева таблиця ІІІ ітерації готова:
і |
Базис |
4 |
4 |
0 |
0 |
0 | ||
1 |
4 |
2 |
1 |
0 |
1/5 |
-1/5 |
0 | |
2 |
4 |
14 5/6 |
0 |
1 |
-1/10 |
4/15 |
0 | |
3 |
0 |
68 1/3 |
0 |
0 |
-1 |
2/3 |
1 | |
|
|
|
0 |
0 |
2/5 |
4/15 |
0 |
Знайдений план задачі являється оптимальним. Це видно з 4-ого рядка таблиці , оскільки всі числа додатні.
Отже, оптимальний план –.
Значення другої змінної є дробовим числом, що не задовольняє початкові умови задачі. Побудуємо для другого рядка наведеної симплексної таблиці додаткове обмеження виду
Оскільки то додаткове обмеження набуває вигляду:
Зведемо його до канонічної форми та введемо штучну змінну:
Приєднавши отримане обмеження до симплексної таблиці з умовно-оптимальним планом дістанемо:
і |
Базис |
4 |
4 |
0 |
0 |
0 |
0 |
-М | ||
1 |
4 |
2 |
1 |
0 |
1/5 |
-1/5 |
0 |
0 |
0 | |
2 |
4 |
14 5/6 |
0 |
1 |
-1/10 |
4/15 |
0 |
0 |
0 | |
3 |
0 |
68 1/3 |
0 |
0 |
-1 |
2/3 |
1 |
0 |
0 | |
4 |
-М |
5/6 |
0 |
0 |
9/10 |
4/15 |
0 |
-1 |
1 | |
|
|
|
0 |
0 |
2/5 |
4/15 |
0 |
0 |
0 | |
|
|
|
-5/6М |
0 |
0 |
-9/10М |
-4/15М |
0 |
М |
0 |
Розв’язуючи наведену задачу, остаточно знаходимо цілочисловий оптимальний план: .