Математичні моделі задач лінійного програмування (стр. 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

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

Розв’язок

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

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

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

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

0х1-11х2≥-11

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

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

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

F(Y)= 14Y1+27Y2-11Y3 (max)

Обмеження:

8Y1+3Y2+0Y3≤5

-14Y1+2Y2-11Y3≤3

Y1≥0

Y2≥0

Y3≥0

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

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

8x1-14x2≥14

3x1+2x2≥27

x2≤11

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

Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.

8x1-14x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 14

3x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 27

0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 11

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

F(X) = 5 x1 +3 x2 +M x6 +M x7 => min

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
1	x6	14	8	-14	-1	0	0	1	0	1.75
x7	27	3	2	0	-1	0	0	1	9
x5	11	0	1	0	0	1	0	0	0
Індексний рядок	F(X1)	4100000	1099995	-1200003	-100000	-100000	0	0	0	0

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

математичний модель симплексний лінійний

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
2	x1	1.75	1	-1.75	-0.13	0	0	0.13	0	0
x7	21.75	0	7.25	0.38	-1	0	-0.38	1	3
x5	11	0	1	0	0	1	0	0	11
Індексний рядок	F(X2)	2175008.75	0	724988.25	37499.38	-100000	0	-137499.38	0	0

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

План	Базис	В	x1	x2	x3	x4	x5	x6	x7	min
3	x1	7	1	0	-0.03	-0.24	0	0.03	0.24	0
x2	3	0	1	0.05	-0.14	0	-0.05	0.14	3
x5	8	0	0	-0.05	0.14	1	0.05	-0.14	11
Індексний рядок	F(X3)	44	0	0	-0.02	-1.62	0	-99999.98	-99998.38	0

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

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

x1 = 7

x2 = 3

x5 = 8

F(X) = 5*7 + 3*3 = 44

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