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

Завдання 1

При продажу двох видів товарів (А і В) торгове підприємство використовує чотири види ресурсів. Норми затрат ресурсів на 1 од. товару, об’єм ресурсів наведені в таблиці. Дохід від реалізації 1 од. товару А складає 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)