На головну

Вступ

  1. I. Вступ
  2. I. Вступ
  3. I. ВСТУП
  4. I. Вступ.
  5. I. Вступ.
  6. I. Вступ.
  7. I. Вступ.

Будь-яка наука виникає в результаті зростаючого інтересу до певного класу задач, І розвитку методів і засобів за допомогою яких можна вирішити ці завдання. ISO не є винятком.

Назва дисципліни «дослідження операцій»Запозичене із західної літератури і з'явилося в 1940р. .

Перші формальні розробки по ІСО були розпочаті в Англії під час Другої світової війни і застосовувалися вони для планування бойових операцій, Звідси і виникла назва дисципліни.

Команда британських вчених сформулювала і вирішила завдання ефективної доставки військового спорядження на фронт.

Після закінчення війни методи ІСО були перенесені в цивільну сферу для підвищення ефективності і продуктивності економічної та виробничої діяльності.

Швидкий розвиток дисципліна отримує з 1962р. Це пов'язують з конкуренцією в комерційній сфері і швидким розвитком обчислювальної техніки.

Незважаючи на те, що сьогодні термін не зовсім точно відображає суть предмета, він зберігся до нашого часу.

лінійне програмування(ЛП) - один з перших і детально вивчених розділів математичного програмування. Саме з розділу лінійне програмування і почало розвиватися математичне програмування.

(Лінійне програмування застосовується в таких завданнях як управління і планування виробництва; в задачах визначення оптимального розміщення устаткування на морських судах, в цехах; в задачах визначення оптимального плану перевезень вантажу (транспортна задача); в задачах оптимального розподілу кадрів і т. Д.)

термін «Лінійне програмування» виник в результаті неточного перекладу з англійської «linear programming». Одне зі значень слова «programming» - складання планів, планування. Отже, правильним перекладом англійського «linear programming» було б не «лінійне програмування», а «лінійне планування», що більш точно відображає зміст дисципліни.

Перші роботи по лінійному програмуванню вийшли в Ленінградському державної реєстрацiї. Університеті. автором був Канторович Леонід Віталійович (1912-1986).

Народився в 1912р. в Санкт-Петербурзі. В 14 років вступив до Ленінградського університету на математичне відділення і закінчивши його в 1930р, залишається на викладацькій роботі. Канторович займається дослідженнями на кафедрі математики, і в 1935р (Йому 23 роки) йому присвоюється вчений ступінь доктора фізико-математичних наук.

У 1938 році, Канторович залучається в якості консультанта на фанерну фабрику і вирішує завдання ефективного використання обладнання.

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

Так вперше була сформульована задача виробничого планування, як завдання ЛП і розроблений метод для її вирішення. Результати його праці були опубліковані в 1939 р. в роботі «Математичні методи організації і планування виробництва». На жаль в цей час ці результати не були належним чином оцінені.

Визнання прийшло пізніше, в 60-і роки. В1975г. Канторович разом з американським економістом Тьяллінг Купмансом (1910-1985) був удостоєний Нобелівської премії з економіки «за внесок в теорію оптимального розподілу ресурсів».

На Заході батьком-засновником цього напряму вважають американського математика Джорджа Данцига (1914-2005).

Під час 2-ої Світової війни Данциг працював в командуванні військово-повітряних сил і займався програмуванням поставок військової техніки. Термін «програмування» був суто військовим і означав складання планів поставок.

Данциг запропонував використовувати лінійну модель, а в кінці 40-х років винайшов універсальний чисельний метод рішення, який наз. Симплексний метод.

Великий внесок у розвиток оптимізаційних методів внесли: Канторович Л. в., Немчинов В. с., Новожилов В. в. У 1965 р Вони були удостоєні Ленінської премії за розробку та впровадження оптимізують методів.

Значний внесок у теорію і методи лінійного програмування внесли С. Гасс, А. Таккер, Р. Гомори, Г. Кун, Т. Сааті, Г. Вагнер, Д. б. Юдін, Е. р Гольштейн і ін.

Завдання виробничого планування (або загальна задача ЛП). Різні форми запису її моделі.

Параметр управління,  - Кількість продукції, що випускається j-того виду.

Координатна форма запису

Цільова функція, Економічний сенс - максимізувати прибуток, одержуваний від випуску продукції:

 (1)

структурні обмеження - відображають вимога не перевитрачати запаси кожного виробничого фактора

- - - - - - - - - - - - - - (2)

- - - - - - - - - - - - - -

Умова невід'ємності параметра управління:

 (3)

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

Сj , bi - Задані постійні величини, а m> n.

Запис за допомогою знаків підсумовування

 - max

Векторно-матрична форма запису задачі

 Якщо скористатися матричними позначеннями, то задачу ЛП можна записати компактно. Позначимо С = (з1, з2, ..., Зj, ..., Зn ) - Вектор-рядок вартостей одиниць продукції.

x1 b1

x2 b2

... ...

X = xj ; - Вектор-стовпець змінних; B = bi - Вектор-стовпець;

... ... Обмежень

xn bm

a11 a12 ... a1j a1n

a21 a22 ... a2j a2n

A = - - - - - - матриця умов,

ai1 ai2 ... aij ain (Матриця технологічних коефіцієнтів)

- - - - - -

am1 am2 ... amj amn

       
   


0 = ... нульовий вектор стовпець

Тоді задача (1) - (3) запишеться:

Z = CX - max (1 ')

AX ? B (2 ')

X ? 0 (3 ')



ситуаційні завдання | Лекція 3 Геометрична інтерпретація і графічний спосіб вирішення задач ЛП
© um.co.ua - учбові матеріали та реферати