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

Лінійне програмування – розділ математичного програмування, апарат якого використовують для розв’язування значного класу лінійних прикладних задач планування в різних галузях народного господарства, наприклад:

• промисловість (планування завантаження обладнання, розподіл замовлень між підприємствами);

• сільське господарство (планування сівозміни, розподіл сількогосподарських машин згідно із замовленнями, пошук оптимального складу кормових концентратів);

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

• медицина (знаходження складу лікарських розчинів, складання рецептів лікарських препаратів);

• будівництво (вибір найкращих проектів будівництва нових об’єктів, оптимізація схем комунікацій);

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

1.1. Основні означення

1.1.1. Множина точок X на площині?є обмеженою, якщо існує коло радіуса скінченної довжини з центром у будь-якій точці множини, яке повністю містить у собі дану множину. В протилежному випадку така множина точок X є необмеженою. Існує гіперсфера скінченного радіуса?

1.1.2. Відрізок, який сполучає дві точки та , є множиною точок з координатами

де .

Нагадаємо, як утворюється таке рівняння: пряма, яка проходить через початок координат та точку , має вигляд , а рівняння прямої, яка проходить через дві точки та має вигляд

,

тому

.

За умови таке рівняння відображує відрізок прямої між двома точками та .

1.1.3. Множина точок простору Х є опуклою, якщо для будь-якої пари точок та до цього простору входить кожна точка відрізка

,

де , .

На рис. 1.1. зображено типи опуклих та не опуклих множин точок

Опуклі Неопуклі

Рис.1.1

Пряма – це окремий випадок опуклої області.

Розглянемо деякі властивості опуклих областей.

П еретин опуклих фігур завжди утворює також опуклу фігуру (рис.1.2).

Рис.1.2

Прикладом опуклої фігури на площині є трикутник, коло, прямокутник, сектор та ін.

Дайте означення епс-околу!

Точка А є граничною точкою множини М, якщо довільний -окіл містить точки, які як належать, так і не належать множині М.

Точка А є внутрішньою точкою М, якщо існує її -окіл , який є підмножиною множини М.

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

Приклади всіх типів точок зображені на рис.1.3.

внутрішня гранична кутова

Рис.1.3

1.1.4. Гіперплощина в n-вимірному просторі є множина точок, яка задовольняє лінійному рівнянню рівняння повинно містити знак „=”!!!

.

Очевидно, що гіперплощину можливо задавати перетином двох півпросторів

та .

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

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

.

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

.

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

2

3

Рис.1.5

1.1.7. Оскільки , то для скорочення викладення матеріалу надалі доцільно розглядати тільки задачі мінімізації цільової функції.

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

,

де .