Реферат: Математичне програмування

Завдання 1

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

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

Ресурси Витрати на один виріб Запас сировини, м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 55.56 x6 1000 2 3 4 1 1 250 x7 800 3 2 5 10 1 160 Індексний рядок F(X1) -12 -5 -15 -10

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

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

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

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

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

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

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

Обмеження: