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

Завдання 1

При продажу двохвидів товарів (А і В) торгове підприємство використовує чотири види ресурсів.Норми затрат ресурсів на 1 од. товару, об’єм ресурсів наведені в таблиці. Дохідвід реалізації 1 од. товару А складає 2 грн., товару В – 3 грн.

Ресурси Норма витрат ресурсів на 1 од. тов. Запас ресурсів А В 1 2 2 12 2 1 2 8 3 4 16 4 12 Дохід, грн. од. 2 3

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

Розв’язок

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

∫= 2х1+3х2.

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

CI=2х1 + 2х2,

CII=1х1 + 2х2,

CIII=4х1 + 0х2,

CIV=0х1 + 4х2,

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

2х1+ 2х2 ≤ 12

1х1+ 2х2 ≤ 8

4х1≤ 16

4х2≤12

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

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

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

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

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

2x1 + 2x2≤12

x1 + 2x2≤8

4x1≤16

4x2≤12

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

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

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

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

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

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

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

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

x3, x4, x5, x6,

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

X1 =(0,0,12,8,16,12)

План Базис B x1 x2 x3 x4 x5 x6 0 x3 12 2 2 1 0 0 0 x4 8 1 2 0 1 0 0 x5 16 4 0 0 0 1 0 x6 12 0 4 0 0 0 1 Індексний рядок F(X0) 0 -2 -3 0 0 0 0

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

План Базис B x1 x2 x3 x4 x5 x6 min 1 x3 12 2 2 1 0 0 0 6 x4 8 1 2 0 1 0 0 4 x5 16 4 0 0 0 1 0 - x6 12 0 4 0 0 0 1 3 Індексний рядок F(X1) 0 -2 -3 0 0 0 0 0

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

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

Обчислимозначення Di по рядках як частку від ділення:

і з них виберемонайменше:

min (12: 2, 8: 2, —, 12: 4 ) = 3

Отже, 4-ий рядокє провідним.

Дозвільнийелемент дорівнює (4) і стоїть на перетині ведучого стовпця і головного рядка.

Формуємонаступну частину симплексної таблиці.

Замість змінноїx в план 1 Замість змінної x2 .

Рядок, відповідноїзмінної x2 в планi 1, отриманий в результаті поділу всіх елементів рядка x6плану 0 на дозвільний елемент ДE=4

На місці дозвільногоелемента в плані 1 отримуємо 1.

В інших клітинахстовпця x2 плану 1 записуємо нулі.

Таким чином, уновому плані 1 заповнені рядок x2 і стовпець x2 .

Всі іншіелементи нового плану 1, включаючи елементи індексного рядка, визначаються заправилом прямокутника.

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

НE = СE — (А*В)/ДE

СДE — елементстарого плану, ДЕ — дозволяє елемент (4), А i В — елементи старого плану, щоутворюють прямокутник з елементами СДЕ і ДE.

План Базис B x1 x2 x3 x4 x5 x6 min 2 x3 6 2 0 1 0 0 -1/2 3 x4 2 1 0 0 1 0 -1/2 2 x5 16 4 0 0 0 1 0 4 x2 3 0 1 0 0 0 1/4 - Індексний рядок F(X2) 9 -2 0 0 0 0 3/4 0

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

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

Обчислимозначення Di по рядках як частка від ділення:

і з них виберемонайменше:

min (6: 2, 2: 1, 16: 4, — ) = 2

Отже, 2-ийрядок є провідним.

Дозвільнийелемент дорівнює (1) і стоїть на перетині ведучого стовпця і головною рядка.

Формуємонаступну частину симплексної таблиці.

Замість змінноїx в план 2 Замість змінної x1 .

Рядок, відповідноїзмінної x1 в планi 2, отриманий в результаті поділу всіх елементів рядка x4плану 1 на дозвільний елемент ДE=1

На місці дозвільногоелемента в плані 2 отримуємо 1.

В інших клітинахстовпця x1 плану 2 записуємо нулі.

Таким чином, уновому плані 2 заповнені рядок x1 і стовпець x1 .

Всі іншіелементи нового плану 2, включаючи елементи індексного рядка, визначаються заправилом прямокутника.

НE = СE — (А*В)/ДE

СДE — елементстарого плану, ДЕ — дозвільний елемент (1), А i В — елементи старого плану, щоутворюють прямокутник з елементами СДЕ і ДE.

