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

Задача про використання сировини (планування виробництва)

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

За звичай, постановку таких задач оформляють у вигляді таблиць (дивись таблицю 2.1). Тут – кількість одиниць сировини , що йде на виготовлення одиниці товару ; – прибуток від реалізації одиниці товару .

Таблиця 2.1 – Вихідні дані
Види сировини	Запаси сировини	Види продукції
П1	П2	...	Пj	...	Пn
S1	b1	a11	a12	...	a1j	...	a1n
S2	b2	a21	a22	...	a2j	...	a2n
...	...	...	...	...	...	...	...
Si	bi	ai1	ai2	...	aij	...	ain
...	...	...	...	...	...	...	...
Sm	bm	am1	am2	...	amj	...	amn
Прибуток	c1	c2	...	cj	...	cn

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

(2.4)

і прибуток підприємства має вигляд

. (2.5)

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

Отже, математична модель даної задачі формулюється наступним чином: серед розв’язків системи лінійних нерівностей (2.4) потрібно знайти такий, при якому форма (2.5) приймає найбільше значення.

В таблиці 2.2 наведено конкретний приклад задачі про використання сировини для двох видів товару та чотирьох видів сировини.

Таблиця 2.2 – Вихідні дані
Види сировини	Види сировини	Запаси сировини	Види продукції
П1	П1
S1	S1		1	1
S2	S2		1	2
...	S3	21	1	5
Si	S4		6	1
...	Прибуток
Sm

Її математична модель має наступний вигляд:

(2.6)

. (2.7)

Задача про використання потужностей обладнання

Нехай підприємству задано план по часу і по номенклатурі: необхідно за час випустити одиниць продукції виду .

Кожен з видів товару може вироблятися машинами з різними потужностями, які задано таблицею 2.3. Тут кількість одиниць товару виду , що виробляє машина за одиницю часу. В таблиці 2.4 задано витрати – ціну одиниці робочого часу машини при виготовленні продукції кожного виду.

Таблиця 2.3 – Вихідні дані

Таблиця 2.4 – Вихідні дані

Машина

Види продукції

Машина

Види продукції

П1

...

Пj

...

Пn

П1

...

Пj

...

Пn

A1

a11

...

a1j

...

a1n

A1

b11

...

b1j

...

b1n

A2

a21

...

a2j

...

a2n

A2

b21

...

b2j

...

b2n

...

...

...

...

...

...

...

...

...

...

...

...

Ai

ai1

...

aij

...

ain

Ai

bi1

...

bij

...

bin

...

...

...

...

...

...

...

...

...

...

...

...

Am

am1

...

amj

...

amn

Am

bm1

...

bmj

...

bmn

План

N1

...

Nj

...

Nn

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

Таблиця 2.5 – Вихідні дані
Машина	Види продукції
П1	...	Пj	...	Пn
A1	x11	...	x1j	...	x1n
A2	x21	...	x2j	...	x2n
...	...	...	...	...	...
Ai	xi1	...	xij	...	xin
...	...	...	...	...	...
Am	xm1	...	xmj	...	xmn

Введемо невідомі – час роботи машини при виготовлені товару виду (таблиця 2.5). Вони повинні задовольняти наступним умовам:

Нерівності (2.8) вказують на те, що деякі з машин будуть працювати не повний час (можливе перевиконання плану).

(2.8)

Якщо вимагати, щоб машини працювали весь час , то система (2.8) прийме вигляд:

(2.9)

Загальні витрати на виготовлення продукції мають вигляд:

. (2.10)

Таким чином математична модель даної задачі формулюється наступним чином: серед розв’язків системи лінійних рівнянь і нерівностей (2.8) або (2.9) знайти такий, при якому функція (2.10) приймає найменше значення.

Задача складання раціону

Для збереження здоров’я людина повинна споживати за добу певну кількість білків, жирів, вуглеводів, води і вітамінів. Їх запаси в різних видах їжі різні. Складемо таблицю 2.6, де , – вид поживної речовини, , – мінімальна добова норма споживання поживної речовини ; – вартість одиниці їжі виду .

Таблиця 2.6 – Вихідні дані

Поживні речовини

Норма (мін. добова потреба)

Види продукції

I1

...

Ij

...

In

B1

b1

a11

...

a1j

...

a1n

B2

b2

a21

...

a2j

...

a2n

...

...

...

...

...

...

...

Bi

bi

ai1

...

aij

...

ain

...

...

...

...

...

...

...

Bm

bm

am1

...

amj

...

amn

Вартість

c1

...

cj

...

cn

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

Нехай , кількість їжі виду , яку споживає людина. Тоді математична модель задачі про складання раціону має наступний вигляд: серед усіх розв’язків системи лінійних нерівностей (2.11)

(2.11)

знайти такий, при якому функція

(2.12)

приймає найменше значення.

Задача про використання обладнання

Виробництву задано план по номенклатурі: потрібно виготовити , одиниць продукції виду . Кожний вид продукції виробляється певною кількістю машин , продуктивність яких (час затрачений на виготовлення одиниці товару певного виду) , задана таблицею 2.3. Потрібно скласти план, тобто знайти , – кількість продукції , яку потрібно виготовити на машині (дивись таблицю 2.5), щоб виконати план по номенклатурі за мінімальний час.

Математична модель задачі про використання обладнання: серед розв’язків системи лінійних рівнянь

(2.13)

знайти такий, при якому функція

(2.14)

приймає найменше значення, де

(1.15)

Транспортна задача

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

Таблиця 2.7 – Вихідні дані
Пункти відправлення	Пункти призначення	Запаси товару
B1	...	Bj	...	Bn
A1	c11	...	c1j	...	c1n	a1
A2	c21	...	c2j	...	c2n	a2
...	...	...	...	...	...	...
Ai	ci1	...	cij	...	cin	ai
...	...	...	...	...	...	...
Am	cm1	...	cmj	...	cmn	am
Потреби	b1	...	bj	...	bn

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

Позначимо через , кількість одиниць товару, які перевезені з в (дивись таблицю 2.8).

Таблиця 2.8 – Вихідні дані
	B1	...	Bj	...	Bn
A1	x11	...	x1j	...	x1n	a1
A2	x21	...	x2j	...	x2n	a2
...	...	...	...	...	...	...
Ai	xi1	...	xij	...	xin	ai
...	...	...	...	...	...	...
Am	xm1	...	xmj	...	xmn	am
	b1	...	bj	...	bn

Тоді математична, модель транспортної задачі має вигляд:

(2.16)

Серед розв’язків системи лінійних рівнянь (2.16) знайти такий, при якому лінійна форма

. (2.17)

приймає найменше значення.

Дата добавления: 2017-02-01