Тривалість обробки продукції на верстатах, год

Верстат	Тривалість обробки одиниці продукції
А	В	С	D

Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу використання верстатів (у машино-годинах). Вартість однієї машино-години становить 10 грн для верстата 1 і 15 грн — для верстата 2. Тривалість використання верстатів обмежена: для верстата 1 вона становить 450 машино-годин, а для верстата 2 — 380 машино-годин.

Ціна одиниці продукції видів А, В, С і D дорівнює відповідно 73, 70, 55 та 45 грн.

Визначити оптимальний план виробництва продукції всіх чотирьох видів, який максимізує загальний прибуток.

Побудова економіко-математичної моделі. Нехай х_j — план виробництва продукції j -го виду, де j може набувати значень від 1 до 4.

Умовами задачі будуть обмеження на тривалість використання верстатів для виробництва продукції всіх видів:

для верстата 1 (маш.-год.);

для верстата 2 (маш.-год.).

Цільовою функцією задачі є загальний прибуток від реалізації готової продукції, який розраховується як різниця між ціною та собівартістю виготовлення продукції кожного виду:

.

Отже, математична модель цієї задачі має такий вигляд:

за умов:

Розв’язання. Розв’яжемо задачу симплекс-методом згідно з розглянутим алгоритмом.

1. Запишемо систему обмежень задачі в канонічному вигляді. Для цього перейдемо від обмежень-нерівностей до строгих рівнянь, увівши до лівої частини обмежень додаткові змінні х ₅ та х ₆:

Ці додаткові змінні за економічним змістом означають недовикористаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:

Канонічну систему обмежень задачі запишемо у векторній формі:

де

Оскільки вектори та одиничні та лінійно незалежні, то саме з них складається початковий базис у зазначеній системі век­торів. Змінні задачі х ₅ та х ₆, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:

Згідно з визначеними векторна форма запису системи обмежень цієї задачі матиме вигляд:

.

Оскільки додатні коефіцієнти х ₅ та х ₆ відповідають лінійно незалежним векторам, то за означенням

є опорним планом задачі і для цього початкового плану

.

2. Складемо симплексну таблицю для першого опорного плану задачі.

Базис

С баз

План

– 5

х 1

х 2

х 3

х 4

х 5

х 6

х 5

х 6

Zj – с j ≥ 0

–8

–10

Елементи останнього рядка симплекс-таблиці є оцінками _j, за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так:

;

;

;

;

;

.

У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану: .

