Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода

Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
Краткое сожержание материала:

Практичне завдання з математичного програмування

Будування математичної моделі економічної задачі і розв'язання її за допомогою графічного метода, методів Жордана-Гаусса, потенціалу та симплекс-метода

Завдання 1

Два вироби В₁ і В₂ обробляються послідовно на двох верстатах. Кожен виріб типу В₁ потребує 1 год. для обробки на І-му верстаті, 2 год. -- на ІІ-му і А = 5^(1/2) = 2,236068 год. -- на ІІІ-му. Кожен виріб типу В₂ потребує 2 год. для обробки на І-му верстаті, А = 5 год. -- на ІІ-му і 3 год. -- на ІІІ-му. Час роботи на І-му верстаті не повинен перевищувати 10*5 = 50 год., на ІІ-му -- 15*5 = 75 год., на ІІІ-му -- 50 год.

Необхідно:

Скласти план виробництва при максимальному прибутку, якщо відомо, що продаж одного виробу типу В₁ приносить прибуток 5 грн, а типу В₂ -- 3 грн.

Для цього:

1). Побудувати математичну модель задачі лінійного програмування.

2). Звести дану задачу до канонічного вигляду.

Розв'язок

Введемо умовні позначення:

кількість змінних задачі (типів виробів) -- n = 2;

змінні задачі оптимізації: х₁ -- кількість виробів типу В₁, х₂ -- кількість виробів типу В₂;

кількість обмежень-нерівностей (верстатів) -- m = 3;

коефіцієнти а_ij обмежень-нерівностей (час обробки виробів j на верстатах i): а₁₁ = 1, а₂₁ = 2, а₃₁ = 2,236068; а₁₂ = 2, а₂₂ = 5, а₃₂ = 3;

праві частини b_і обмежень-нерівностей (максимальний час роботи і-го верстату) -- b₁ = 50, b₂ = 75, b₃ = 50;

коефіцієнти с_j цільової функції Z (прибуток), що максимізується -- с₁ = 5, с₂ = 3.

Одиниці вимірювання ті самі, що й в умові завдання.

1. Отже, використовуючи наведені вище дані, сформулюємо вихідну математичну модель задачі лінійного програмування: знайти кількості х₁, х₂ виробів В₁, В₂ такі, що максимізували б прибуток (цільову функцію)

Z = с₁х₁ + с₂х₂ > max

за обмежень на час роботи верстатів

а₁₁х₁ + а₁₂х₂ ? b₁

а₂₁х₁ + а₂₂х₂ ? b₂

а₃₁х₁ + а₃₂х₂ ? b₃

і, звісно, додатних значеннях змінних задачі -- х_і ? 0, і = 1, 2.

Підставляючи сюди вихідні дані, отримаємо шукану модель (1):

х₁ + 2х₂ ? 50,

2х₁ + 5х₂ ? 75, (1)

2,236068х₁ + 3х₂ ? 50;

Z = 5х₁ + 3х₂ > max.

2. Аби звести дану задачу до канонічного (стандартного) вигляду

Z = СХ > mах; АХ = В; Х ? 0, (2)

введемо допоміжні (балансові) змінні х_3,4,5 ? 0, які представляють собою різниці між максимальним і фактичним (знайденим в результаті розв'язку задачі оптимізації) часом роботи кожного з трьох верстатів. Тоді й отримаємо нашу задачу в канонічному вигляді (2), де:

Х = { х_і }, і = 1 ч n = 5,

С = (5, 3, 0, 0, 0),

1 2 1 0 0

А = 2 5 0 1 0

2,236068 3 0 0 1

В = (50, 75, 50).

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

Завдання 2

Розв'язати задачу лінійного програмування, сформульовану в Завданні 1, графічним методом:

Z = 3x₁ + 2x₂ > max

2х₁ + х₂ ? 4,

х₁ + 2х₂ ? 5, (1)

х₁ ? 0, х₂ ? 0.

Розв'язок

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

1) х₁ = - x₂/2 + 2,

2) х₁ = -2x₂ + 5,

3) x₁ = Z - 2x₂/3

Ці графіки показані на рис. 1, на якому многокутник розв'язків, як видно, обмежений знизу (оскільки в системі обмежень (1) фігурують знаки ?) тільки додатною чвертю декартової системи х_1,2 ? 0.

На цьому рисунку цільова функція показана штриховою лiнiєю, яка, залежно від величини Z, може переміщуватися паралельно сама собі. Стрілкою з буквою n на рис. 1 позначений напрямок градієнта цільової функції (тобто напрямок збільшення Z). Зрозуміло, що її максимум знаходиться в точці перетину ліній обмежень 1) і 2), в якій х₁ = 1 > 0, х₂ = 2 > 0. Це й є графічний розв'язок задачі. При цьому цільова функція буде мати таке значення:

Z = 3*1 + 2*2 = 7.

Рисунок 1. Графік до розв'язання Завдання 2

Завдання 3

Розв'язати систему лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць:

2х₁ + х₂ - х₃ - х₄ = 2

4х₁ + х₃ - 7х₄ = 3

2х₁ - 3х₂ + х₄ = 1

Розв'язок

Взагалі кажучи, ця недовизначена система може або мати безліч розв'язків, або не мати жодного (тобто бути несумісною). Для з'ясування цього застосуємо метод Гаусса (точніше, Жордана-Гаусса), який реалізуємо у вигляді таблиць 2 - 4. В таблиці 1 вміщені вихідні дані.

Таблиця 1. Вихідна матриця системи

А1	А2	А3	А4	В
2	1	-1	-1	2
4	0	1	-7	3
2	-3	0	1	1

Згідно методу Жордана-Гаусса, провідний елемент a_rs замінюємо одиницею, решту елементів провідного (r-го) рядка ділимо на провідний елемент a_rs, а решту елементів провідного (s-го) стовпчика замінюємо нулями. Елементи, які не належать до провідного рядка або стовпчика, обчислюються за правилом прямокутника:

a'_ij = a_ij - a_isa_rj / a_rs, (1)

b'_i = b_i - a_isb_r / a_rs, (2)

j = 1, …, n = 4, і r,

i = 1, …, m = 3, j s,

де a_rs -- провідний елемент (у наших таблицях підкреслений). Розрахунки за формулами (1), (2) зведемо в наступні таблиці, послідовно вибираючи провідними діагональні елементи матриці А.

На першому кроці провідним вибираємо елемент а₁₁.

Таблиця 2. Перший крок методу

А1	А2	А3	А4	В
1	0,5	-0,5	-0,5	1
0	-2	3	-5	-1
0	-4	1	2	-1

На другому кроці...