Оскільки востанньому стовпці присутні кілька мінімальних елементів 4, то номер рядкавибираємо за правилом Крек.

Метод Крекполягає в наступному. Елементи рядків, що мають однакові найменші значенняmin=4, діляться на передбачувані дозвільні елементи, а результати заносяться вдодаткові рядки. За провідний рядок вибирається той, в якому ранішезустрінеться найменше приватне при читанні таблиці зліва направо по стовпцях.

План Базис B x1 x2 x3 x4 x5 x6 min 3 x3 2 0 0 1 -2 0 1/2 4 x1 2 1 0 0 1 0 -1/2 - x5 8 0 0 0 -4 1 2 4 x2 3 0 1 0 0 0 1/4 12 Індексний рядок F(X3) 13 0 0 0 2 0 -1/4 0

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

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

Обчислимозначення Di по рядках як частку від ділення:

і з них виберемонайменше:

min (2: 1/2,-, 8: 2, 3: 1/4 ) = 4

Отже, 1-ий рядокє провідним.

Дозвільнийелемент дорівнює (1/2) і стоїть на перетині ведучого стовпця і головною рядка.

Формуємонаступну частину симплексної таблиці.

Замість змінноїx в план 3 Замість змінної x6 .

Рядок, відповідноїзмінної x6 в плані 3, отриманий в результаті поділу всіх елементів рядка x3плану 2 на дозвільний елемент ДE=1/2

На місцідозволяє елемента в плані 3 отримуємо 1.

В інших клітинахстовпця x6 плану 3 записуємо нулі.

Таким чином, уновому плані 3 заповнені рядок x6 і стовпець x6 .

Всі іншіелементи нового плану 3, включаючи елементи індексного рядка, визначаються заправилом прямокутника.

НE = СE — (А*В)/ДE

СДE — елементстарого плану, ДЕ — дозвільний елемент (1/2), А i В — елементи старого плану,що утворюють прямокутник з елементами СДЕ і ДE.

Оскільки, індекснийрядок не містить негативних елементів — знайдений оптимальний план.

Остаточнийваріант симплекс-таблиці:

План Базис B x1 x2 x3 x4 x5 x6 4 x6 4 0 0 2 -4 0 1 x1 4 1 0 1 -1 0 0 x5 0 0 0 -4 4 1 0 x2 2 0 1 -1/2 1 0 0 Індексний рядок F(X4) 14 0 0 1/2 1 0 0

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

x6 = 4

x1 = 4

x5 = 0

x2 = 2

F(X) = 2•4 + 3•2= 14

Завдання 2

Розв’язатизадачі:

а) графічнимметодом;

б) методомсимплексних таблиць;

в) скластидвоїсту задачу і розв’язати її.

/>/>

Розв’язок

Розв’язокграфічним методом.

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

Межі області

Цільова функціяF(x) => min

Розглянемоцільову функцію завдання F = 7X1+5X2 => min.

Побудуємо пряму,що відповідає значенню функції F = 0: F = 7X1+5X2 = 0. Будемо рухати цю прямупаралельним чином. Оскільки нас цікавить мінімальне рішення, тому рухався прямодо першого торкання позначеної області. На графіку ця пряма позначенапунктирною лінією.

Рівний масштаб

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

Пряма F(x) =const перетинає область у точці A. Оскільки точка A отримана в результатіперетину прямих 4 i 3, то її координати задовольняють рівнянням цих прямих:

x2=0

3x1-5x2≥11

Вирішившисистему рівнянь, одержимо: x1 = 3.6667, x2 = 0

Звідки знайдемомінімальне значення цільової функції:

F(X) = 7*3.6667+ 5*0 = 25.67

Розв’язокметодом симплексних таблиць.

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

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

2x1+4x2≥1

5x1-x2≤42

3x1-5x2≥11

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

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

5x1-1x2 + 0x3 +1x4 + 0x5 = 42

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

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

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

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

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

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

F(X) =7x1+5x2+Mx6+Mx7 => min

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

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

З рівняньвисловлюємо штучні змінні:

x6 =1-2x1-4x2+x3

x7 =11-3x1+5x2+x5

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

F(X) = 7x1 + 5x2+ M(1-2x1-4x2+x3) + M(11-3x1+5x2+x5) => min

або

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

