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

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

Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:

    1. Функції мети для якої знаходимо оптимальне значення

      Задача лінійного програмування

      де Задача лінійного програмування – апибуток від реалізації однієї i-ї продукції, а Задача лінійного програмування – кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів Задача лінійного програмуванняна протилежні, то функція Задача лінійного програмування змінюється на Задача лінійного програмування і навпаки.

    2. Обмеження по запасу ресурсів:

      Задача лінійного програмування

      де Задача лінійного програмування – нориа витрат i-го ресурсу; Задача лінійного програмування – кількість продукції j-го виду, випуск одиниці якої потребує Задача лінійного програмування витрат, також слід зазначити, що виличина Задача лінійного програмування не повинна бути від’ємною; Задача лінійного програмування – запаси i-го ресурсу; i=1,…,m – порядковий номер ресурсу; j=1,…,n – порядковий номер продукції.

Читати далі

Двоїста задача лінійного програмування

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

120

при обмеженнях:

216

39

Читати далі

Графічний метод. Приклад розв’язання задачі лінійного програмування графічним методом

Для виготовлення товару A і B підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A, B а також загальна кількість сировини наведені в наступній таблиці:

510

Потрібно організувати випуск даної продукції таким чином, щоб прибуток від її реалізації був максимальним.

Позначимо через 28 — кількість товару виду А; 33 — кількість товару виду В. Тоді математична модель даної задачі полягає у визначенні максимального значення функції мети:

215

при обмеженнях:

68

46

Читати далі

Графічний метод розв’язання задачі лінійного програмування

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

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

На відміну від графічного методу, симплекс-метод є більш універсальним, тобто дозволяє знайти розв’язок будь-якої задачі лінійного програмування. При рішенні задачі симплексним методом, обчислення ведуться в таблицях. Рішення задачі даним методом дає не тільки оптимальне рішення, але і рішення двоїстої задачі, залишки ресурсів і тому подібне.

Читати далі

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

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

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

при обмеженнях:

Читати далі