3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність. Для цього продивляються елементи оцінкового рядка. Якщо всі (для задачі на max) або (для задачі на min), то визначений опорний план є оптимальним. Якщо ж в оцінковому рядку є хоча б одна оцінка, що не задовольняє умову оптимальності (від’ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.

У цій задачі в оцінковому рядку дві оцінки та від’ємні, тобто не задовольняють умову оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.

4. Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних.

Для введення до нового базису вибираємо змінну х ₂, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності
(|–10|>|–8|).

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х ₂» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці маємо, що , і тому з базису виключаємо змінну х ₅, а число а ₁₂ = 3 — розв’язувальний елемент. Дальший перехід до нового опор­ного плану задачі полягає в побудові наступної симплексної таблиці, елементи якої розраховують за методом Жордана—Гаусса.

Друга симплексна таблиця має такий вигляд:

Базис

С баз

План

– 5

х 1

х 2

х 3

х 4

х 5

х 6

х 2

2/3

4/3

2/3

1/3

х 6

5/3

–5/3

2/3

–2/3

Zj – сj ≥ 0

–4/3

40/3

35/3

10/3

У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «С _баз», а решту елементів нової таблиці розраховують за розглянутими нижче правилами:

1. Кожний елемент розв’язувального (напрямного) рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці.

2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.

3. Якщо в напрямному рядку є нульовий елемент, то від­повідний стовпчик переписують у нову симплексну таблицю без змін.

4. Якщо в напрямному стовпчику є нульовий елемент, то відповідний рядок переписують у нову таблицю без змін.

Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.

Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:

1 — розв’язувальний елемент (число 1);

2 — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;

3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

Необхідний елемент нової симплекс-таблиці визначають за такою формулою:

.

Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «х ₄». Складемо умовний прямокутник:

Тоді . Це значення записуємо в стовпчик «х ₄» у другому рядку другої симплексної таблиці.

Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка. Наявність двох способів зображення визначення оцінок опорного плану (за правилом прямокутника та за відповідною формулою) дає змогу контролювати правильність арифметичних обчислень на кожному кроці симплекс-методу.

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності Z_j – с _j ≥ 0 для другого опорного плану. Цей план також неоптимальний, оскільки . Викорис­товуючи процедуру симплекс-методу, визначаємо третій опор­ний план задачі, який наведено у вигляді таблиці:

Базис

С баз

План

– 5

х 1

х 2

х 3

х 4

х 5

х 6

х 2

2/5

3/5

–2/5

х 1

–1

2/5

–2/5

3/5

Zj – сj ≥ 0

61/5

14/5

4/5

В оцінковому рядку третьої симплексної таблиці немає від’ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, що знайдено оптимальний план задачі:

або

Х ^* = (48; 118; 0; 0; 0; 0);

.

Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 одиниць продукції В, є оптимальним. Він уможливлює отримання найбільшого прибутку за заданих умов (1564 грн). При цьому час роботи верстатів використовується повністю (х ₅ = х ₆ = 0).

Наведені вище три симплексні таблиці можна об’єднати в одну та послідовно записувати в ній всі ітерації.

2.8.6. Метод штучного базису

У попередніх параграфах розглядався випадок, коли система обмежень задачі лінійного програмування містила одиничну матрицю порядку m. Проте більшість задач не можна звести до потрібного вигляду. В такому разі застосовується метод штучного базису.

Розглянемо задачу лінійного програмування:

(2.60)

(2.61)

(2.62)

Задача подана в канонічному вигляді і система обмежень (2.61) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну . Такі змінні називають штуч­ними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (2.61) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння:

(2.63)

У результаті додавання змінних у рівняння системи (2.61) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (2.63) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (2.63) набуде вигляду (2.61) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі (2.60)—(2.62).

Згідно з симплексним методом до базису вводять змінні, які покращують значення цільової функції. Для даної задачі на максимум вони мають його збільшувати. Отже, для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з від’ємними коефіцієнтами. Тобто цільова функція набуде вигляду:

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд: ).

Припускається, що величина М є досить великим числом. Тоді якого б малого значення не набувала відповідна коефіцієнту штучна змінна , значення цільової функції буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні .

Якщо в оптимальному плані розширеної задачі існує хоча б одне значення , то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна.

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му — ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.

Теорема 2.8. Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.

Доведення. Зазначимо, що коли план є оптимальним планом розширеної задачі, то план — план початкової задачі. При цьому

.

Доведемо, що план — оптимальний план початкової задачі. Допустимо, що не є оптимальним планом. Тоді існує та­кий оптимальний план , для якого . Звідси для вектора , що є планом розширеної задачі, маємо:

,

тобто

.

Отже, план розширеної задачі не є оптимальним, що суперечить умові теореми, а тому зроблене допущення щодо неоптимальності плану є неправильним.

Отже, загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

3. Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.

4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.

5. Повторення дій, починаючи з п. 3.

Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі.

У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки.

1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язуваль­ний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.

2. Якщо при переході у симплекс-методі від одного опорного плану задачі до іншого в напрямному стовпчику немає додатних елементів , тобто неможливо вибрати змінну, яка має бути виведена з базису, то це означає, що цільова функція задачі лінійного програмування є необмеженою й оптимальних планів не існує.

3. Якщо для опорного плану задачі лінійного програмування всі оцінки задовольняють умову оптимальності, але при цьому хоча б одна штучна змінна є базисною і має додатне значення, то це означає, що система обмежень задачі несумісна й оптимальних планів такої задачі не існує.

Розв’язати задачу з прикладу 2.10 із додатковою умовою: продукція С має виготовлятися обсягом не менш як 9 одиниць.

Розв’язання. Математичну модель сформульованої задачі запишемо так:

Застосовуючи для розв’язування поставленої задачі симплекс-метод, спочатку запишемо систему обмежень у канонічній формі:

Зауважимо, що нерівність типу «≥» перетворюємо у рівняння вве­денням у ліву частину обмеження додаткової змінної зі знаком «–».

Система містить лише два одиничні вектори — та , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом + 1 штучну змінну х ₈, якій відповідатиме одиничний вектор .

Тепер можемо розглянути розширену задачу лінійного програмування:

за умов:

