загрузка...
загрузка...
На головну

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

  1. CLIPS як багатофункціональне середовище програмування (інженерії знань)
  2. I. ЗАВДАННЯ АРТИЛЕРІЇ
  3. I. Приклади деяких розподілів дискретних випадкових величин
  4. I. Мета і завдання дисципліни
  5. II. Основні завдання та їх реалізація
  6. III. 12.2. Мислення і вирішення завдань
  7. IV тип завдань.

1. Завдання про використання ресурсів (планування виробництва). Для виготовлення двох видів продукції P1 и P2 використовують чотири види ресурсів S1, S2, S3 і S4 Запаси ресурсів, число одиниць ресурсів, що витрачаються на виготовлення одиниці продукції, дані в табл. 1.1 (цифри умовні):

Таблиця 1.1

 Вид продукції Вид ресурсу   P1   P2  запаси ресурсів
S1 S1 S3 S4

Прибуток, що отримується від одиниці продукції P1 и Р2, Відповідно 2 і 3 руб.

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

Складемо економіко-математичну модель задачі.

позначимо x1, x2 - Число одиниць продукції відповідно P1 и Р2 запланованих до виробництва. Для їх виготовлення потрібно (див. Табл. 1.1)  одиниць ресурсу S1,  одиниць ресурсу S3  одиниць ресурсу S3 і 3x1 одиниць ресурсу S4. Оскільки споживання ресурсів S1, S2, S3 и S4 не повинно перевищувати їх запасів, відповідно 18, 16, 5 і 21 одиниці, то зв'язок між споживанням ресурсів і їх запасами виразиться системою нерівностей:

 (1.1)

За змістом задачі змінні  (1.2)

сумарний прибуток F складе 2х1 руб. від реалізації продукції P1 і 3x2 руб. від реалізації продукції Р2, Тобто  . (1.3)

Отже, економіко-математична модель задачі матиме вигляд: знайти такий план випуску продукції X = (х1, x2), Що задовольняє системі (1.1) і умові (1.2), при якому функція (1.3) приймає максимальне значення.

Завдання легко узагальнити на випадок випуску n видів продукції з використанням m видів ресурсів.

позначимо xj (J = 1, 2, ..., n) - Число одиниць продукції Pj, Запланованої до виробництва; b1 (i = 1, 2, ..., m) - Запас ресурсу Si; aij - Число одиниць ресурсу S1, Що витрачається на виготовлення одиниці продукції Pj (числа aij часто називають технологічними коефіцієнтами); cj- Прибуток від реалізації одиниці продукції Pj.

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

 (1.4)

і умові  , (1.5)

при якому функція  (1.6) приймає максимальне значення.

2. Завдання складання раціону (завдання про дієту, завдання про сумішах). Є два види корму I і II, що містять поживні речовини (вітаміни) S1, S2 и S3. Зміст числа одиниць поживних речовин в 1 кг кожного виду корму і необхідний мінімум поживних речовин наведені в табл. 1.2 (цифри умовні). Вартість 1 кг корму I і II відповідно 4 і 6 руб.

Таблиця 1.2

 Поживна речовина (вітамін)  Необхідний мінімум поживних речовин  Число одиниць поживних речовин в 1 кг корму
I  II
S1 S1 S3

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

Складемо економіко-математичну модель задачі.

позначимо х1, х2 - Кількість кормів I і II, що входять в денний раціон. Тоді цей раціон буде включати (див. Табл. 1.2)  одиниць поживної речовини S1,  одиниць речовини S2 и  одиниць поживної речовини S3.Так Як вміст поживних речовин S1 S2 и S3 в раціоні повинно бути не менше відповідно 9, 8 і 12 одиниць, то отримаємо систему нерівностей:

 (1.7)

Крім того змінні  (1.8)

Загальна вартість раціону складе (в руб.)  . (1.9)

Отже, економіко-математична модель задачі: скласти денний раціон X = (х1, х2), Що задовольняє системі (1.7) і умові (1.8), при якому функція (1.9) приймає мінімальне значення.

Для формулювання завдання в загальній постановці позначимо: xj (j = 1, 2, ..., n) - Число одиниць корму n-го виду;  , - Необхідний мінімум змісту в раціоні поживної речовини Sij, aij - Число одиниць поживної речовини S1 в одиниці корму j-го виду; Сj- Вартість одиниці корму j-го виду. Тоді економіко-математична модель задачі матиме вигляд:

Знайти такий раціон X = (х1, х2, ..., xn), Що задовольняє системі

 (1.10)

і умові  , (1.11)

при якому функція  (1.12) приймає мінімальне значення.

