1.Загальна модель задачі лінійного програмування. Цільова функція задачі математичного програмування. Основні і неосновні обмеження. Оптимальні та допустимі розв’язки задачі лінійного програмування

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

max(min)Z=++…+

за умов:

n – кількість невідомих ;

m – кількість основних обмежень в системі.

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

max(min)Z=++…+ - цільова функція задачі (критерій, згідно якого шукається розв’язок задачі).

- основні обмеження системи.

- неосновні обмеження системи – це ті обмеження, які вказують, що розв’язки задач повинні бути невід’ємними.

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

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

2. Форми запису задач лінійного програмування. Перехід від однієї форми запису до іншої, їх еквівалентність

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

1. Загальна форма запису

max(min)Z=++…+

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

2. Стандартна (симетрична) форма запису

max(min)Z=++…+

Де – коефіцієнти при невідомих в цільовій функції, дійсні числа.

– невідомі, змінні задач.

- коефіцієнти при невідомих в системі обмежень, дійсні числа.

Особливості даної форми запису:

• Якщо задача на максимум, то усі основні обмеження є нерівностями виду «», якщо задача на min, то усі основні обмеження є нерівностями виду «»;

• На усі без винятку невідомі накладається умова невід’ємності.

3. Канонічна форма запису

max(min)Z=++…+

Особливості:

• Задача може бути як на max, так і на min,

• Усі основні обмеження є нерівностями,

• На усі без винятку невідомі накладається умова невід’ємності.

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

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

Перетворення за допомогою яких переходимо від однієї форми до іншої:

• Якщо задача на max maxZ=++…+, то її можна представити як задачу на пошук min – min(-Z)=--…- і навпаки.

• Будь-яка нерівність виду можна представити у вигляді нерівності .

• Нерівність можна представити у вигляді рівняння , де .

• Нерівність виду можна представити рівнянням , де .

• Будь-яке рівняння виду можна представити у вигляді системи двох нерівностей .

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