На відміну від додаткових змінних штучна змінна х ₈ має в цільовій функції Z коефіцієнт + М (для задачі на min) або – М (для задачі на max), де М — досить велике додатне число.

У розширеній задачі базисними змінними є х ₅, х ₆, х ₈, а решта змінних вільні. Початковий опорний план задачі такий:

Складемо першу симплексну таблицю цієї задачі:

Базис

С баз

План

– 5

– М

q

х 1

х 2

х 3

х 4

х 5

х 6

х 7

х 8

х 5

112,5

х 6

х 8

– М

–1

Zj – с j ³ 0

– 8

– 10

– 9 М

– М

М

Розраховуючи оцінки першого опорного плану, дістаємо:
Z ₀ = –9 M; Z ₁ – с₁ = –8; Z ₂ – с₂ = –10, Z ₃ – с₃ = – М і т. д. Отже, ми отримуємо оцінки двох видів: одні з них містять М, а інші є звичайними числами. Тому для зручності розділимо оцінковий рядок на два. У перший оцінковий рядок будемо записувати звичайні числа, а в другий — числа з коефіцієнтом М.

Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Згідно з алгоритмом, розглянутим у задачі 2.41, виконуємо перехід до наступного опорного плану задачі. Піс­ля першої ітерації з базису виведена штучна змінна х ₈. Дальше розв’язування продовжуємо за алгоритмом симплексного методу.

Наступні кроки розв’язування задачі наведені у загальній таблиці:

Базис

С баз

План

– 5

– М

q

х 1

х 2

х 3

х 4

х 5

х 6

х 7

х 8

х 5

–4

х 6

–1

185,5

х 3

–1

—

Zj – с j ³ 0

–8

–10

М

х 2

2/3

2/3

1/3

4/3

–4/3

х 6

5/3

2/3

–2/3

–5/3

5/3

х 3

– 1

—

Zj – с j ³ 0

–4/3

35/3

10/3

40/3

–40/3

М

х 2

2/5

3/5

–2/5

–2

х 1

2/5

–2/5

3/5

–1

х 3

–1

Zj – с j ³ 0

61/5

14/5

4/5

–12

М

Оптимальним планом задачі є вектор:

Х ^* = (57; 100; 9; 0; 0; 0; 0),

Отже, оптимальним є виробництво 57 одиниць продукції А, 100 одиниць продукції В і 9 одиниць продукції С. Тоді прибуток буде найбільшим і становитиме 1456 грн.

Фінансові ресурси фірми можуть використовуватися для вкладення у два проекти. За інвестування в проект А гарантується отримання через рік прибутку в розмірі 60 коп. на кожну вкладену гривню, а вкладення в проект В дає змогу отримати дохід у розмірі 2 грн на кожну інвестовану гривню, але через два роки. За фінансування проекту В період інвестування має бути кратним двом. Визначити, як потрібно розпорядитися капіталом у сумі 100 000 грн, щоб максимізувати загальний грошовий дохід, який можна отримати через три роки після початку інвестування.

Розв’язання. Нехай x_ij — розмір вкладених коштів у і -му році в проект j (i = ; j = 1, 2). Побудуємо умовну схему розподілу грошових коштів протягом трьох років.

		Проект А	Проект В
1-й рік	Наявна сума на початок року	100 000
	Альтернативні вкладення	х 11	х 12
	Дохід на кінець року	1,6 х 11	—
2-й рік	Наявна сума на початок року	100 000 – (х 11 + х 12) +1,6 х 11
	Альтернативні вкладення	х 21	х 22
	Дохід на кінець року	1,6 х 21	3 х 12
3-й рік	Наявна сума на початок року	100 000 – (х 11 + х 12) + 1,6 х 11 – – (х 21 + х 22) + 1,6 х 21 + 3 х 12
	Альтернативні вкладення	х 31	—
	Дохід на кінець року	1,6 х 31	3 х 22

Згідно з наведеною схемою можна записати математичну модель задачі.

Цільова функція: грошовий дохід фірми після трьох років інвестицій

.

Обмеження моделі сформулюємо згідно з такою умовою: розмір коштів, інвестованих у поточному році, не може перевищувати суми залишку коштів минулого року та доходу за минулий рік:

для 1-го року ;

для 2-го року ;

для 3-го року .

Виконавши елементарні перетворення, дістанемо систему обмежень:

