1.2. Приклади задач лінійного програмування

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

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

Складемо математичну модель задачі. Нехай:

m - число ресурсів, що використовуються у виробництві;

n - число товарів, що можуть вироблятись з наявних ресурсів;

a_ij - кількість одиниць i-го ресурсу, що використовується для виробництва одиниці j-го товару;

b_i - максимальна кількість одиниць i-го ресурсу, що можна використати у виробництві (запас одиниць i-го ресурсу);

c_j - прибуток від реалізації одиниці j-го товару;

x_j- кількість одиниць j-го товару, що планується виробити (шукані величини).

Загальна кількість одиниць i-го ресурсу, що використовується у виробництві згідно з планом, становить a_i1x₁+a_i2x₂+...+a_inx_n (i=1,2,...,m)

Оскільки ця кількість одиниць не може перевершувати запас i- го ресурсу, то

a_i1x₁+a_i2x₂+...+a_inx_nb_i (i=1,2,...,m)

Очевидно, x_j0 (j=1,2,...,n)

Прибуток, одержаний від виробництва x_j одиниць j-го товару становить c_jx_j, а загальний прибуток від виробництва F_max=c₁x₁+c₂x₂+...+c_nx_n.

Таким чином, математична модель задачі є такою: знайти максимум лінійної форми: F_max=c₁x₁+c₂x₂+...+c_nx

за умов a_i1x₁+a_i2x₂+...+a_inx_nb_i (i=1,2,...,m)

x_j0 (j=1,2,...,n)

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

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

Складемо математичну модель задачі. Нехай:

m - число поживних речовин, що містяться в кормах;

n - число кормів, які використовуються для відгодівлі худоби;

a_ij - кількість одиниць i-ї поживної речовини, що міститься в одиниці j-го корму;

b_i - мінімальна добова потреба в i-й поживній речовині при відгодівлі худоби;

c_j - вартість одиниці j-го корму;

x_j - кількість одиниць j-го корму, що планується використати в добовому раціоні (шукані величини).

Загальна кількість i-ї поживної речовини, яка міститься в кормах раціону, становить a_i1x₁+a_i2x₂+...+a_inx_n (i=1,2,...,m).

Оскільки ця кількість одиниць не може бути меншою, ніж добова потреба в i-й поживній речовині, то a_i1x₁+a_i2x₂+...+a_inx_nb_i (i=1,2,...,m).

Очевидно, x_j0 (j=1,2,...,n)

Вартість x_j одиниць j-го корму становить c_jx_j, а загальна вартість добового раціону Z_min=c₁x₁+c₂x₂+...+c_nx_n

Таким чином, математична модель задачі є такою:

Z_min=c₁x₁+c₂x₂+...+c_nx_n

за умов

a_i1x₁+a_i2x₂+...+a_inx_nb_i (i=1,2,...,m)

x_j0 (j=1,2,...,n)