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

Завдання 1

Побудувати математичну модель задачі.

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

Ресурси	Витрати на один виріб				Запас сировини, м2
Ресурси	Столи	Стільці	Тумби	Книжкові шафи	Запас сировини, м2
Дошки І виду, м2	5	1	9	12	500
Дошки ІІ виду, м2	2	3	4	1	1000
Трудові ресурси, люд.год.	3	2	5	10	800
Прибуток від реалізації одного виробу, грн.од.	12	5	15	10

Визначити асортимент, що максимізує прибуток.

Розв’язок

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

∫ = 12х1+5х2 + 15х3+ 10х4.

Витрати сировини на виготовлення такої кількості виробів складають відповідно:

А =5х1+1х2 + 9х3+ 12х4,

В =2х1+3х2 + 4х3+ 1х4,

С =3х1+2х2 + 5х3+ 10х4,

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

5х1+1х2 + 9х3+ 12х4≤ 500

2х1+3х2 + 4х3+ 1х4≤ 1000

3х1+2х2 + 5х3+ 10х4≤ 800

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

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

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

Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х5 ≥ 0, х6≥ 0, х7≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 12х1+5х2 + 15х3+ 10х4 → max при обмеженнях

де х1,...,х7>0

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

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
1	x5	500	5	1	9	12	1	0	0	55.56
x6	1000	2	3	4	1	0	1	0	250
x7	800	3	2	5	10	0	0	1	160
Індексний рядок	F(X1)	0	-12	-5	-15	-10	0	0	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
2	x3	55.56	0.56	0.11	1	1.33	0.11	0	0	100
x6	777.78	-0.22	2.56	0	-4.33	-0.44	1	0	0
x7	522.22	0.22	1.44	0	3.33	-0.56	0	1	2350
Індексний рядок	F(X2)	833.33	-3.67	-3.33	0	10	1.67	0	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
3	x1	100	1	0.2	1.8	2.4	0.2	0	0	500
x6	800	0	2.6	0.4	-3.8	-0.4	1	0	307.69
x7	500	0	1.4	-0.4	2.8	-0.6	0	1	357.14
Індексний рядок	F(X3)	1200	0	-2.6	6.6	18.8	2.4	0	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
4	x1	38.46	1	0	1.77	2.69	0.23	-0.08	0	500
x2	307.69	0	1	0.15	-1.46	-0.15	0.38	0	307.69
x7	69.23	0	0	-0.62	4.85	-0.38	-0.54	1	357.14
Індексний рядок	F(X4)	2000	0	0	7	15	2	1	0	0

Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=38.46, х2=307.69, х3=0, х4=0, х5=0, х6=0, х7=69.23. Прибуток, при випуску продукції за цим планом, становить 2000 грн.

Завдання 2

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

Розв’язок

Пряма задача лінійного програмування має вигляд:

При обмеженнях:

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

Для досягнення відповідного вигляду помножимо 1-ю нерівність на -1

-2X1-5X2≥-10

В результаті отримаємо наступні матриці:

Для складання двоїстої задачі лінійного програмування знайдемо матриці АT, BT, C.

А, В, СТ.

Відповідно, двоїста задача лінійного програмування матиме вигляд:

F(Y)= 10Y1+28Y2-8Y3 (min)

Обмеження:

-2Y1+3Y2+1Y3≥ 5

-14Y1+2Y2-11Y3≥ 5

Y1≥0

Y2≥0

Y3≥0

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

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

2x1+5x2≥10

3x1+4x2≤28

x1-3x2≤5

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

2x1 + 5x2-1x3 + 0x4 + 0x5 = 10

3x1 + 4x2 + 0x3 + 1x4 + 0x5 = 28

1x1-3x2 + 0x3 + 0x4 + 1x5 = 5

Введемо штучні змінні x.

2x1 + 5x2-1x3 + 0x4 + 0x5 + 1x6 = 10

3x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 28

1x1-3x2 + 0x3 + 0x4 + 1x5 + 0x6 = 5

Для постановки завдання на максимум цільову функцію запишемо так:

F(X) = 8x1+2x2 - Mx6 => max

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

X1 = (0,0,0,28,5,10)

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

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
1	x6	10	2	5	-1	0	0	1	2
x4	28	3	4	0	1	0	0	7
x5	5	1	-3	0	0	1	0	0
Індексний рядок	F(X1)	-10M	-8-2M	-2-5M	1M	0	0	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
2	x2	2	0.4	1	-0.2	0	0	0.2	5
x4	20	1.4	0	0.8	1	0	-0.8	14.29
x5	11	2.2	0	-0.6	0	1	0.6	5
Індексний рядок	F(X2)	4	-7.2	0	-0.4	0	0	0.4+1M	0

План	Базис	В	x1	x2	x3	x4	x5	x6	min
3	x1	5	1	2.5	-0.5	0	0	0.5	0
x4	13	0	-3.5	1.5	1	0	-1.5	8.67
x5	0	0	-5.5	0.5	0	1	-0.5	0
Індексний рядок	F(X3)	40	0	18	-4	0	0	4+1M	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	min
4	x1	5	1	-3	0	0	1	0	0
x4	13	0	13	0	1	-3	0	1
x3	0	0	-11	1	0	2	-1	0
Індексний рядок	F(X4)	40	0	-26	0	0	8	1M	0

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