Загальний вигляд задачі лінійного програмування. Різні форми запису задач лінійного програмування

 

Функція, мінімум чи максимум якої шукаємо, називається цільовою функцією (критерієм, функціоналом).

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

, (1)

причому вектор повинен задовольняти систему співвідношень (обмежень)

(2)

де – деякі функції, – деякі дійсні числа,

та умову невід’ємності

, . (3)

Вектор , що задовольняє умови (2) і (3), називається допустимим розв’язком або планом задачі.

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

Множина наборів , , …, що задовольняють умови (2) і (3), називається областю визначення задачі або допустимою областю (допустимим розв’язком задачі).

План задачі , при якому цільова функція набуває мінімуму чи максимуму, називається оптимальним планом або оптимальним розв’язком задачі.

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

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

(4)

за умов

, (5)

(6)

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

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

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

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

Або якщо необхідно знайти найменше значення цільової функції за обмежень, записаних рівняннями та нерівностями , за умови, що

Задача знаходження найменшого значенння цільової функції еквівалентна до задачі знаходження найбільшого значення функції : .

Приклад 1. Задача про використання та оцінку ресурсів.

Меблева фабрика виготовляє столи, стільці, бюро та книжкові шафи, використовуючи для цього два різних види дощок, прочому фабрика має 500 м³ дощок першого виду і 1000 м³ дощок другого. Крім того задані трудові ресурси 800 людино-годин.

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

Таблиця 1

Ресурси	Витрати на один виріб
Столи	Стільці	Бюро	Книжкові шафи
Дошки першого виду, м3
Дошки другого виду, м3
Трудові ресурси, людино-години
Прибуток на один виріб, у.о.

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

На виготовлення одного стола витрачається 5 м³ деревини першого виду, а на виготовлення одного стільця – 1 м³ деревини першого виду, на виготовлення одного бюро – 4 м³, однієї книжкової шафи – 12 м³ деревини першого виду. Тоді на виготовлення столів витрачають 5м³ цієї деревини, на виготовлення стільців - м³ деревини першого виду, на виготовлення бюро - 4м³ деревини першого виду, на виготовлення книжкових шаф – 12м³ деревини першого виду. Всі витрати деревини першого виду становлять і не перебільшують запаси підприємства 500 м³, а витрати деревини другого виду становлять і не перебільшують запаси підприємства 1000 м³. Витрати трудових ресурсів становлять і не перебільшують 800 людино-годин.

Загальний прибуток підприємства від виробництва меблів становить:

.

Отже, маємо математичну постановку (математичну модель) задачі:

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