Основні властивості розв'язків задачі лінійного програмування - Розв'язання задач математичного програмування
Теорема 2.2. Множина всіх планів задачі лінійного програмування опукла.
Доведення. Необхідно довести, що коли X1 та X2 -- плани задачі лінійного програмування (2.1)--(2.3), то їх опукла комбінація X = Л1X1 + Л2X2, Л1 ? 0, Л2 ? 0, Л1 + Л2 = 1 також є планом задачі.
Так як X1 і X2 -- плани задачі, то виконуються такі співвідношення:
AX1 = A0, X1 ? 0; AX2 = A0, X2 ? 0.
Якщо підставити в систему обмежень значення X, то отримаємо:
AX = A(Л1X1 + Л2X2) = Л1AX1 + Л2AX2 = Л1A0 + Л2A0 = (Л1 + Л2)A0 = A0.
Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки Х1 ? 0, Х2 ? 0, Л1 ? 0, Л2 ? 0, то й Х ? 0, тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х -- план задачі лінійного програмування.
Теорема 2.3. Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин багатогранника розв'язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.
Рис. 2.3 Багатокутник розв'язків задачі у двовимірному просторі
Доведення. 1) Припустимо, що багатогранник розв'язків задачі Обмежений і має скінченну кількість кутових точок. Позначимо кутові точки через Х1, Х2,..., ХР, А оптимальний план -- Х0
Для значення Х0 Виконується нерівність F(X0) ? F(X). Припустимо, що Х0 не є кутовою точкою.
Отже, її можна подати як опуклу лінійну комбінацію кутових точок множини Q, тобто
X0 = Л1X1 + Л2X2 + ... + ЛPXP,
.
F(X) -- лінійна функція:
(2.16)
Припустимо, найбільше значення відповідає кутовій точці і позначимо його через m, тобто. Оскільки, то
.
За припущенням Х0 -- оптимальний план, отже, з одного боку, F(X0) ? F(XK) = M, а з другого, доведено, що F(X0) ? M, значить, F(X0) = M = F(XK), де XK -- кутова точка. Отже, лінійна функція досягає максимального значення в кутовій точці (XK).
2) Припустимо, що F(X) набирає максимальних значень більше, ніж в одній кутовій точці,
Наприклад у точках
Х1, Х2,..., ХQ, (1 ? Q ? P),
Тоді F(X1) = F(X2) = ... = F(XQ) = M.
Якщо Х Опукла лінійна комбінація цих кутових точок, то:
Тобто лінійна функція F набирає максимальних значень у довільній точці Х, яка є опуклою лінійною комбінацією кутових точок Х1, Х2,..., ХQ.
Рис. 2.4 Багатокутник розв'язку задачі у двовимірному просторі з необмеженою областю
Зауваження. Якщо багатокутник розв'язків -- Необмежена область (рис. 2.4), то не кожну точку можна подати у вигляді опуклої лінійної комбінації її кутових точок. У такому разі введемо в систему додаткове обмеження
Х1 + Х2 ? L,
Де L -- достатньо велике число. Введення цього обмеження означає відтинання прямою Х1 + Х2 = L від багатокутної необмеженої області обмеженого багатокутника, для якого виконується наведена теорема.
Очевидно, що координати кутових точок, які утворяться в результаті введення нового обмеження, залежать від L. Якщо в одній з них лінійна функція набирає максимального значення, то воно залежить від L. Змінюючи L, значення функціонала можна зробити як завгодно великим, а це означає, що лінійна функція необмежена на багатограннику розв'язків.
Теорема 2.4. Якщо відомо, що система векторів (K ? n) у розкладі, лінійно незалежна і така, що
,
Де всі XJ ? 0, то точка X = (X1, X2, ..., XK, 0, ..., 0) є кутовою точкою багатогранника розв'язків.
Доведення. Припустимо, що точка Х Не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок Х1 та Х2 багатокутника розв'язків, тобто:
Компоненти векторів Х1 та Х2, значення Л1 і Л2 невід'ємні і останні N - k компонентів вектора Х дорівнюють нулю, тому відповідні N - k Компонент векторів Х1 та Х2 також мають дорівнювати нулю, тобто
,
.
Оскільки Х1 та Х2 -- плани, то
,
.
Віднімаючи від першого рівняння друге, отримаємо:
.
За припущенням вектори лінійно незалежні, тому останнє співвідношення виконується, якщо
.
Звідси:
Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв'язків. Значить, Х -- кутова точка.
Теорема 2.5. Якщо -- кутова точка багатогранника розв'язків, то вектори в розкладі, , що відповідають додатним, є лінійно незалежними.
Доведення. Не порушуючи загальності, можна вважати нерівними нулю перші K елементів вектора Х, отже,
.
Здійснимо доведення від супротивного. Припустимо, що система векторів Лінійно залежна. Тоді існують такі числа, не всі рівні нулю, за яких виконується співвідношення:
.
За умовою
.
Задамо деяке число, помножимо на нього першу рівність, далі результат спочатку додамо до другого, а потім віднімемо від другого рівняння:
,
.
Отже, система рівнянь задачі лінійного програмування має два розв'язки, які можуть і не бути планами.
.
Всі ХІ > 0, тому число можна вибрати настільки малим, що всі перші компоненти та набуватимуть додатних значень, тоді та -- плани. При цьому, тобто Х -- опукла лінійна комбінація точок Х1 та Х2, що суперечить умові теореми, оскільки Х -- кутова точка.
Припущення стосовно лінійної залежності векторів привело до суперечності. Отже, воно є неправильним, а система векторів -- лінійно незалежна.
Наслідок 1. Оскільки вектори мають розмірність M, то кутова точка багатокутника розв'язків має не більше, ніж M додатних компонентів.
Наслідок 2. Кожній кутовій точці багатокутника розв'язків відповідає лінійно незалежних векторів системи.
З наведених властивостей можна висновувати:
Якщо функціонал задачі лінійного програмування обмежений на багатограннику розв'язків, то:
Існує така кутова точка багатогранника розв'язків, в якій лінійний функціонал досягає свого оптимального значення;
Кожний опорний план відповідає кутовій точці багатогранника розв'язків.
Тому для розв'язання задачі лінійного програмування необхідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.
Похожие статьи
-
1. За допомогою знака суми "". (2.6) 2. У векторно-матричному вигляді: Max(min) Z = CX АХ = А 0; (2.7) Х ? 0, Де , , Матриця коефіцієнтів; вектор...
-
Подамо схематично довільну економічну систему у такому вигляді (рис. 1.1): Рис. 1.1 Схема економічної системи Параметри С K ( K = 1, 2,..., l ) -...
-
Система ... називається системою обмежень, або системою умов задачі. Вона описує внутрішні технологічні та економічні процеси функціонування й розвитку...
-
Класифікація задач математичного програмування - Розв'язання задач математичного програмування
Рис. 1.2 Класифікація задач математичного програмування У математичному програмуванні виділяють два напрямки -- Детерміновані задачі і Стохастичні ....
-
Приклади економічних задач МП та їх моделей - Розв'язання задач математичного програмування
Задача визначення оптимального плану виробництва : для деякої виробничої системи (цеху, підприємства, галузі) необхідно визначити план випуску кожного...
-
Історична довідка - Розв'язання задач математичного програмування
Початком математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. (монографія "Математичні методи...
-
Умова цілочисловості є по суті нелінійною і може зустрічатися в задачах, що містять як лінійні, так і нелінійні функції. Задачі математичного...
-
Предмет та об'єкти математичного програмування - Розв'язання задач математичного програмування
Переклад англійського терміну Mathematical programming означає розроблення на основі математичних розрахунків Програми Дій для досягнення обраної мети ....
-
Методи розв'язування стохастичних задач поділяють на дві групи -- прямі та непрямі. Прямі методи використовують для розв'язування задач стохастичного...
-
Система диференціальних рівнянь, що записана у вигляді Чи у векторно-матричному вигляді Називається системою лінійних неоднорідних диференціальних...
-
Для побудови алгоритмів розв'язання задач матричних ігор використовується властивість оптимальних змішаних стратегій: оптимальна змішана стратегія...
-
Якщо в транспортній задачі не виконується така умова, тобто загальна кількість продукції постачальників не дорівнює загальному попиту всіх споживачів, то...
-
Умова задачі Бройлерне господарство птахівницької ферми налічує 20000 курчат, які вирощуються до 8-тижневого віку і після відповідної обробки надходять у...
-
До задач дробово лінійного програмування відносяться задачі нелінійного програмування математична модель яких в загальному можна представити в наступному...
-
ВСТУП, - Методи розв'язування різних типів економічних задач
Економіко-математичне моделювання є галуззю економічної науки, яка вивчає основні принципи та інструментарій постановки економічних задач, побудови їх...
-
Характеристичний багаточлен матриці, Розв'язання рівнянь - Вивчення математичного пакету MathСad
Для побудови характеристичного багаточлена матриці A використаємо символьні обчислення. Побудуємо матрицю D = A - Е, віднявши з діагональних елементів...
-
Всі економічні процеси та явища є динамічними, оскільки вони функціонують і розвиваються не тільки у просторі, але й у часі. Для народного господарства в...
-
ЗАТ "Біола" випускає три види продукції: напій на основі сиропу з цукром, напій на основі сиропу з цукрозамінником, сік. У поточному місяці прогнозуються...
-
1. записуємо цільову функцію та обмеження 2. приводимо систему обмежень до канонічної форми 3. знаходимо рівняння прямої. Будуємо ці прямі в системі...
-
Розв'язання систем рівнянь, Порядок виконання роботи - Вивчення математичного пакету MathСad
Матриця математичний пакет арифметичний Для розв'язання системи рівнянь з кількома невідомими треба задати початкові наближення для кожної змінної. Далі...
-
1. Задача оптимального планування виробництва. Визначити план виробництва х=(х1,...,хn)'(xj - шукана кількість одиниць продукції Pj), який би при заданих...
-
Методом розв'язку ТЗ є метод потенціалів. для того, щоб можна було застосувати цей метод, необхідне виконання 2х умов: - ТЗ є закритою; - побудовано...
-
Нехай функція F (х) задана на відрізку [a, b] . Розіб'ємо цей відрізок на N частин точками ділення А = х0 < x1 < x2 < ... < хn = b У кожному...
-
Закритою називається транспортна задача в якій загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто . Теорема:...
-
Опорний розвязок(план) - невідємний базисний розв'язок. Базисні розвязки - це частинний розвязок, який знаходиться якщо надати всім вільним змінним...
-
Перед пошуком розв'язку задачі зробимо деякі перетворення в моделі. Для перетворимо рівняння (2.2) і отримаємо: Отримаємо: Тепер підставимо отриманий...
-
Задачі, що привели до поняття визначеного інтеграла Розглянемо дві задачі -- геометричну та фізичну. 1. Обчислення площі криволінійної трапеції . Нехай...
-
В основі моделі (2.2.) - (2.6) лежить рівняння, яке має вигляд: , Зробимо просте перетворення, зробивши заміну: (2.7) І отримаємо рівняння (2.8): (2.8)...
-
Опорним називають базисний розв'язок, який не містить від'ємних чисел. Серед опорних розв'язків і міститься оптимальний розв'язок, що максимізує чи...
-
Перехід від одного опорного плану до іншого - Методи розв'язування різних типів економічних задач
Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї...
-
Складемо симплексну таблицю для першого опорного плану задачі. Елементи останнього рядка симплекс-таблиці є оцінками j, за допомогою яких опорний план...
-
РОЗВ'ЯЗУВАННЯ ЗАДАЧ НА НАДЛИШОК - Неметали та їхні сполуки
Ви знаєте, що речовини взаємодіють у певних співвідношеннях. Але часто одна з вихідних речовин береться у надлишку, щоб забезпечити повнішу взаємодію...
-
РОЗВ'ЯЗУВАННЯ ЗАДАЧ НА НАДЛИШОК - Загальні відомості про елементи
Ви знаєте, що речовини взаємодіють у певних співвідношеннях. Але часто одна з вихідних речовин береться у надлишку, щоб забезпечити повнішу взаємодію...
-
Цілочисельне програмування - різновид лінійного програмування, в якому отримані значення повинні бути цілими числами. Особливий інтерес до задач...
-
Оптимізаційна задача - це емм задача мета якої полягає у знаходженні найкращого виконання сформованих обмежуючих умов. K1, k2,k3 - знаки нерівності A,...
-
РОЗВ'ЯЗУВАННЯ ЗАДАЧ НА ВИХІД ПРОДУКТУ - Неметали та їхні сполуки
Ви розумієте, що в основі виробництва сульфатної кислоти (так само і будь-якого іншого хіміко-технологічного процесу) лежить хімічне перетворення речовин...
-
РОЗВ'ЯЗУВАННЯ ЗАДАЧ НА ВИХІД ПРОДУКТУ - Загальні відомості про елементи
Ви розумієте, що в основі виробництва сульфатної кислоти (так само і будь-якого іншого хіміко-технологічного процесу) лежить хімічне перетворення речовин...
-
Застосування подвійного інтегралу до задач механіки Статичні моменти. Центр маси пластини. Нехай матеріальна пластина в площині Оху має форму області D;...
-
Інтерполяцію можна розглядати як процес визначення для даного аргументу Х , який не потрапляє в таблицю экспериментальних значень, значення функції...
-
Розглянемо емпіричну залежність y=a+bx (1). Так як це лінійна функція, то ні яких перетворень не буде і x та y лишаються без будь-яких перетворень...
Основні властивості розв'язків задачі лінійного програмування - Розв'язання задач математичного програмування