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

Завдання 1

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

Напідприємстві виготовляються вироби двох видів А і В. Для цього використовуєтьсясировина чотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно,21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількістьодиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од.відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од.Скласти план виробництва, який забезпечує найбільший прибуток.

Сировина Норма витрат сировини, од Запаси сировини, од. А В І 2 3 21 ІІ 1 4 ІІІ 1 6 ІV 2 1 10 Ціна, грн. од. 3 2

Розв’язок

 

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

∫ = 3х1+2х2.

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

CI =2х1 + 3х2,

CII =1х1 + 0х2,

CIII =0х1 + 1х2,

CIV =2х1 + 1х2,

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

2х1 + 3х2≤ 21

1х1≤ 4

1х2≤ 6

2х1 + 1х2≤ 10

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

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

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

/>

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

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

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

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

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

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

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

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

F(X) = 3 x1 +2 x2 — M x6 =>max

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

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

План Базис В

x1

x2

x3

x4

x5

x6

min 1

x3

21 2 3 1 10.5

x6

4

1

1

4

x4

6 1 1

x5

10 2 1 1 5 Індексний рядок F(X1) -400000

-100003

-2

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

математична модель симплекс транспортна задача екстремум

План Базис В

x1

x2

x3

x4

x5

x6

min 2

x3

13 3 1 -2 4.33

x1

4 1 1

x4

6 1 1 6

x5

2

1

1 -2

2

Індексний рядок F(X2) 12

-2

100003

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

План  Базис  В

 x1

 x2

 x3

 x4

 x5

 x6

Min  3

 x3

 7  0  0  1  0  -3  4  4.33

 x1

 4  1  0  0  0  0  1  0

 x4

 4  0  0  0  1  -1  2  6

 x2

 2  0  1  0  0  1  -2  2 Індексний рядок F(X3)  16  0  0  0  0  2 99999  0

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

 

Завдання 2

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

/>/>

/>

Розв’язок

 

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

/>

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

/>

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

/>

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

1х1-4ч2≥-8

-1х1+1х2≥-3

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

/>

/>

/>

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

/>

/>

/>

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

F(Y)=-8Y1-3Y2+9Y3 (max)

Обмеження:

1Y1-1Y2+2Y3≤2

-4Y1+1Y2+1Y3≤1

Y1≥0

Y2≥0

Y3≥0

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

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

-x1+4x2≤8

x1-x2≤3

2x1+x2≥9

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

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

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

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

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

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

F(X)= 2 x1 + x2 +M x6 =>min

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

План Базис В

x1

x2

x3

x4

x5

x6

Min 1

x3

8 -1 4 1

x4

3

1

-1 1

3

x6

9 2 1 -1 1 4.5 Індексний рядок F(X1) 900000

199998

99999 -100000

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

План Базис В

x1

x2

x3

x4

x5

x6

min 2

x3

11 3 1 1 3.67

x1

3 1 -1 1

x6

3

3

-2 -1 1

1

Індексний рядок F(X2) 300006

299997

-199998 -100000

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

План  Базис  В

 x1

 x2

 x3

 x4

 x5

 x6

min  3

 x3

 8  0  0  1  3  1  -1  3.67

 x1

 4  1  0  0  0.33  -0.33  0.33  0

 x2

 1  0  1  0  -0.67  -0.33  0.33  1  Індексний рядок  F(X3)  9  0  0  0  0  -1  -99999  0

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

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

x3 = 8

x1 = 4

x2 = 1

F(X) = 2*4 + 1*1 = 9

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

F(Y)=-8Y1-3Y2+9Y3 (max)

Обмеження:

1Y1-1Y2+2Y3≤2

-4Y1+1Y2+1Y3≤1

Y1≥0

Y2≥0

Y3≥0

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

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

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

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

План Базис В

x1

x2

x3

x4

x5

x4

2 1 -1 2 1

x5

1 -4 1 1 1 Індексний рядок F(X0) 8 3 -9

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