Математичне програмування (стр. 1 из 3)

Завдання 1

При продажу двох видів товарів (А і В) торгове підприємство використовує чотири види ресурсів. Норми затрат ресурсів на 1 од. товару, об’єм ресурсів наведені в таблиці. Дохід від реалізації 1 од. товару А складає 2 грн., товару В – 3 грн.

Ресурси	Норма витрат ресурсів на 1 од. тов.		Запас ресурсів
Ресурси	А	В	Запас ресурсів
1	2	2	12
2	1	2	8
3	4	0	16
0	0	4	12
Дохід, грн. од.	2	3

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

Розв’язок

Складаємо математичну модель задачі. Позначимо через х1 кількість товарів 1-ї моделі, що реалізує підприємство за деяким планом, а через х2 кількість товарів 2-ї моделі. Тоді прибуток, отриманий підприємством від реалізації цих товарів, складає

∫ = 2х1+3х2.

Витрати ресурсів при продажу такої кількості товарів складають відповідно:

CI =2х1 + 2х2,

CII =1х1 + 2х2,

CIII =4х1 + 0х2,

CIV =0х1 + 4х2,

Оскільки запаси ресурсів обмежені, то повинні виконуватись нерівності:

2х1 + 2х2 ≤ 12

1х1 + 2х2 ≤ 8

4х1 ≤ 16

4х2≤ 12

Оскільки, кількість товарів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0.

Таким чином, приходимо до математичної моделі (задачі лінійного програмування):

Знайти х1 , х2 такі, що функція ∫ = 2х1+3х2 досягає максимуму при системі обмежень:

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

Визначимо максимальне значення цільової функції F (X) = 2x1 + 3x2 за таких умов-обмежень.

2x1 + 2x2≤12

x1 + 2x2≤8

4x1≤16

4x2≤12

Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми). Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

2x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 12

1x1 + 2x2 + 0x3 + 1x4 + 0x5 + 0x6 = 8

4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16

0x1 + 4x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x3, x4, x5, x6,

Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:

X1 = (0,0,12,8,16,12)

План	Базис	B	x1	x2	x3	x4	x5	x6
0	x3	12	2	2	1	0	0	0
x4	8	1	2	0	1	0	0
x5	16	4	0	0	0	1	0
x6	12	0	4	0	0	0	1
Індексний рядок	F(X0)	0	-2	-3	0	0	0	0

Переходимо до основного алгоритму симплекс-методу.

План	Базис	B	x1	x2	x3	x4	x5	x6	min
1	x3	12	2	2	1	0	0	0	6
x4	8	1	2	0	1	0	0	4
x5	16	4	0	0	0	1	0	-
x6	12	0	4	0	0	0	1	3
Індексний рядок	F(X1)	0	-2	-3	0	0	0	0	0

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

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

Обчислимо значення Di по рядках як частку від ділення:

і з них виберемо найменше:

min (12 : 2 , 8 : 2 , - , 12 : 4 ) = 3

Отже, 4-ий рядок є провідним.

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

Формуємо наступну частину симплексної таблиці.

Замість змінної x в план 1 Замість змінної x2 .

Рядок, відповідної змінної x2 в планi 1, отриманий в результаті поділу всіх елементів рядка x6 плану 0 на дозвільний елемент ДE=4

На місці дозвільного елемента в плані 1 отримуємо 1.

В інших клітинах стовпця x2 плану 1 записуємо нулі.

Таким чином, у новому плані 1 заповнені рядок x2 і стовпець x2 .

Всі інші елементи нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

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

НE = СE - (А*В)/ДE

СДE - елемент старого плану, ДЕ - дозволяє елемент (4), А i В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДE.

План	Базис	B	x1	x2	x3	x4	x5	x6	min
2	x3	6	2	0	1	0	0	-1/2	3
x4	2	1	0	0	1	0	-1/2	2
x5	16	4	0	0	0	1	0	4
x2	3	0	1	0	0	0	1/4	-
Індексний рядок	F(X2)	9	-2	0	0	0	0	3/4	0

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

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

