- •6.030504, 6.030509, 6.030510, 6.030601Денної й заочної форм навчання
- •1.Рішення систем лінійних рівнянь методом гауса - жордана
- •1.1. Основні поняття
- •1.2. Приведення системи лінійних рівнянь до жорданової форми
- •1.3. Поняття загального, часного й базисного рішень
- •2. Загальні властивості задач лінійного програмування
- •2.І. Приклад задачі лінійного програмування - задача про використання обладнання.
- •2.2. Задача про використання сировини
- •2.3. Задачі складання раціону (задача про дієту)
- •2.4. Загальна постановка задач лінійного програмування
- •2.5. Геометричний метод вирішення злп
- •Приклад 1
- •2.6. Канонічний вигляд злп
- •3. Симплексний метод вирішення злп
- •3.1. Загальна характеристика й основні етапи симплекс - методу
- •3.2. Табличний вигляд злп. Симплекс - таблиці
- •3.3. Умова оптимальності опорного плану
- •3.4. Умова нерозв'язності злп через необмеженість знизу на опр цільової функції
- •3.5. Перехід до нового опорного плану.
- •3.6. Табличний симплекс-алгоритм
- •Після вибору генерального елемента переходимо до таблиці 3.11
- •Знову вибираємо генеральний елемент і переходимо до таблиці 3.14
- •3.7. Відшукування початкового опорного плану злп методом штучного базису
- •3.8. Виродженість опорного плану. Зациклення
- •Двоїстість у лінійному програмуванні
- •5.4. Цикли перерахування
- •5.4.1. Поняття циклу перерахування
- •5.4.2. Максимально припустиме зрушення по циклу перерахування
- •5.4.3. Ціна циклу перерахування
- •5.5. Потенціали
- •5.6. Алгоритм вирішення транспортної задачі методом потенціалів
- •5.7. Відкриті транспортні задачі.
- •6. Цілочислове лінійне програмування
- •6.1. Загальна постановка задачі цілочислового лінійного програмування (зцлп)
- •6.2. Цілочислова задача про використання сировини
- •6.3. Задача про рюкзак
- •6.4. Вирішення зцлп методом округлення
- •6.5. Метод гілок і меж
- •Оптимальний план оптимальний план
- •7. Загальна постановка й різновиди задач математичного програмування
- •Література
1.3. Поняття загального, часного й базисного рішень
.
Нехай система (І.І) представлена в жордановій формі (1.2). Виразимо базисні змінні через вільні.
(1.6)
(1.6) називається загальним рішенням системи (I.I).
Якщо вільним змінним додати будь-які числові значення й обчислити значення базисних змінних із системи (1.6), то вийде рішення вихідної системи, яке має назву часне. Часне рішення називається базисним, якщо вільні змінні приймають нульові значення. Рішення (1.3) є базисним.
У прикладі загальне рішення таке:
а базисне рішення . Якщо в жордановій формі число рівнянь дорівнює числу змінних n, тобто жорданова форма має вигляд:
то система має єдине рішення; воно є й загальним, і часним , і базисним. Якщо ж k‹n , тобто жорданова форма містить вільні змінні, то система має нескінченно багато рішень.
2. Загальні властивості задач лінійного програмування
2.І. Приклад задачі лінійного програмування - задача про використання обладнання.
Підприємство випускає два види виробів А і В, для виробництва яких використовуються три типи верстатів. Відомі витрати часу (у годинах) верстатами на виробництво одиниці кожного виду виробів, резерви часу верстатів, а також прибуток від реалізації кожного виду виробу. Всі ці дані наведені в таблиці:
Таблиця 2.1.
Вироби верстати |
А |
В |
Резерви часу (у годинах) |
I |
Витрати часу на виробництво одиниці виробу (у годинах) | ||
2 |
3 |
30 | |
II |
4 |
2 |
40 |
III |
3 |
4 |
60 |
Прибуток від реалізації од. виробу |
6 |
7 |
|
Потрібно скласти план виробництва виробів А і В, що забезпечує максимальний прибуток від їхньої реалізації.
Це приклад оптимізаційної економічної задачі. Вирішення таких задач містить наступні етапи:
побудова економіко-математичної моделі;
вирішення отриманої математичної задачі яким-небудь математичним методом;
впровадження результату вирішення в практику.
Під економіко-математичною моделлю розуміється система математичних співвідношень, що описує економічний процес.
Побудуємо економіко-математичну модель задачу про використання обладнання.
Нехай х1 - кількість виробів А, а - кількість виробів В, які будуть випущені підприємством. Тоді прибуток, отриманий підприємством, дорівнює , Зміннііпотрібно підібрати так, щоб функціямаксимізувалася. Оскільки перший верстат може працювати не більше 30 годин, то повинно виконуватися співвідношення. Аналогічні обмеження на змінні х1 і х2 накладаються резервами часу другого й третього верстатів. З огляду на те, що змінні х1 і х2 можуть приймати тільки додатні значення, одержимо наступну економіко-математичну модель задачі:
max
при обмеженнях
2.2. Задача про використання сировини
З математичної точки зору ця задача є узагальненням тієї, котра розглянута в попередньому параграфі. Формулюється вона так.
Підприємство випускає продукцію n видів , на виготовлення якої витрачається сировина m видів, запаси котрої на підприємстві дорівнюють відповідно . Відомі витратисировини Si на виробництво одиниці продукції (i = ; j =). Вартість одиниці продукціїдорівнює(j =). Потрібно скласти такий план випуску продукції, при якому прибуток від реалізації продукції був би найбільшим.
Складемо математичну модель задачі.
Нехай - кількість одиниць продукції(j =).
Математична модель має вигляд:
f =→ max
при обмеженнях:
( 2.0)