3. Основні означення злп. Властивості множини планів злп. Основна теорема лінійного програмування.

ІІланом ЗЛП називається набір значень змінних (x₁; x₂;…x_n), що задовольняє повну систему обмежень. Розв’язком ЗЛП, або оптимальним планом, називається план, що забезпечує мінімум цільовій функції. План ЗЛП називається опорним, якщо його додатним компонентам відповідає система незалежних векторів. Опорний план ЗЛП називається невиродженим, якщо вектори, що відповідають його додатним компонентам, утворюють базис. У противному разі опорний план називається виродженим. Означення Числа Z_j-C_j називають оцінками векторів A_l або оцінками плану.

Властивості множини планів ЗЛП:

Позначимо множину планів ЗЛП.

Теорема . Множина є опуклою.

Теорема. Множина К є замкненою. /Доведення теореми ґрунтується на матеріалі, що виходить за рамки цього курсу, тому теорему приймають без доведення.

Теорема . Опорному плану ЗЛП відповідає кутова точка множини К.

Теорема. Кутовій точці множини К відповідає опорний план..

Теорема . Число кутових точок множини планів К скінчене.

Теорема9. Якщо ЗЛП має розв’язок, тобто цільова функція досягає мінімуму на множині К , то такого самого значення вона набуває принаймні в одній із кутових точок.

Примітка. Якщо К – опукла многогранна область, то цільова функція необмежена на К зверху й знизу. В першому випадку розв’язок ЗЛП існує й твердження теореми 2.9 правильне, в другому – ЗЛП розв’язку не має.

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

Теорема (ознака неоптимальності невироджених опорних планів). Якщо для деякого опорного невиродженого плану X₀ існує вектор A_l з додатною оцінкою Z_j-C_j>0, то X₀ не є оптимальним планом, тобто можна побудувати план Х^’, l-та компонента якого перевищує нуль і для нього

