Industrialnet Головна Про сайт webcache.site checkip.site takescreenshot.site
  • Строрінки

  • Математичні моделі задач лінійного програмування

    Лінійне програмування

  • Математичні моделі задач лінійного програмування
  • Симплексний метод розв'язання задач лінійного програмування
  • Транспортна задача. Математична модель [1 ч.]
  • Транспортна задача. Опорне рішення [2 ч.]. Метод північно-західного кута
  • Зміст
  • Складові математичної моделі
  • Приклад складання математичної моделі
  • Канонічна форма завдання лінійного програмування
  • Приведення загальної задачі лінійного програмування до канонічної формі
  • Складові математичної моделі

    Основою для рішення економічних завдань є математичні моделі.

    Математичною моделлю задачі називається сукупність математичних співвідношень, що описують суть завдання.

    Складання математичної моделі включає:
  • вибір змінних задачі
  • складання системи обмежень
  • вибір цільової функції
  • Змінними задачі називаються величини Х1, Х2, Хп, які повністю характеризують економічний процес. Зазвичай їх записують у вигляді вектора: X=(X1, X2,...,Xn).

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

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

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

    Даний запис означає наступне: знайти екстремум цільової функції (1) і відповідні йому змінні X=(X1, X2,...,Xn) за умови, що ці змінні задовольняють системі обмежень (2) і умов неотрицательности (3).

    Допустимим розв'язком (планом) задачі лінійного програмування називається будь-n-мірний вектор X=(X1, X2,...,Xn), що задовольняє системі обмежень і умов неотрицательности.

    Безліч допустимих рішень (планів) завдання утворює область допустимих рішень (ОДР).

    Оптимальним розв'язком (планом) задачі лінійного програмування називається таке припустиме рішення (план) завдання, при якому цільова функція досягає екстремуму.

    Приклад складання математичної моделі Завдання використання ресурсів (сировини)

    Умова: Для виготовлення n видів продукції використовується m видів ресурсів. Скласти математичну модель.

    Відомі:

  • bi ( i = 1,2,3,...,m) — запаси кожного i-го виду ресурсу;
  • aij ( i = 1,2,3,...,m; j=1,2,3,...,n) — витрати кожного i-го виду ресурсу на виробництво одиниці об'єму j-го виду продукції;
  • cj ( j = 1,2,3,...,n) — прибуток від реалізації одиниці об'єму j-го виду продукції.
  • Потрібно скласти план виробництва продукції, який забезпечує максимум прибутку при заданих обмеженнях на ресурси (сировина).

    Рішення:

    Введемо вектор змінних X=(X1, X2,...,Xn), де xj ( j = 1,2,...,n) — обсяг виробництва j-го виду продукції.

    Витрати i-го виду ресурсу на виготовлення даного обсягу xj продукції дорівнюють aijxj, тому обмеження на використання ресурсів на виробництво всіх видів продукції має вигляд:
    Прибуток від реалізації j-го виду продукції дорівнює cjxj , тому цільова функція дорівнює:

    Відповідь - Математична модель має вигляд:

    Канонічна форма завдання лінійного програмування

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

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

    Вона може бути представлена в координатній, векторної і матричної запису.

    Канонічна задача лінійного програмування в координатній запису має вигляд:

    Канонічна задача лінійного програмування в матричній запису має вигляд:

    Тут:

  • А — матриця коефіцієнтів системи рівнянь
  • Х — матриця-стовпець змінних задачі
  • Ат — матриця-стовпець правих частин системи обмежень
  • Нерідко використовуються задачі лінійного програмування, що називаються симетричними, які в матричній записи мають вигляд:

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

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

    Це може бути зроблено наступним чином:

    Візьмемо лінійну нерівність a1x1+a2x2+...+anxn?b і додамо до його лівої частини деяку величину xn+1 , таку, що нерівність перетворилося в рівність a1x1+a2x2+...+anxn+xn+1=b. При цьому дана величина xn+1 є невід'ємної.

    Розглянемо все це на прикладі.

    Приклад 26.1

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

    Рішення:
    Перейдемо до задачі на відшукування максимуму цільової функції.
    Для цього змінимо знаки коефіцієнтів цільової функції.
    Для перетворення другого і третього нерівностей системи обмежень в рівняння введемо невід'ємні додаткові змінні x4 x5 (на математичній моделі ця операція позначена літерою Д).
    Змінна х4 вводиться в ліву частину другого нерівності зі знаком "+", так як нерівність має вигляд "?".
    Змінна x5 вводиться в ліву частину третього нерівності зі знаком "-", так як нерівність має вигляд "?".
    У цільову функцію змінні x4 x5 вводяться з коефіцієнтом. рівним нулю.
    Записуємо задачу в канонічному вигляді:

    Copyright © industrialnet.com.ua. 2016 • All rights reserved.