3. Завдання про використання потужностей (про завантаження обладнання).Підприємству заданий план виробництва продукції за часом і номенклатурі: потрібно за час Т випустити п1, п2, ..., nk одиниць продукції P1, P2, ..., Pk Продукція виробляється на верстатах S1, S2, ..., Sm. Для кожного верстата відомі продуктивність аij (Тобто число одиниць продукції Pj; яке можна зробити на верстаті Si) І витрати bij на виготовлення продукції Pj на верстаті Si в одиницю часу.

Необхідно скласти такий план роботи верстатів (тобто так розподілити випуск продукції між верстатами), щоб витрати на виробництво всієї продукції були мінімальними.

Складемо економікj-математичну модель задачі.

позначимо хij - Час, протягом якого верстат Si буде зайнятий виготовленням продукції Pj (i = 1, 2, ..., m; j= 1, 2, ..., k).

Так як час роботи кожного верстата обмежена і не перевищує T, То справедливі нерівності:

 (1.13)

Для виконання плану випуску по номенклатурі необхідно, щоб виконувалися наступні рівності:

 (1.14)

Крім того,  (1.15)

Витрати на виробництво всієї продукції виразяться функцією  (1.16)

Економіко-математична модель задачі про використання потужностей набуде вигляду:

знайти таке рішення Х= (х11, х12, ..., xmk), Яке задовольняє системам (1.13) і (1.14) і умові (1.15), при якому функція (1.16) приймає мінімальне значення.

4. Завдання про розкрої матеріалів. На розкрій (розпил, обробку) надходить матеріал одного зразка в кількості а одиниць. Потрібно виготовити з нього l різних комплектуючих виробів в кількостях, пропорційних числах b1, b2 ..., bl (Умова комплектності). Кожна одиниця матеріалу може бути розкроєна п різними способами, причому використання i-го способу (i = 1, 2, ..., n) дає аik одиниць k-го виробу (k = 1, 2, ...,l).

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

Складемо економіко-математичну модель задачі.

позначимо хi - Число одиниць матеріалу, розкроюємо i-м способом, і х - Число виготовлених комплектів виробів. Так як загальна кількість матеріалу дорівнює сумі його одиниць, розкроюємо різними способами, то  . (1.17)

Вимога комплектності виразиться рівняннями  . (1.18)

Очевидно, що  . (1.19)

Економіко-математична модель набуде вигляду:

знайти таке рішення Х= (х1, х2, ..., xn), Яке задовольняє системі рівнянь (1.17) - (1.18) і умові (1.19), при якому функція F = х приймає максимальне значення.

приклад 1.1. Для виготовлення брусів довжиною 1,2 м, 3 м та 5 м в співвідношенні 2: 1: 3 на розпил надходить 195 колод довжиною 6 м. Визначити план розпилу, що забезпечує максимальне число комплектів. Скласти економіко-математичну модель задачі.

Рішення. Перш за все визначимо всілякі способи розпилу колод, вказавши відповідне число одержуваних при цьому брусів (табл. 1.3):

Таблиця 1.3

 Спосіб розпилу i  Число одержуваних брусів довжиною в м:
 1,2  3,0  5,0
 - -  - -  - - -

позначимо:  - Число колод, розпиляних i-м способом (i= 1,2,3,4); х - Число комплектів брусів.

З огляду на, що всі колоди повинні бути розпиляні, а числа брусів кожного розміру повинні задовольняти умові комплектності, економіко-математична модель задачі матиме вигляд:

F = х  max при обмеженнях

(i = 1, 2, 3, 4).

Завдання про розкрої легко узагальнити на випадок m розкроюємо матеріалів.

Нехай кожна одиниця j-го матеріалу (j = 1, 2, ..., m) Може бути розкроєна п різними способами, причому використання i-го способу (i = 1, 2, ..., n) дає аijk одиниць k-то вироби (k= 1, 2, ..., l»А запас j-го матеріалу дорівнює aj одиниць.

позначимо xij - Число одиниць j-го матеріалу, розкроюється i-м способом.

Економіко-математична модель задачі про розкрої в загальній постановці набуде вигляду: знайти таке рішення Х= (х11, х12, ..., xnm) Задовольняє системі

і умові  , При якому функція F = х приймає максимальне значення. 5.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   Наступна

ЗАГАЛЬНА ПОСТАНОВКА ЗАВДАННЯ лінійного програмування | Геометричний сенс рішень нерівностей, рівнянь і їх систем | ГЛАВА 4. ГЕОМЕТРИЧНИЙ МЕТОД ВИРІШЕННЯ ЗАВДАНЬ лінійного програмування | Геометрична інтерпретація симплексного методу | Відшукання максимуму лінійної функції | Відшукання мінімуму лінійної функції | при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці |

загрузка...
© um.co.ua - учбові матеріали та реферати