Тема 4 теорія двоїстості та двоїсті оцінки в аналізі задач лінійного програмування
Економічна інтерпретація прямої та двоїстої задач лінійного програмування. Після оптимізаційний аналіз задач лінійного програмування. Аналіз діапазону зміни коефіцієнтів цільової функції. Параметричне програмування. Параметричні зміни вектора обмежень.
Пряма задача. Знайти максимум (мінімум) цільової функції
(1)
за умов
(2)
(3)
Потрібно знайти значення змінних , які задовольняють умовам (2) і (3), тоді як цільова функція набуває екстремального значення.
Форми запису ЗЛП
Задачу (1) – (3) зручно записати у вигляді:
За умов
(i=1,…m), Xj (j=1,2,…,n)
Або у векторно-матричному вигляді
За умов , де А- матриця коефіцієнтів при змінних; Х – вектор змінних; В – вектор вільних членів.
Розглянемо тепер цю саму задачу з іншого погляду. Допустемо, що за певних умов доцільно продавати деяку частину або всі наявні ресурси. Необхідно визначити ціни ресурсів.
Тема 5 Цілочислове програмування. Загальна характеристика цілочисельних задач і методів їх розв'язування. Нерівності Гоморі. Метод Гоморі.
Постановка завдання. Підприємство має запаси 4-х видів ресурсів (борошно, жири, цукор, фінанси), з яких виробляється 2 види продуктів (хліб і батон). Відомі:
норми витрат ресурсів на виробництво одиниці продукції; • запаси ресурсів; • ціни продуктів; • попит на хліб. Знайти оптимальний план виробництва, при якому дохід від реалізації виробленої продукції повинен бути максимальний. Економіко-математична модель. • Знайти план (кількість хліба і батонів) такий, щоб • Дохід = 0,99 * Хліб +1,21 * Батон - мах • При обмеженнях: 0,6 * Хліб +0,5 * Батон <= 120 0,05 * Хліб +0,08 * Батон <= 70 0,2 * Хліб +0,6 * Батон <= 65 0,2 * Хліб +0,24 * Батон <= 50 120 <= Хліб <= 150, а також Батон> = 0 Реалізація в Excel. Створюємо таблицю з формулами, які пов'язують план, обмеження та цільову функцію (Прибуток):
у стовпці «Використано» в кожну клітинку вводимо формулу обчислення кількості використаних ресурсів: = СУММПРОІЗВ (Норма; План); • в клітинку з Доходом вводимо формулу = СУММПРОІЗВ (Ціна; План). Рада. Якщо таблицю розмістити так, як показано, досить ввести формулу в першу клітинку, зафіксувати абсолютні координати плану (натиснути F4, щоб з'явилися символи $) і протягнути це формулу (маркером автозаповнення) до рядка Ціна. Запускаємо програму Пошук рішень командою Дані / Аналіз / Пошук рішення (У Excel 2007) Сервіс / Пошук рішення (У Excel 2003 і нижче). У полях Встановити цільову клітинку, Змінюючи клітинки, Обмеження вводимо відповідні адреси осередків. Так як це лінійна модель, то не забуваємо фіксувати у вікні Параметри пошуку рішень перемикач на позицію Лінійна модель і позитивне значення. Натискаємо кнопку Виконати і у вікні Результати пошуку рішення виводимо звіт за стійкістю.
Результат: щоб отримати максимальний дохід у розмірі 219,1 д. од. нам потрібно виробляти 150 од. хліба і 58,3 од. батона. Зі звіту за стійкістю бачимо, що ресурс Цукор дефіцитний і його «Тіньова ціна» становить 2 д. од., Це означає те, що якщо ми збільшимо цей ресурс на 1 од. наш дохід збільшиться на 2 і буде дорівнює 221,1 д. од. Цікаво те, що «нормована вартість» хліба - позитивне число (0,6) означає, що примусове збільшення випуску цього продукту збільшить дохід на 0,6 д. од. за кожну додаткову одиницю, оскільки ми самі занизили цю величину відповідно до попиту.
Асортиментне обмеження. Асортимент - набір товар в певній пропорції. Це досить поширене обмеження, особливо при випуску комплектів продуктів з одних і тих же ресурсів.
Наприклад, з металевого дроту потрібно зробити гайки і болти різних діаметрів в певному комплекті. Ми залишимо нашу задачу про хліб і батони, але тільки приберемо обмеження на попит і додамо асортиментна обмеження в такому співвідношенні Хліб / Батон = 3 / 1, 2, тобто, 1,2 Хліба = 3Батона.
У рядку Обмеження водимо формули 1,2 * Хліб і 3 * Батон відповідно. Потім запускаємо програму Пошук рішень і додаємо обмеження на асортимент. Отримуємо результат, де при заданому асортименті отримаємо максимальний дохід (217,7), якщо будемо виробляти 147,7 од. хліба і 59,1 од. батонів. Знову ми можемо вивести звіт по стійкості зробити певний аналіз і після цього додати цілочисельне обмеження на план
ТЕМА 6 НЕЛІНІЙНІ ОПТИМІЗАЦІЙНІ МОДЕЛІ ЕКОНОМІЧНИХ СИСТЕМ. Економічна і математична постановка задачі нелінійного програмування. Стохастичне програмування. Особливості математичної постановки задач стохастичного програмування
Зведення матричної гри до задачі лінійног програмування. Економічна сутність задач динамічного програмування.
Управління запасами. Постановка завдання. За статистикою середні витрати на утримання запасів становлять майже третину вартості цих запасів. Це дуже багато, і це показник зростає з ускладненням сучасного виробництва, де номенклатура все, що використовується, вимірюється десятками і сотнями тисяч найменувань, і тому дуже високий ризик збою або зупинки виробництва через відсутність хоча б однієї складової. Запаси на виробництві - це предмети, які стають частиною продукції або вносять вкладення у виробництво: сировина, готова продукція, комплектуючі, допоміжні матеріали і т. д. Запас у сфері послуг (магазин, салони, пошта, банки, ресторани, служби прокату і т . д.) - це товари на продаж, запасні частини, гроші, їжа, транспортні засоби, атракціони. Якщо запасів багато, це, одночасно добре (надійно забезпечується попит) і погано (великі витрати на зберігання) - тому повинна бути «золота середина» у вигляді оптимального запасу. Оптимально управляти запасом - значить, визначити такі моменти і обсяги постачання для поповнення запасів, що б мінімізувати загальні витрати на створення та отримання запасів відповідно з їх використанням (попит). Припущення: фіксований розмір замовлення; стабільні попит; миттєве поповнення запасу; відсутності дефіциту на готову продукцію. Вперше цю модель визначив Р. Вільсон (RH Wilson) у 1927 році і носить назву «формула Вільсона»: В англомовній літературі оптимальний запас називається економічна розмір замовлення, ЕРЗ (Economic Order Quantity, EOQ). У нашому випадку потрібно визначити оптимальний розмір замовлення чотирьох товарів, для кожного і них відомі ціни для покупки, попит, витрати на оформлення та зберігання одиниці продукції, а також обмеження на розмір складу і торбу фінансування покупки. Економіко-математична модель. 1. Знайти оптимальний план замовлення, щоб 2. Загальні витрати = Витрати на оформлення + Витрати на зберігання - min 3. При обмеженнях: Зайнята площа на складі <= Площа складу; Фінансування купівлі <= Бюджет; План> = 0. Реалізація в Excel. Створюємо таблицю з формулами, які пов'язують план, обмеження та цільову функцію (ОЗ):
• в стовпець ЕРЗ (економічний розмір замовлення) вводимо формули Вільсона; • стовпець Вартість вводимо формули: Розмір замовлення * Ціна; • в стовпець Витрати на зберігання вводимо формули: (Розмір замовлення * Витрати на хр.) / 2; • в стовпець Витрати на оформлення вводимо формули: (Витрати на оформ. * Попит) / Розмір замовлення; • в стовпець Загальні витрати вводимо формули суми стовпців Витрати на зберігання і оформлення; • стовпець Зайнята площа заповнюємо формулами: (Розмір замовлення * Розмір товару) / 2; • в рядок Усього вводимо формули суми за відповідними стовпцями