F(X) =(7-5M)x1+(5+1M)x2+(1M)x3+(1M)x5+(12M) => min

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

2 4 -1 0 0 1 0 5 -1 0 1 0 0 0 3 -5 0 0 -1 0 1

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

x6, x4, x7,

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

X1 =(0,0,0,42,0,1,11)

План Базис В x1 x2 x3 x4 x5 x6 x7 0 x6 1 2 4 -1 0 0 1 0 x4 42 5 -1 0 1 0 0 0 x7 11 3 -5 0 0 -1 0 1 Індексний рядок F(X0) 12M -7+5M -5-1M -1M 0 -1M 0 0

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

План Базис В x1 x2 x3 x4 x5 x6 x7 min 1 x6 1 2 4 -1 0 0 1 0 0.5 x4 42 5 -1 0 1 0 0 0 8.4 x7 11 3 -5 0 0 -1 0 1 3.67 Індексний рядок F(X1) 12M -7+5M -5-1M -1M 0 -1M 0 0 0

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

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

Обчислимозначення Di по рядках як частку від ділення

і з них виберемонайменше:

Отже, 1-ий рядокє ведучим

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

Формуємонаступну частину симплексної таблиці.

Замість змінноїx6 в план 1 увійде змінна x1

Рядок,відповідної змінної x1 в плані 1, отриманий в результаті поділу всіх елементіврядка x6 плану 0 на дозвільний елемент ДЕ=2

На місцідозвільного елемента в плані 1 отримуємо 1.

В інших клітинахстовпця x1 плану 1 записуємо нулі.

Таким чином, уновому плані 1 заповнені рядок x1 і стовпець x1 .

Всі іншіелементи нового плану 1, включаючи елементи індексного рядка, визначаються заправилом прямокутника.

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

НE = СE — (А*В)/ДE

СДЕ — елементстарого плану, ДЕ — дозвільний елемент (2), А і В — елементи старого плану, щоутворюють прямокутник з елементами СДЕ і ДЕ.

План Базис В x1 x2 x3 x4 x5 x6 x7 min 2 x1 0.5 1 2 -0.5 0 0 0.5 0 0 x4 39.5 0 -11 2.5 1 0 -2.5 0 15.8 x7 9.5 0 -11 1.5 0 -1 -1.5 1 6.33 Індексний рядок F(X2) 3.5+9.5M 0 9-11M -3.5+1.5M 0 -1M 3.5-2.5M 0 0

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

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

Обчислимозначення Di по рядках як частку від ділення

і з них виберемонайменше:

Отже, 3-ий рядокє ведучим

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

Формуємонаступну частину симплексної таблиці.

Замість змінноїx7 в план 2 увійде змінна x3

Рядок, відповідноїзмінної x3 в плані 2, отримана в результаті поділу всіх елементів рядка x7плану 1 на дозвільний елемент ДЕ=1.5

На місці дозвільногоелемента в плані 2 отримуємо 1.

В інших клітинахстовпця x3 плану 2 записуємо нулі.

Таким чином, уновому плані 2 заповнені рядок x3 і стовпець x3 .

Всі іншіелементи нового плану 2, включаючи елементи індексного рядка, визначаються заправилом прямокутника.

Кінець ітерацій:індексний рядок не містить негативних елементів — знайдений оптимальний план

Остаточнийваріант симплекс-таблиці:

План Базис В x1 x2 x3 x4 x5 x6 x7 3 x1 3.67 1 -1.67 0 0 -0.3333 0 0.3333 x4 23.67 0 7.33 0 1 1.67 0 -1.67 x3 6.33 0 -7.33 1 0 -0.6667 -1 0.6667 Індексний рядок F(X3) 25.67 0 -16.67 0 0 -2.33 -1M 2.33-1M

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

x1 = 3.67

x4 = 23.67

x3 = 6.33

F(X) = 7*3.67 =25.67

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

2y1+5y2+3y3≤7

4y1-y2-5y3≤5

y1+42y2+11y3=> max

y1 ≥ 0

y2 ≤ 0

y3 ≥ 0

Рішення двоїстоїзадачі дає оптимальну систему оцінок ресурсів.

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

З першої теоремидвоїстості випливає, що Y = C*A-1.

Складемо матрицюA з компонентів векторів, що входять в оптимальний базис.

Визначившизворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:

