Лінійне програмування
 
а б в г д е ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
 

Лінійне програмування

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

  Типовим представником завдань Л. п. є наступна: знайти максимум лінійної функції

   (1)

  за умов

 , i = 1, 2 ..., m , (2)

  x j ³ 0, j = 1, 2, n , (3)

  де c j , a ij і b i — задані величини.

  Завдання Л. п. є математичними моделями багаточисельних завдань техніко-економічного вмісту. Розглянемо як приклад наступне завдання планерування роботи підприємства. Для виробництва однорідних виробів необхідно витратити різні виробничі чинники — сировину, робочу силу, верстатний парк, паливо, транспорт і так далі Зазвичай є декілька відпрацьованих технологічних способів виробництва, причому в цих способах витрати виробничих чинників в одиницю часу для випуску виробів різні. Кількість витрачених виробничих чинників і кількість виготовлених виробів залежить від того, скільки часу підприємство працюватиме за тим або іншим технологічним способом. Ставиться завдання раціонального розподілу часу роботи підприємства по різних технологічних способах, тобто такого, при якому буде вироблено максимальну кількість виробів при заданих обмежених витратах кожного виробничого чинника. Формалізуємо завдання. Хай є n технологічних способів виробництва виробів і m виробничих чинників. Введемо позначення: c j — кількість виробів, що випускаються в одиницю часу при роботі по j -у технологічному способу; a ij — витрата i -го виробничого чинника в одиницю часу при роботі по j -у технологічному способу; b i — наявні ресурси i-го виробничого чинника і x j — планований час роботи по j -у технологічному способу. Величина

   

  означає загальну витрату i-го виробничого чинника при плане х ( i ) = ( x ( i ) 1 , x ( i ) 2 ..., x ( i ) n ) . І оскільки ресурси обмежені величинами b i , то виникають природні умови (2) і (3). Ставиться завдання відшукання такого розподілу часу (оптимального плану) х* = ( x* 1 , х* 2 ..., х* n ) роботи за кожним технологічним способом, при якому загальний об'єм продукції був би максимальним, тобто завдання (1) — (3). Іншим характерним прикладом прикладних завдань Л. п. є транспортне завдання .

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

  Функцію (1) в Л. п. прийнято називати цільовою функцією, або критерієм ефективності, вектор х = ( x 1 , x 2 ..., x n ) — планом, вектор x*= ( x* 1 , x* 2 ..., x* n ) — оптимальним планом, а безліч, визначувана умовами (2), — (3), — допустимим, або безліччю планів. Одним з основних методів вирішення завдань Л. п. є сімплексний метод. Геометрично його ідея полягає в наступному. Допустима безліч (2) — (3) є опукла багатогранна безліч (якщо воно обмежене, то — багатовимірний опуклий многогранник). Якщо завдання Л. п. має рішення, то існує вершина х* багатогранної безлічі, що є оптимальним планом. Сімплексний метод полягає в такому направленому переборі вершин, при якому значення цільовій функції зростає від вершини до вершини. Кожній вершині відповідає система рівнянь, вибирана спец.(спеціальний) образом з системи нерівностей (2) — (3), тому обчислювальна процедура сімплексного методу полягає в послідовному вирішенні систем лінійних рівнянь алгебри. Простота алгоритму робить цей метод зручним для його реалізації на ЕОМ(електронна обчислювальна машина).

 

  Літ.: Юдін Д. Би., Гольштейн Е. Р., Лінійне програмування, М., 1969.

  Ст Р. Кишень.