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 році.

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

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

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

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

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

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

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


 

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

14272. Работа над художественным материалом в начальный период обучения 15.98 KB
  Работа над художественным материалом в начальный период обучения. В Педагогической практике работа над произведением принимает самые разнообразные формы в зависимости от личных качеств учащегося степени их одаренности и музыкального развития. Работа над произве...
14273. Рахманинов Сергей Васильевич (1873-1943) - композитор, пианист, дирижёр 251 KB
  Рахманинов Сергей Васильевич 18731943 композитор пианист дирижёр. Родился Рахманинов в дворянской семье в Старорусском уезде Новгородской губернии в имении Онег 20 марта 1873 г. История рода Рахманинова уходит корнями к внуку молдавского царя Стефана Вел
14274. Сказа́ние о неви́димом гра́де Ки́теже и деве Февро́нии 18.75 KB
  Сказа́ние о неви́димом гра́де Ки́теже и деве Февро́нии опера русского композитора Николая Андреевича РимскогоКорсакова. В опере четыре действия шесть картин. Основой сюжета стала легенда конца XVIII века о граде Китеже. РимскийКорсаков приступил к написанию музык
14275. Физика и музыка 371.5 KB
  Содержание Что называется высотой тона Что называется мажорной диатонической гаммой Что называется музыкальным интервалом Для чего служат черные клавиши на рояле и в органах Что называется равномерно темперированной гаммой Какова стандартная высота...
14276. Музыка в детских праздниках и представлениях 137.5 KB
  Реферат Музыка в детских праздниках и представлениях СОДЕРЖАНИЕ: ВВЕДЕНИЕ Роль праздников в развитии и воспитании детей. Значение и роль праздника. Построение праздника. Характеристика основных видов зрелищ для детей раннего возраста. М...
14277. Воздействие звука на человека 139.66 KB
  Воздействие звука на человека Что такое звук Звук представляет собой определенную вибрацию волну или энергию в пространстве. Вся Вселенная была создана Звуком. Согласно Библии: Вначале было Слово при помощи которого Бог творил нашу Вселенную. В индийской философи...
14279. Значение музыки в жизни человека 2.49 MB
  ВВЕДЕНИЕ В области музыки существует огромное поле для исследования а ее психическое влияние представляется очень малоизвестным современной науке. Нас учили что влияние музыки или звука и вибрации приходит к нам и затрагивает наши чувства снаружи; но остается еще
14280. Полонезы. Мазурки . Этюды 5.59 MB
  Полонезы. Мазурки. Этюды. План и содержание: Полонезы характеристика разбор полонезов: Adur №3 и esmoll №2. Мазурки характеристика разбор мазурок: Fdur №50 amoll № 49 fismoll №38 Cdur №15 amoll №13 Bdur №5. Этюды характерис