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

Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А3B2, та позначаємо вершини циклу

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

Контрольная работа

Экономика

Другие контрольные работы по предмету

Экономика

Сдать работу со 100% гаранией

Завдання 1

 

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

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

 

РесурсиВитрати на один вирібЗапас сировини, м2СтолиСтільціТумбиКнижкові шафиДошки І виду, м251912500Дошки ІІ виду, м223411000Трудові ресурси, люд.год.32510800Прибуток від реалізації одного виробу, грн.од.1251510

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

 

Розвязок

 

Складаємо математичну модель задачі. Позначимо через х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

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

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

 

ПланБазисВx1x2x3x4x5x6x7min1x55005191210055.56x610002341010250x780032510001160Індексний рядокF(X1)0-12-5-15-100000

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

 

ПланБазисВx1x2x3x4x5x6x7min2x355.560.560.1111.330.1100100x6777.78-0.222.560-4.33-0.44100x7522.220.221.4403.33-0.56012350Індексний рядокF(X2)833.33-3.67-3.330101.67000

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

 

ПланБазисВx1x2x3x4x5x6x7min3x110010.21.82.40.200500x680002.60.4-3.8-0.410307.69x750001.4-0.42.8-0.601357.14Індексний рядокF(X3)12000-2.66.618.82.4000

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

 

ПланБазисВx1x2x3x4x5x6x7min4x138.46101.772.690.23-0.080500x2307.69010.15-1.46-0.150.380307.69x769.2300-0.624.85-0.38-0.541357.14Індексний рядокF(X4)2000007152100

Оскільки всі оцінки >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

 

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

 

ПланБазисВx1x2x3x4x5x6x7

min

1x6148-14-100101.75x727320-10019x51101001000Індексний рядокF(X1)41000001099995-1200003-100000-1000000000

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

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

ПланБазисВx1x2x3x4x5x6x7min2x11.751-1.75-0.13000.1300x721.7507.250.38-10-0.3813x511010010011Індексний рядокF(X2)2175008.750724988.2537499.38-1000000-137499.3800

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

 

ПланБазисВx1x2x3x4x5x6x7min3x1710-0.03-0.2400.030.240x23010.05-0.140-0.050.143x5800-0.050.1410.05-0.1411Індексний рядокF(X3)4400-0.02-1.620-99999.98-99998.380

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

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

 

x1 = 7

x2 = 3

x5 = 8

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

 

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

 

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

Обмеження:

8Y1+3Y2+0Y3≤5

-14Y1+2Y2-11Y3≤3

Y1≥0

Y2≥0

Y3≥0

 

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

 

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

-14x1 + 2x2-11x3 + 0x4 + 1x5 = 3

 

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

 

ПланБазисВx1x2x3x4x50x4583010x53-142-1101Індексний рядокF(X0)083-900

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

 

ПланБазисВx1x2x3x4x5min1x45830101.67x53-142-11011.5Індексний рядокF(X1)0-14-2711000

ПланБазисВx1x2x3x4x5min2X40.529016.51-1.50.0172X21.5-71-5.500.50Индексная строкаF(X2)40.5-2030-137.5013.50

ПланБазисВx1x2x3x4x53x10.0172100.5690.0345-0.0517x21.6201-1.520.24140.1379Индексная строкаF(X3)4400-2273

ПланБазисВx1x2x3x4x54x30.03031.76010.0606-0.0909x21.672.67100.33330Индексная строкаF(X4)44.6738.67008.331

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

x3 = 0.0303

x2 = 1.67

F(X) = 27*1.67 + -11*0.03 = 44.67

 

 

Завдання 3

 

Розвязати транспортну задачц.

 

141563001311225041223200100120907080

Розвязок

 

Побудова математичної моделі. Нехай xij кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби

 

 

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

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

Занесемо вихідні дані у таблицю.

 

В1В2В3В4В5В6ЗапасиА1141560300А2131120250А3412230200Потреби100120907080290

Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:

&

Похожие работы

1 2 >