Обчислимо значення Di по рядках як частка від ділення:

і з них виберемо найменше:

min (6 : 2 , 2 : 1 , 16 : 4 , - ) = 2

Отже, 2-ий рядок є провідним.

Дозвільний елемент дорівнює (1) і стоїть на перетині ведучого стовпця і головною рядка.

Формуємо наступну частину симплексної таблиці.

Замість змінної x в план 2 Замість змінної x1 .

Рядок, відповідної змінної x1 в планi 2, отриманий в результаті поділу всіх елементів рядка x4 плану 1 на дозвільний елемент ДE=1

На місці дозвільного елемента в плані 2 отримуємо 1.

В інших клітинах стовпця x1 плану 2 записуємо нулі.

Таким чином, у новому плані 2 заповнені рядок x1 і стовпець x1 .

Всі інші елементи нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

НE = СE - (А*В)/ДE

СДE - елемент старого плану, ДЕ - дозвільний елемент (1), А i В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДE.

Оскільки в останньому стовпці присутні кілька мінімальних елементів 4, то номер рядка вибираємо за правилом Крек.

Метод Крек полягає в наступному. Елементи рядків, що мають однакові найменші значення min=4, діляться на передбачувані дозвільні елементи, а результати заносяться в додаткові рядки. За провідний рядок вибирається той, в якому раніше зустрінеться найменше приватне при читанні таблиці зліва направо по стовпцях.

План	Базис	B	x1	x2	x3	x4	x5	x6	min
3	x3	2	0	0	1	-2	0	1/2	4
x1	2	1	0	0	1	0	-1/2	-
x5	8	0	0	0	-4	1	2	4
x2	3	0	1	0	0	0	1/4	12
Індексний рядок	F(X3)	13	0	0	0	2	0	-1/4	0

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

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

Обчислимо значення Di по рядках як частку від ділення:

і з них виберемо найменше:

min (2 : 1/2 , - , 8 : 2 , 3 : 1/4 ) = 4

Отже, 1-ий рядок є провідним.

Дозвільний елемент дорівнює (1/2) і стоїть на перетині ведучого стовпця і головною рядка.

Формуємо наступну частину симплексної таблиці.

Замість змінної x в план 3 Замість змінної x6 .

Рядок, відповідної змінної x6 в плані 3, отриманий в результаті поділу всіх елементів рядка x3 плану 2 на дозвільний елемент ДE=1/2

На місці дозволяє елемента в плані 3 отримуємо 1.

В інших клітинах стовпця x6 плану 3 записуємо нулі.

Таким чином, у новому плані 3 заповнені рядок x6 і стовпець x6 .

Всі інші елементи нового плану 3, включаючи елементи індексного рядка, визначаються за правилом прямокутника.

НE = СE - (А*В)/ДE

СДE - елемент старого плану, ДЕ - дозвільний елемент (1/2), А i В - елементи старого плану, що утворюють прямокутник з елементами СДЕ і ДE.

Оскільки, індексний рядок не містить негативних елементів - знайдений оптимальний план.

Остаточний варіант симплекс-таблиці:

План	Базис	B	x1	x2	x3	x4	x5	x6
4	x6	4	0	0	2	-4	0	1
x1	4	1	0	1	-1	0	0
x5	0	0	0	-4	4	1	0
x2	2	0	1	-1/2	1	0	0
Індексний рядок	F(X4)	14	0	0	1/2	1	0	0

Оптимальний план можна записати так:

x6 = 4

x1 = 4

x5 = 0

x2 = 2

F(X) = 2•4 + 3•2 = 14

Завдання 2

Розв’язати задачі:

а) графічним методом;

б) методом симплексних таблиць;

в) скласти двоїсту задачу і розв’язати її.

Розв’язок

Розв’язок графічним методом.

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