13. Математична постановка задачі лп.

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

Основним інструментом при вирішенні цих завдань стало математичне моделювання - формальний опис досліджуваного явища і дослідження з допомогою математичного апарату.

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

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

14.Перетворення математичного запису задачі лп для застосування симплекс методу.

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

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

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

Розглянемо задачу лінійного програмування, записану в канонічній формі:

.

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

(2.36)

(2.37)

(2.38)

Система обмежень (2.37) у векторній формі матиме вигляд:

, (2.39)

де

, ,..., ,

, …, , ,

— лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (2.39) базисними змінними будуть , а інші змінні — вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори — одиничні, то отримаємо один із розв’язків системи обмежень (2.37):

(2.40)

тобто допустимий план.

Такому плану відповідає розклад

(2.41)

де — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (§ 2.5) план є кутовою точкою багатогранника розв’язків, а отже, може бути почат­ковим опорним планом.