Принцип побудови та постанова задачі лінійного програмування.

Методичні вказівки до виконання лабораторної роботи № 2

Тема: Реалізація математичних моделей лінійного програмування для пошуку оптимальних рішень засобами MS Excel

Ціль: вивчити методи лінійного програмування і способи їх реалізації в MS Excel

Завдання:

1) розглянути принцип побудови та постанову задачі лінійного програмування;

Знайти оптимальне рішення моделі лінійного програмування в MS Excel при заданих значеннях вхідних параметрів.

Хід роботи

Принцип побудови та постанова задачі лінійного програмування.

1.1. Побудова математичних моделей лінійного програмування.

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

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

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

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

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

Після побудови модель, якщо це можливо, спрощують.

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

При складанні добового раціону при відгодівлі худоби можна використовувати свіже сіно (не більше 50 кг) і силос (не більше 85 кг). Раціон повинен мати визначену поживність (число кормових одиниць не менше 30) і вміщувати поживні речовини: білок (не менше 1 кг), кальцій (не менше 100 г) і фосфор (не менше 80 г).

У наступній таблиці наведені дані про концентрацію необхідних елементів у 1 кг кожного корму та собівартості (коп./кг) цих кормів.

Необхідно скласти оптимальний добовий раціон годування худоби із умови мінімуму собівартості[1].

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

Невідомими в цьому рівнянні будуть ваги складових раціону, ікси.

Відомі константи при іксах, і відомі деякі обмеження, з яких теж потрібно скласти рівняння – рівняння обмежень.

Почнемо з них, як з більш легких.

Припустимо, вага сіна свіжого Х1 (в таблиці MS Excel буде В1 – за адресою). Тоді обмеження для сіна – Х1<=50

Аналогічно, силос Х2 (В2). Обмеження – Х2<=85

Далі, відомо, що на 1 кг сіна і на 1 кг силосу по 0,5 кг кормових одиниць, а в раціоні їх повинне бути не менше 30. Тобто більше або рівно. Тоді Х1*0.5+Х2*0.5>=30 (В1*0.5+В2*0.5>=30)

Поживних елементів в сіні і силосі:

білок Х1*0.04+Х2*0.01>=1 або В1*0.04+В2*0.01>=1

кальцій Х1*0.00125+Х2*0.0025>=0.1 або В1*0.00125+В2*0.0025>=0.1

фосфор Х1*0.002+Х2*0.001>=0.08 або В1*0.002+В2*0.001>=0.08

Тепер рівняння вартості: Х1*0.03+Х2*0.07→min або В1*0.03+В2*0.07→min

2. Розв’язання задачі проводиться з використанням табличного процесору MS Excel.

Для знаходження іксів необхідно внести всі складені рівняння на лист MS Excel, приймаючи при цьому, що В1-В2 – ікси, тобто поки що порожні чарунки, значення яких MS Excel і шукатиме перебором з урахуванням цільового рівняння і обмежень, в які ці ікси входять.

Рішення моделі в MS Excel при заданих значеннях вхідних параметрів.

2.1. Введіть всі рівняння на лист. Рівняння вводимо без «менше або рівно» та «більше або рівно», межі вводяться пізніше, у вікні пошуку рішення, в розділі обмежень. На рисунку 3.1 зображено, як виглядає лист зі введеними формулами (підрахованими та в режимі відображення формул).

2.2. Викличте пункт меню „ Сервіс ” – підпункт „ Пошук рішення ”. Бажано викликати з чарунки В4 (курсор в ній при завантаженні вікна пошуку), тоді посилання на цільове рівняння у вікні пошуку відразу вже буде встановлено (див. рис. 3.2).

Рисунок 3.2 – Виклик вікна „Поиск решения”

2.3. Введення обмежень у вікні “ Поиск решения”: тих, що розташовані на листі, а також умов не негативності.

Рисунок 3.3 - Вигляд діалогового вікна “Поиск решения” зі введеними адресами цільового рівняння та іксів

Додайте перше обмеження. Натисніть на кнопку «Добавить», в діалоговому вікні, що з'явилося, введіть посилання на рівняння кормових одиниць, знак >= виберіть з поля із списком, і також введіть константу – 0 (див. рис. 3.4).

Натисніть на кнопку «Добавить».

Знов з'явиться таке ж вікно для введення наступного обмеження.

Введіть і натисніть «Добавить».

Таким же чином вводимо ще 2 обмеження.

Додайте їх. В останньому обмеженні натисніть «ОК», а не «Добавить».

Рисунок 3.4 – Додавання обмежень у вікні “Поиск решения”

2.4. Знаходження рішення.

Отже, у вікні “ Поиск решения ” натисніть на кнопку „ Выполнить ” (див. рис. 3.5).

Рисунок 3.5 – Вікно “Поиск решения” підготоване для запуску пошуку на виконання

В результаті отримано шукане рішення – ікси В1 і В2 знайдені і заповнені, рівняння відповідно до них заповнені порахованими результатами, можна зберегти знайдений результат (див. рис. 3.6).

Рисунок 3.6 – Результати пошуку   рішення

В отриманій моделі можна змінювати коефіцієнти і параметри і одержувати нові варіанти добового раціону відгодовування.

Не нашли, что искали? Воспользуйтесь поиском: