Завдання 1. Графічне рішення задачі розподілу ресурсів
В· Записати стандартну і канонічну форми.
В· Знайти усі базисні і допустимі базисні рішення. Визначити оптимальне базисне рішення.
В· Знайти графічно оптимальне базисне рішення.
Фірма випускає два види виробів А та В. Кожен виріб проходить обробку на двох технологічних лініях.
Відома таблиця технологічних коефіцієнтів - часу обробки (У хвилинах) кожного виробу на кожній технологічній лінії. Крім цього, відомі ринкова ціна кожного виробу і і загальний час кожної лінії і.
Вироби А
Вироби В
Загальний час роботи лінії
Лінія 1
60
32
1920
Лінія 2
36
60
2160
Ціна одного виробу
30
25
РІШЕННЯ
Запишемо стандартну і канонічну форми
Позначимо:
план випуску виробу А;
план випуску виробу В.
Тоді витрати лінії 1 і лінії 2, необхідні для виробництва плану будуть дорівнюють відповідно:
План буде допустимим, якщо витрати для лінії 1 і лінії 2 не перевершують загального часу роботи кожної з ліній, тобто виконуються нерівності:
Цільовою функцією служить виручка від реалізації допустимого плану при обмеженнях
(1.1)
Для канонічної форми ці обмеження потрібно перетворити в рівності. Для цього введемо дві додаткові змінні
залишок від виробництва на лінії 1 (Залишок часу обробки)
залишок від виробництва на лінії 2 (Залишок часу обробки).
Тоді отримаємо канонічну форму завдання:
-знайти змінні, які дають максимум цільової функції
при обмеженнях
(1.2)
В· Знайдемо всі базисні рішення.
Отримані обмеження утворюють систему двох рівнянь з чотирма невідомими. Серед нескінченної безлічі рішень цієї системи базисні рішення виходять наступним чином. Дві змінних прирівняємо до 0. Ці змінні назвемо вільними. Значення інших змінних отримуємо з рішення системи. Ці змінні назвемо базисними. Базисне рішення називається допустимим, якщо воно неотрицательно.
1) Нехай вільні змінні. Підставляючи значення (1.2), отримуємо систему рівнянь
Отже, базисне рішення має вигляд
.
Базисне рішення означає, що вироби А і вироби У не виробляються. Це базисна рішення є допустимим. Виручка від реалізації цього плану складе
.
2) Нехай вільні змінні. Підставляючи значення (1.2) отримуємо систему
Отже, базисне рішення має вигляд
.
Це базисна рішення означає, що виріб А не виробляється, виріб В проводиться в кількості 60 од., час виготовлення продукції на лінії 1 використовується повністю, для виробництва на лінії 2 не вистачає 1440 хвилин роботи. Це базисна рішення не є допустимим.
3) Нехай вільні змінні. Підставляючи значення в (1.2) отримуємо систему
для базисних змінних і. Отже, базисне рішення має вигляд
.
Це базисна рішення означає, що виріб А не виробляється, виріб В проводиться у кількості 36 одиниць, час виготовлення продукції лінії 1 використовується не повністю і його залишок становить 768 хвилин, а на лінії 2 використовується повністю. Це базисна рішення є допустимим. Виручка від реалізації цього плану складе ден.ед.
4) Нехай вільні змінні. Підставляючи значення в (1.2) отримуємо систему
для базисних змінних. Отже, базисне рішення має вигляд. Базисне рішення означає, що вироби А проводиться у кількості 32 од., виріб В не проводиться, час виготовлення продукції лінії 1 використовується повністю, а час виготовлення лінії 2 не повністю використовується, його залишок становить 1008 хвилин. Це базисна рішення є допустимим. Виручка від реалізації цього плану складе
ден. од.
5) Нехай вільні змінні. Підставляючи значення в (1.2) отримуємо систему
для базисних змінних. Отже, базисне рішення має вигляд. Це базисна рішення означає, що вироби А виробляється 60 од., виріб В не проводиться, не вистачає часу обробки 1680 хвилин для першої лінії, а час обробки другої лінії використовується повністю. Це базисна рішення не є допустимим.
6) Нехай вільні змінні. Тоді базисні змінні і знайдемо з системи рівнянь
Звідси випливає, що базисне рішення має вигляд. Це рішення означає, що вироби А виробляються в кількості од., вироби В виробляються в кількості, час обробки на кожній з ліній використовується повністю. Це базисна рішення є допустимим. Виручка від реалізації складе ден.ед.
В· Визначимо оптимальне базисне рішення.
З теорії лінійного програмування випливає, що оптимальне рішення можна знайти серед допустимих базисних рішень. Звідси випливає, що для визначення оптимального рішення потрібно обчислити значення цільової функції на всіх допустимих базисних рішеннях. Оптимальним буде базисне рішення, на якому значення цільової функції найбільше.
У таблиці 1.1 наведені всі допустимі базисні рішення і відповідні їм значення виручки.
двоїстий завдання рівноважний попит корисність товар
Таблиця 1.1
№
Базисні перемінні
небазисной змінні
1
2
3
4
Максимальне значення виручки досягається на четвертому базисному рішенні у цій таблиці
Отже, виріб А виробляється в кількості од., виріб В проводиться в кількості од., час обробки на кожній з ліній використовується повністю ().
Графічне рішення задачі
Розглянемо задачу в стандартній формі: знайти змінні, які забезпечують максимальне значення функції
при обмеженнях
На горизонтальній осі прямокутної системи координат будемо відкладати план випуску продукції, а на вертикальній - план випуску друга продукції.
Розглянемо перше обмеження . Безліч крапок, що задовольняють рівності, утворює пряму на площині. Побудуємо цю пряму по її точкам перетину з осями координат. Для визначення координат точки А перетину з віссю в рівняння підставимо. З нього випливає, т.е. Для визначення координат точки В перетину з віссю в рівняння підставимо. З нього випливає, тобто . Нерівності задовольняють всі точки однієї з півплощини, які утворила побудована пряма. Для її визначення достатньо перевірити справедливість нерівності для однієї точки. Для початку координат нерівність виконується. Отже, всі точки півплощини, що містить початок координат, будуть графічним зображенням цієї нерівності. Аналогічно побудуємо пряму по її точкам перетину з осями координат:. Всі точки п...