Як видно з останньогоплану симплексної таблиці, зворотна матриця A-1 розташована в стовпцяхдодаткових змінних .

Тоді Y = C*A-1 =

Оптимальний пландвоїстої задачі дорівнює:

y1 = 0

y2 = 0

y3 = 2.33

Z(Y) =1*0+42*0+11*2.33 = 25.67

Завдання 3

Знайтипочатковий розв’язок транспортної задачі методом «північно-західного кута» імінімальної вартості. Вибравши один із знайдених початкових розв’язків, знайтиоптимальний розв’язок транспортної задачі.

3 5 1 4 200 4 1 2 3 140 1 2 3 5 160 90 110 220 80 500

Розв’язок

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

Умовабалансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі єзакритою.

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

В1 В2 В3 В4 Запаси А1 3 5 1 4 200 А2 4 1 2 3 140 А3 1 2 3 5 160 Потреби 90 110 220 80

Розпочинаємобудувати математичну модель даної задачі:

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

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

Загальнівитрати, пов’язані з транспортуванням продукції, визначаються як сума добутківобсягів перевезеної продукції на вартості транспортування од. продукції довідповідного замовника і за умовою задачі мають бути мінімальними. Томуформально це можна записати так:

minZ=3x11+5x12+1x13+4x14+4x21+1x22+2x23+3x24+1x31+2x32+3x33+4x34.

Загалом математична модельсформульованої задачі має вигляд:

minZ=3x11+5x12+1x13+4x14+4x21+1x22+2x23+3x24+1x31+2x32+3x33+4x34.

за умов:

Запишемо умовизадачі у вигляді транспортної таблиці та складемо її перший опорний план у ційтаблиці методом «північно-західного кута».

Ai Bj ui b1 = 90 b2 = 110 b3 = 220 b4=80 а1 = 200 3 5

200

4 u1 = а2 = 140

2 3 u2 = а3 = 160 1

u3 = vj v1 = v2 = v3 = v4 =

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

Підрахуємо числозайнятих клітин таблиці, їх 6, а має бути m + n — 1 = 6. Отже, опорний план єне виродженим.

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

Ai Bj ui b1 = 90 b2 = 110 b3 = 220 b4=80 а1 = 200 3 5

200

4 u1 = 0 а2 = 140 4

[-] 110

[+] 10

u2 = 1 а3 = 160

[+]

[-] 70

u3 = 3 vj v1 = -2 v2 = 0 v3 = 1 v4 = 2

Підрахуємо числозайнятих клітин таблиці, їх 6, а має бути m + n — 1 = 6. Отже, опорний план є невиродженим.

Для розв’язкувізьмемо останній опорний план.

Перевіримооптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинамтаблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:

u1=0, u2=0, u3=3,v1=-2, v2=0, v3=1 v4=2. Ці значення потенціалів першого опорного планузаписуємо у транспортну таблицю.

Потім згідно залгоритмом методу потенціалів перевіряємо виконання другої умови оптимальностіui + vj ≤ cij (для порожніх клітинок таблиці).

Опорний план неє оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

(3;2): 3 + 0> 2; ∆32 = 3 + 0 — 2 = 1

(3;3): 3 + 1> 3; ∆33 = 3 + 1 — 3 = 1

max(1,1) = 1

Тому від ньогонеобхідно перейти до другого плану, змінивши співвідношення заповнених іпорожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 2.Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинахбагатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

Тепер необхідноперемістити продукцію в межах побудованого циклу. З вантажів хij що стоять вмінусових клітинах, вибираємо найменше, тобто у = min (3, 4) = 70. Додаємо 70до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, щостоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Усі іншізаповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другутаблицю без змін. Кількість заповнених клітинок у новій таблиці також маєвідповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

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

Ai Bj ui b1 = 90 b2 = 110 b3 = 220 b4=80 а1 = 200 3 5

200

4 u1 = 0 а2 = 140 4

u2 = 1 а3 = 160

3 5 u3 = 2 vj v1 = -1 v2 = 0 v3 = 1 v4 = 2

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

Знайдемопотенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij,вважаючи, що u1 = 0.

u1 + v3 = 1; 0 +v3 = 1; v3 = 1

u2 + v3 = 2; 1 +u2 = 2; u2 = 1

u2 + v2 = 1; 1 +v2 = 1; v2 = 0

u3 + v2 = 2; 0 +u3 = 2; u3 = 2