Смекни!
smekni.com

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

Завдання 1

Цех випускає вали і втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки – 2 год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а від реалізації однієї втулки – 60 грн. Цех має випустити не менше 100 валів і не менше 200 втулок. Скільки валів і скільки втулок має випустити цех, щоб одержати найбільший прибуток, якщо фонд робочого часу робітників становить 900 людино-годин?

Ресурс Вироби Фонд робочого часу
Вали Втулки
Робітник, год. од. 3 2 900
Вартість, грн. од. 80 60

Розв’язок

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

∫ = 80х1+60х2.

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

CI =3х1+2х2,

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


3х1+2х2≤900

Окрім того, валів потрібно виготовити не менше 100 штук, а втулок – 200 шт., тобто повинні виконуватись ще нерівності: х1≥100, х2≥ 200.

Таким чином, приходимо до математичної моделі:

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

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

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

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

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

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

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

F(X) = 80 x1 +60 x2 - M x6 - M x7 => max

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

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

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

x6 = 100-x1 +x4

x7 = 200-x2 +x5

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

F(X) = 80x1 + 60x2 - M(100-x1 +x4 ) - M(200-x2 +x5 ) => max

або

F(X) = (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max

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

3 2 1 0 0 0 0
1 0 0 -1 0 1 0
0 1 0 0 -1 0 1

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

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

x3 , x6 , x7

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

X1 = (0,0,900,0,0,100,200)

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

Складаємо симплекс-таблицю:

План Базис В x1 x2 x3 x4 x5 x6 x7 min
1 x3 900 3 2 1 0 0 0 0 300
x6 100 1 0 0 -1 0 1 0 100
x7 200 0 1 0 0 -1 0 1 0
Індексний рядок F(X1) -30000000 -100080 0 -100060 0 100000 0 0 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min
2 x3 600 0 2 2 0 3 -3 0 300
x1 100 1 0 0 0 -1 1 0 0
x7 200 0 1 1 0 0 0 1 200
Індексний рядок F(X2) -19992000 0 0 -100060 0 -80 100080 0 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min
3 x3 200 0 0 1 3 2 -3 -2 66,67
x1 100 1 0 0 -1 0 1 0 0
x2 200 0 1 0 0 -1 0 1 0
Індексний рядок F(X3) 20000 0 0 0 -80 -60 100080 100060 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min
4 x4 66,67 0 0 0,33 1 0,67 -1 -0,67 100
x1 166,67 1 0 0,33 0 0,67 0 -0,67 250
x2 200 0 1 0 0 -1 0 1 0
Індексний рядок F(X4) 25333,33 0 0 26,67 0 -6,67 100000 100006,67 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min
5 x5 100 0 0 0,5 1,5 1 -1,5 -1 100
x1 100 1 0 0 -1 0 1 0 250
x2 300 0 1 0,5 1,5 0 -1,5 0 0
Індексний рядок F(X5) 26000 0 0 30 10 0 99990 100000 0

Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=100, х2=300. Прибуток, при випуску продукції за цим планом, становить 26000 грн.


Завдання 2

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

Розв’язок

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

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

x1+2x2≤6

-5x1+4x2≤2

7x1+5x2≥35

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

1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 6

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

7x1 + 5x2 + 0x3 + 0x4-1x5 = 35

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


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

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

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

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

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

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

X1 = (0,0,6,2,0,35)

План Базис В x1 x2 x3 x4 x5 х6
0 х3 6 1 2 1 0 0 0
x4 2 -5 4 0 1 0 0
х6 35 7 5 0 0 -1 1
Індексний рядок F(X0) 0 0 0 0 0 0 0

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

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

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

План Базис В x1 x2 x3 x4 x5 x6 min
2 х3 1 0 1,29 1 0 0,1429 -0,1429 7
x4 27 0 7,57 0 1 -0,7143 0,7143 0
х1 5 1 0,7143 0 0 -0,1429 0,1429 0
Індексний рядок F(X2) 0 0 0 0 0 0 0 0

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

План Базис В x1 x2 x3 x4 x5 x6
3 х5 7 0 9 7 0 1 -1
x4 32 0 14 5 1 0 0
х1 6 1 2 1 0 0 0
Індексний рядок F(X3) 0 0 0 0 0 0 0

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

x5 = 7

x4 = 32

x1 = 6

F(X) = 3*6 = 18

Складемо двоїсту задачу до поставленої задачі лінійного програмування.

y1+5y2+7y3≥3

2y1-4y2+5y3≥1

6y1-2y2+35y3 => min

y1 ≥ 0

y2 ≤ 0

y3 ≤ 0

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

Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1. Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.