Отже, економіко-математична модель сформульованої задачі має такий вигляд:

за умов:

Очевидно, що ця задача є задачею лінійного програмування і її можна розв’язати симплекс-методом. Згідно з алгоритмом необхідно звести систему обмежень задачі до канонічної форми. Це виконується за допомогою додаткових змінних х ₁, х ₂, та х ₃, які введемо зі знаком «+» до лівої частини всіх відповідних обмежень. У цільовій функції задачі ці змінні мають коефіцієнт, що дорівнює нулю.

Розв’язування задачі наведено у вигляді симплексної таблиці:

Базис	С баз	План					1,6
х 11	х 12	х 21	х 22	х 31	х 1	х 2	х 3
х 1		100 000
х 22			–1,6
х 31	1,6			–3	–1,6
Zj – с j ³ 0		–4,8	–4,8	0,44					1,6
х 11		100 000
х 22		160 000		1,6				1,6
х 31	1,6			–3	–1,6
Zj – с j ³ 0	480 000			0,44			4,8		1,6

Оптимальним є такий план:

За такого плану інвестувань

Але задача має ще один оптимальний план, який можна дістати, вибравши розв’язувальний елемент у стовпчику «х ₁₂» останньої симплексної таблиці. Це може бути або число 1, або 1,6. Візьмемо як розв’язувальний елемент 1. Виконавши один крок перетворень симплекс-методом, дістанемо таку другу кінцеву симплексну таблицю:

Базис	С баз	План					1,6
х 11	х 12	х 21	х 22	х 31	х 1	х 2	х 3
х 12		100 000
х 22			–1,6
х 31	1,6	300 000			–1,6
Zj – с j ³ 0	480 000			0,44			4,8		1,6

Звідси:

Зобразимо використання грошових коштів фірми за першим оптимальним планом задачі у вигляді схеми:

		Проект А	Проект В
1-й рік	Наявна сума на початок року	100 000 грн
	Вкладення	х 11 = 100 000	х 12 = 0
	Дохід на кінець року		160 000 грн
2-й рік	Наявна сума на початок року	160 000 грн
	Вкладення	х 21 = 0	х 22 = 160 000
	Дохід на кінець року		0 грн
3-й рік	Наявна сума на початок року	0 грн
	Вкладення
	Дохід на кінець року	х 31	480 000 грн.

Згідно з розглянутою схемою перший оптимальний план інвестування передбачає на перший рік усі кошти обсягом 100 000 грн вкласти в проект А, що дасть змогу одержати прибуток обсягом 60 000 грн, а загальна сума в кінці року становитиме 160 000 грн. На другий рік усі кошти в розмірі 160 000 грн передбачається витратити на фінансування проекту В. Наприкінці другого року фірма прибутку не отримає. На третій рік фінансування проектів не передбачається, але в кінці року прибуток фірми від минулорічних інвестицій проекту В становитиме 320 000 грн, а загальний грошовий дохід — 480 000 грн.

Такий же максимальний дохід можна мати, провівши інвестиції за схемою:

		Проект А	Проект В
1-й рік	Наявна сума на початок року	100 000 грн
	Вкладення	х 11 = 0	х 12 = 100 000
	Дохід на кінець року	0 грн
2-й рік	Наявна сума на початок року	0 грн
	Вкладення	х 21 = 0	х 22 = 0
	Дохід на кінець року	300 000 грн
3-й рік	Наявна сума на початок року	300 000 грн
	Вкладення	х 31 = 300 000
	Дохід на кінець року		480 000 грн.

Згідно з другим оптимальним планом у першому році фірма спрямовує весь капітал у розмірі 100 000 грн на фінансування проекту В. Це уможливить одержання грошового доходу лише наприкінці другого року обсягом 300 000 грн, які на третій рік повністю інвестуються в проект А. Загальний грошовий дохід фір­ми за три роки діяльності за цим варіантом також становитиме 480 000 грн.

Якщо як розв’язувальний елемент в останній симплексній таблиці взяти число 1,6, то матимемо третій оптимальний план:

Продукція фабрики випускається у вигляді паперових рулонів стандартної ширини — 2 м. За спеціальним замовленням споживачів фабрика постачає також рулони інших розмірів, розрізуючи стандартні.

Типові замовлення на рулони нестандартних розмірів наведено в табл. 2.9.

Таблиця 2.9

Дата добавления: 2015-05-23