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

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

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

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

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

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

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

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


 

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

10888. Технологія робіт лобзиком. Технологічний процес пиляння. Прийоми пиляння лобзиком. Організація робочого місця 75 KB
  Тема. Технологія робіт лобзиком. Технологічний процес пиляння. Прийоми пиляння лобзиком. Організація робочого місця. Мета: сформувати в учнів поняття про процес різання та уявлення про технологію пиляння фанери і ДВП; розвивати політехнічне мислення; виховувати культу...
10889. Процес випилювання з фанери й ДВП, обпилювання, шліфування 237 KB
  Тема уроку: Процес випилювання з фанери й ДВП обпилювання шліфування. Мета уроку. Формування вмінь виконувати обпилювання фанери; закріплення знань про обпилюваяння деревини. Розвивати точність окомір. Виховувати акуратність виконавчу дисципліну творче ставлення д
10890. Технологія обробітку та захисту ґрунтів 63.5 KB
  Тема уроку: Технологія обробітку та захисту ґрунтів. Мета уроку. Засвоєння знань про типи структуру та родючість ґрунтів; ручні знаряддя праці; прийоми і послідовність ручного обробітку ґрунту; види механізованого обробітку ґрунту; правила безпечної праці та особист
10891. Благоустрій і озеленення приміщень і території 36 KB
  Тема: Благоустрій і озеленення приміщень і території. Мета уроку: Засвоєння знань про роль і місце зелених насаджень у житті людини умови використання у насадженнях різних порід породи декоративних і захисних рослин. Об’єкт навчальної праці: проектування зелених нас...
10892. Практична (проектна) робота. Процес випилювання з фанери та ДВП 33.5 KB
  Тема уроку: Практична проектна робота. Процес випилювання з фанери та ДВП. Мета уроку. Формування вмінь виконувати пиляння фанери лобзиком; закріплення знань про пиляння деревини. Розвивати точність окомір. Виховувати акуратність виконавчу дисципліну творче ставл
10893. Планирование ресурсного потенциала предприятия 118 KB
  Под потенциалом предприятия принято понимать совокупность показателей или факторов, характеризующих его силу, источники, возможности, средства, запасы, способности, ресурсы и многие другие производственные резервы
10894. Процес обробки матеріалів різанням 29 KB
  Тема: Процес обробки матеріалів різанням. Мета: 1 ознайомити учнів з основними способами різання деревини елементами і назвами інструментів. Забезпечити засвоєння правил ТБ; 2 виховувати в учнів уважність відповідальне ставлення до обладнання майстерні бережливі...
10895. Прийоми розмічання за шаблонами та інструментами 36.5 KB
  Тема: Прийоми розмічання за шаблонами та інструментами. Мета: 1 вдосконалювати в учнів знання про процес розмічання дати основні поняття про розмічальний інструмент навчити правильно використовувати цей інструмент; 2 виховувати естетичний смак культуру праці; ...
10896. Розмічання: за шаблоном, копіюванням. Підготовка заготовки до роботи 40.5 KB
  Тема уроку: Розмічання: за шаблоном копіюванням. Підготовка заготовки до роботи. Мета: навчальна: сформувати уявлення про призначення та будову вимірювальних інструментів. Прийоми розмічання за шаблоном. Відомості про припуски на обробку. Виховна: виховувати стара...