Що вивчає лінійне програмування?

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

Що таке задача лінійного програмування?

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

Що в лінійному програмуванні розуміють під планом?

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

Лінійне програмування - що це таке, визначення та поняття

Отже, лінійне програмування - це процес, за допомогою якого лінійна функція буде максимізована. Тобто рівняння першого ступеня, де змінні підняті до степеня 1.

Треба пам’ятати, що цей тип рівнянь є математичною рівністю, яка може мати одну або кілька невідомих. Таким чином, він має наступну основну форму, де a і b - константи, тоді як x і y - змінні.

Тепер, за допомогою лінійного програмування, цю функцію можна оптимізувати, знаходячи максимальне або мінімальне значення y. Це, беручи до уваги, що x підпадає під певні обмеження. Можливо, це більше ніж 0 і менше 20, наприклад.

Елементи лінійного програмування

Основними елементами лінійного програмування є наступні:

• Завдання: Це функція, яка оптимізована, або шляхом максимізації, або мінімізації її результату.
• Обмеження: Це ті умови, яким необхідно дотримуватися при оптимізації цільової функції. Це можуть бути алгебраїчні рівняння або нерівності.

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

Подивимось, на завершення, вправу лінійного програмування.

Припустимо, що ми маємо наступну функцію, яка виражає вигоду, яку отримує людина при придбанні певних товарів, - це корисність U та продукти, x та y.

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

У цьому випадку, якщо ми побудуємо графік функцій, ми зрозуміємо, що найбільша корисність виникає, коли людина купує лише добрий х (11 одиниць), маючи таким чином корисність 44 (4 × 11 + 0x7). Натомість, якщо ви придбаєте 9 одиниць x та 1 y, наприклад, ваш прибуток складе 42 (9 × 4 + 1 × 7). Тим часом, якщо ви витрачаєте все на хороший у, ви можете придбати лише 5, що дасть вам прибуток 35 (4 × 0 + 5 × 7).

Варто згадати, що на графіку вище сіра лінія є однією з кривих байдужості.

На цьому етапі ми також повинні пам’ятати, що товари x та y можуть приймати лише цілі значення.

Представлений випадок може бути з двома товарами, які задовольняють однакову потребу, наприклад, голод. Однак один з них, хороший x, хоча пропонує трохи менше корисності, є менш дорогим, за ціною 6 ВО, тоді як хороший y коштує більше, ніж вдвічі 14 ВО.

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

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

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

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

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

Економічна і математична постановка цілочислової задачі лінійного програмування [ ред. | ред. код ]

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

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

Див. також [ ред. | ред. код ]

Джерела [ ред. | ред. код ]