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

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

120

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

216

39

Читати повністю

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

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

510

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

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

215

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

68

46

Читати повністю

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

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

Розглянемо задачу лінійного програмування:

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

214

37

Читати повністю

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

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

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

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

Читати повністю

Розв'язок задачі лінійного програмування методом штучного базису

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

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

Читати повністю