Теорема (достатня ознака оптимальності опорних планів). Якщо для деякого опорного плану X₀ оцінки всіх векторів недодатні Z_j-C_j≤0 (, то X₀ оптимальний план.

Примітка. Ця теорема справджується також для вироджених планів. Якщо X₀ – невироджений опорний план, то достатня ознака оптимальності є й необхідною. Якщо для деякого опорного плану існує вектор з додатною оцінкою, компоненти якого недодатні, то цільова ф-ія є необмеженою. ЗЛП не має розв.

4.Економічна постановка та математична модель задачі раціонального використання ресурсів. Економічна постановка. Підприємство випускає n видів продукції, використовуючи m видів ресурсів. Відомо матрицю питомих витрат ресурсів A = // a_ij // ( i = ; j = ), де a_ij - кількість одиниць і-го виду ресурсів, що витрачаються на виробництво одиниці j -го виду продукції. Запаси ресурсів виражаються величиною b_i ( і = ), а прибуток - c_j ( j = ).

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

Математична модель. Позначимо шуканий запланований випуск продук­ції j-го виду x_j ( j = ). Тоді цільова функція, що виражає ви­могу максимізувати сумарний прибуток Z, набуває вигляду

Z = c₁x₁ + c₂x₂ +…+ c_nx_n (max).

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

a₁₁x₁+a₁₂x₂+…+a_1nx_n<b₁;

a₂₁x₁+a₂₂x₂+…+a_2nx_n<b₂;

…………………………………

a_m1x₁+a_m2x₂+…+a_mnx_n<b_n

На змінні накладаються також умови невід’ємності:

x₁ 0; x₂ 0;…;x_n 0.

Щоб розв’язати задачу, треба визначити невід’ємні значення змінних х₁,х₂,...,х_n, які задовольняють систему основних обмежень і надають максимуму цільової функції .

5. Економічна постановка та математична модель задачі оптимального раціону харчування. Економічна постановка. Для відгодівлі худоби можна використовувати n видів кормів, які містять m видів поживних речовин. Вміст кожної з поживних речовин в одиниці кожного виду корму задається матрицею А= //a_ij// (i = ; j = ), де a_ij - вміст i-ї поживної речовини в одиниці j-го виду корму.Мінімальна добова норма становить b_i ( i= ), а вартість одиниці корму - c_j ( j = ).

Необхідно скласти добовий раціон, що задовольняє вимоги поживності та мінімальної вартості.

Математична модель. Позначимо кількість кормів, які йдуть на від­годівлю худоби, x₁,x₂,…,x_n. Тоді цільова функція, що виражає вимогу мінімізації вартості раціону, має вигляд: Z=c₁x₁+c₂x₂+…+c_nx_n (min)

Обмеження, що відображують вимогу поживності:

На змінні накладається також умова невід’ємності

x₁ 0; x₂ 0; …; x_n 0.

Розв’язок задачі – набір значень змінних х₁, х₂,..., x_n , який задовольняє і надає мінімуму цільовій функції.

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

6. Геометрична інтерпретація ЗЛП. Графо-аналітичний метод розв’язування ЗЛП. Система обмежень ЗЛП геометрично являє собою багатокутник або багатокутну область як перетинання напівплощин - геометричних образів нерівностей системи. Можна виділити два способи графоаналітичного розв’язування ЗЛП: повний перебір кутових точок; напрямлений перебір кутових точок, або градієнтний спосіб.

Можна виділити такі етапи розв’язування ЗЛП градієнтним способом.

1.Побудова К та його оцінка:

якщо К=Æ₁ – розв’язку немає;

якщо К Æ₁ – перехід до етапу 2

2. Побудова , тобто

3. Побудова лінії рівня, що має з К спільні точки.

4. Переміщення лінії рівня в напрямі , якщо розв’язується задача на максимум цільової функції, та в протилежному, якщо розв’язується задача на мінімум цільової функції, доки вона не стане опорною для К. Можливі три випадки:

1. опорна пряма з К має спільну точку, тоді розв’язком ЗЛП є координати цієї точки;

2. опорна пряма з К має спільний відрізок, або спільний промінь, тоді розв’язком ЗЛП є координати будь-якої точки цього відрізку або променю, тобто ЗЛП має незліченну множину розв’язків;

3. пряма не може стати опорною для К, тобто завжди перетинає К, отже, ЗЛП розв’язку не має – цільова функція необмежена на К

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

7.Симплексний метод. Основна ідея та алгоритм. Метод штучного базису (М-метод). CM – це обчислювальна схема, що дає змогу за наявності опорного плану спрямовано перебирати опорні плани доти, доки не буде знайдено оптимальний план або встановлено, що ЗЛП не має розв’язку.

Існує чотири етапи процедури CM:

- побудова початкового опорного плану,

- оцінка оптимальності плану;

- оцінка розв’язності ЗЛП;

- перехід від одного опорного плану до кращого.

Опишемо побудову початкового опорного плану. Нехай ортонормований базис утворюють перші т векторів. Тоді ЗЛП має вигляд

.

Випишемо відповідні вектори:

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

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

Якщо вектори А₁,А₂, ... ,А_m утворюють базис, то змінні х₁, х₂, ..., х_m –базисні, а змінні х_m+1, ..., x_п – вільні. За означенням невиродженого опорного плану, базисні змінні мають бути додатними, а вільні – нульовими. Прирівняємо в основній системі обмежень змінні х_m+1, ..., x_п до нуля, тоді базисні змінні набудуть значень х₁ = b₁, х₂ = b₂, ..., х_m = b_m. Отже, отримано початковий опор ний план:

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

Теорема (ознака неоптимальності невироджених опорних планів). Якщо для деякого опорного невиродженого плану існує вектор з додатною

оцінкою , то не є оптимальним планом, тобто можна побудувати план Х^’, l-та компонента якого перевищує нуль і для нього .

Теорема (достатня ознака оптимальності опорних планів). Якщо для деякого опорного плану оцінки всіх векторів недодатні ( , то оптимальний план.

Примітка. Ця теорема справджується також для вироджених планів. Якщо – невироджений опорний план, то достатня ознака оптимальності є й необхідною.

Метод штучного базису використовують для розв’язування ЗЛП, у яких серед відповідних векторів немає ортонормованого базису.

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

Отже, якщо задано ЗЛП

.

то після введення штучних змінних повна система обмежень набував вигляду

.

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

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