Завдання лінійного програмування
2. Складаємо систему обмеження завдання
за умовою завдання потрібно, щоб
трудові ресурси були використані повністю значить, ставимо знак (=), а накладні витрати були б не менш наявних значить, ставимо знак (
).
3. Задаємо цільову функцію
Математична модель має вигляд: знайти план випуску верстатів
),
задовольняє системі обмежень задачі
і умові незаперечності
), При якому прибуток буде максимальної
§ 3 Алгоритми рішення задачі симплексним методом
Загальна ідея симплексного методу (методу послідовного поліпшення плану) для вирішення задачі лінійного програмування складається
1) вміння знаходити початковий опорний план;
2) наявність ознаки оптимальності опорного плану;
3) вміння переходить до нехудшему опорного плану.
1) Математична модель задачі має мати канонічну форму. В іншому випадки її приводять до канонічного вигляду.
2) Знаходять початкове опорне рішення задачі. Їм є вектор, що складається з тих змінних, які входять тільки в одне рівняння в системі обмежень. Якщо початкове рішення відразу не знайти те використовують метод Гаусса.
Кількість змінних рішення дорівнює кількості рівнянь системи. Заповнюють симплексну таблицю по системі обмежень і цільової функції.
Макет симплексной таблиці:
Перший стовпець - коефіцієнти в цільової функції при базисних змінних.
Другий стовпець - базисні змінні.
Третій стовпець - вільні члени.
Сама верхня рядок - коефіцієнти при цільовій функції.
Друга верхній рядок - самі змінні, що входять в цільову функцію і в систему обмежень.
Основне поле симплекс методу - система коефіцієнтів з рівняння.
Останній рядок - служить для того, щоб відповісти на питання: "оптимальний план чи ні".
Індексна рядок дозволяє нам судити про оптимальність плану.
3) Перевіряють опорне рішення, на оптимальність, обчислюючи коефіцієнти індексного рядка за формою:
При вирішенні завдання можливі два випадки:
- При вирішенні завдання на максимум:
випливає, що рішення оптимальне
б) хоча б одна оцінка
і при відповідній змінної немає позитивних коефіцієнтів, то задача не має оптимального рішення m, k, цільова функція необмежена в О.Д.Р.
в) хоча б одна оцінка
і при відповідній змінної є позитивний коефіцієнт то дане рішення можна поліпшити, побудувавши нове опорне рішення на якому цільова функція буде більше.
- При вирішенні задачі на мінімум:
випливає, що рішення оптимальне
б) хоча б одна оцінка
і при відповідній змінної немає позитивних коефіцієнтів, то задача не має оптимального рішення m, k, цільова функція необмежена в О.Д.Р.
в) хоча б одна оцінка
і при відповідній змінної є позитивний коефіцієнт то дане рішення можна поліпшити, побудувавши нове опорне рішення.
4) Нове опорне рішення знаходиться за допомогою ключового стовпця, ключовий рядки і ключового елемента.
Ключовий стовпець вказує на змінну, яку треба вивести з числа базисних для поліпшення рішення.
Ключова рядок вказує на змінну, яку треба вивести з числа базисних для поліпшення рішення.
Ключовий елемент потрібен для елементів нового опорного рішення (для нової симплексной таблиці).
Їх знаходження залежить від мети завдання.
- При вирішенні завдання на максимум:
а) ключовий стовпець - це стовпець з негативною найменшою оцінкою
в індексному рядку.
б) ключова рядок - це рядок з найменшим відношенням вільних членів до позитивних коефіцієнтам ключового стовпця:
=
в) ключовий елемент - це число розташоване на перетині ключових стовпця і рядка (не може бути дорівнює нулю).
- При вирішенні завдань на мінімум:
а) ключовий стовпець - це стовпець з позитивною найменшою оцінкою
в індексному рядку.
б) ключова рядок - це рядок з найбільшим відношенням вільних членів до позитивних коефіцієнтам ключового стовпця:
=
в) ключовий елемент - це число розташоване на перетині ключових стовпця і рядка.
5) Заповнюють першу симплексну таблицю наступним чином:
а) ключовий рядок ділять на ключовий елемент і записують на тому ж місці в новій таблиці.
б) заповнюють базисні стовпці.
в) інші елементи перераховують за правилом "прямокутника":
де НЕ - новий елемент
СТЕ - елемент старого плану
РЕ - роздільною елемент
А та Б - елементи старого плану
6) Повертаються до другого етапу алгоритму - перевірка плану на оптимальність.
§ 4 Побудова початкового опорного рішення методом Гаусса
Наводимо завдання до канонічного вигляду.
)
)
> 0 рішення оптимальне
Відповідь: max Z (X) = 452 при X = (0; 8; 13)
Максимальний прибуток в розмірі 425 тис. Руб. може бути досягнута, якщо виробляти 8 верстатів І # 921; виду, 13 верстатів І # 921; І виду і не виробляти верстати # 921; виду.
При цьому витрачається 146 од. сировини, 120 од. трудових ресурсів і 250 од. накладних витрат.
Ця курсова робота присвячена питанню про рішення задачі лінійного програмування методом послідовного поліпшення плану, інакше симплекс - метод. Складається зі вступу, двох розділів, висновків та списку використаних джерел.
У першому розділі розповідається про лінійному програмуванні зокрема, і про те, що таке загальна постановка задачі лінійного програмування, як скласти математичну модель, а також розказано про канонічну формі завдань лінійного програмування.
Другий розділ роботи присвячена практичній частині рішення задачі. Будується математична модель, вирішується завдання симплексним методом, а також методом Гаусса.