19811

Задача лінійного програмування

Доклад

Информатика, кибернетика и программирование

Задача лінійного програмування Зада́ча ліні́йного програмува́ння задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями. Тобто необхідно мінімізувати 1 при обмеженнях 2 3 4 де cj ...

Украинкский

2013-07-17

29 KB

1 чел.

Задача лінійного програмування

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

Тобто, необхідно мінімізувати

(1)

при обмеженнях

, (2)

, (3)

, (4)

де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.

Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні.

Методи розв'язання

Метод потенціалів — розроблений в 1940 радянськими вченими Канторовичем та Гавуріним Л. В. в застосуванні до транспортної задачі;

Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.

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

Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.

Близький зв'язок між лінійним програмуванням та теорією ігор дає змогу використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.

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

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

Методів лінійного програмування недостатньо при накладанні додаткових обмежень на цілочисельність значень змінних. Вивченням таких задач займається цілочисельне програмування.

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


 

А также другие работы, которые могут Вас заинтересовать

6329. Філософія її призначення, зміст і функції в суспільстві 52.05 KB
  Філософія її призначення, зміст і функції в суспільстві План: Філософія як слово. Предмет філософії. Функції філософії. Цінність філософії для особи і суспільства. Слово Філософія - грецького походження, буквально означає...
6330. Сучасна вища школа в освітній системі України 75 KB
  Сучасна вища школа в освітній системі України План Система освіти України, її структура Принципи діяльності освітніх закладів Характеристика вищої освіти України початку третього тисячоліття 1. Система освіти України, її структура ...
6331. Поняття, суть і завдання кримінального процесу 81.48 KB
  Поняття, суть і завдання кримінального процесу ПЛАН: Вступ 1. Поняття, сутність та форми кримінального процесу. 2. Завдання кримінального процесу. 3. Система стадій кримінального процесу. 4. Кримінально-процесуальна форма, функції, відносини та гара...
6332. Соціологія як наука. Класифікація соціальних законів. Основні групи категорій соціології 94 KB
  Соціологія як наука Виникнення соціології як окремої науки. Етапи формування соціологічного знання. Предмет і об'єкт соціології. Класифікація соціальних законів. Основні групи категорій соціології. Місце соціології...
6333. Менеджмент програмних проектів 327.5 KB
  Менеджмент програмних проектів Процес розробки Моделі розробки додатків Модель водоспаду Спіральна модель Універсальний процес Етапи Фази Ітерації Компромісний трикутник Принципи моделі ...
6334. Фізіологія як наука. Фізіологія збудливих тканин 31.77 KB
  Фізіологія як наука. Фізіологія збудливих тканин. Фізіологія як наука. Про здоров'я і хворобу. Механізми регуляції фізіологічних функцій. Гомеостаз. Ритмічність фізіологічних функцій. Фізіологія збудливих тканин. Ф...
6335. Соціальна лінгвістика і її предмет 133 KB
  Соціальна лінгвістика і її предмет Визначення соціолінгвістики та її предмета. Проблеми сучасних соціолінгвістичних досліджень. Напрямки соціолінгвістичних досліджень. Історія становлення соціолінгвістики. Методи соціол...
6336. Історія України та її місце в системі вузівського навчання 22.77 KB
  Місце вітчизняної історії у системі вузівського навчання. 2 Предмет, завдання, методологічні принципи вивчення історії України. 3 Основні джерела вивчення історії України. 4 Наукова періодизація історії України. 1 Місце вітчизняної історії у...
6337. Праісторія українських земель. Ранньоісторичні племена які населяли територію України 33.94 KB
  Праісторія. Передісторія українських земель. Кіммерійці, скіфи, сармати на території Північного Причорномор'я. Античні міста-держави Північного Причорномор'я. Теорії походження слов...