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

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

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

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

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

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

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

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


 

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

41419. СПЕЦИФИКА СОЦИАЛЬНОЙ РЕАЛЬНОСТИ 122 KB
  Существование человека вне общества невозможно. Но что такое общество, как оно возникает, каково его строение, в соответствии с какими принципами оно существует и функционирует Эти вопросы составляют предметное поле того раздела философских знаний, который называется социальной философией
41420. Порядок ведения и отражения в учете кассовых операций 20.81 KB
  Первичными документами по кассе являются документы, разработанные ЦБ России. Прием наличных денежных средств кассами организаций производится по приходным кассовым ордерам, подписанным главным бухгалтером или лицом, уполномоченным на это письменным распоряжением руководителя организации.
41421. Учет операций на расчетных счетах в банках 20.45 KB
  Він розширив її територію на підкорених древлян сіверян радимичів. міська верхівка почала боротись за розширення прав міста і відтоді усі князі перед посіданням князівського престолу укладали “ряд†договір з Вічем. Розширена – укладена за князювання Володимира Мономаха чи його сина Мстислава. Розширена Правда встановлювала норми щодо захисту земельної власності феодалів та обмеження майнових і особистих прав феодально залежного населення.
41422. Учёт выбытия материальных запасов 21.67 KB
  Для учета реализации и прочего выбытия товарно-материальных ценностей предназначен операционно-результатный счет 91 «Прочие доходы и расходы». Выбытие материалов в качестве вклада в уставный (складочный) капитал других организаций учитывается как долгосрочные инвестиции
41423. ВОССТАНОВЛЕНИЕ НАРУШЕННЫХ ПРАВ УЧАСТНИКОВ УГОЛОВНОГО СУДОПРОИЗВОДСТВА 350 KB
  Цель работы состоит в изучении и анализе теоретических положений, норм института восстановления нарушенных прав участников уголовного судопроизводства, в том числе признанных незаконно или необоснованно подвергнутыми уголовному преследованию или осуждению, а также правоприменительной практики
41424. Учет кассовых операций. Учет удержаний из заработной платы работников 22.8 KB
  Приходный кассовый ордер (ПКО). Используется при поступлении наличных денег в кассу. Составляется кассиром, должны быть пронумерованы по порядку от начала отчетного года.
41425. Учёт поступления основных средств. Учет операций на расчетном счете в банке 28.6 KB
  Основные средства поступают в организацию и принимаются к бухгалтерскому учету в случаях их приобретения, сооружения (изготовления), внесения учредителями в счет их вкладов в уставный капитал
41426. НЕМЕТАЛИ ІV ГРУПИ. ВУГЛЕЦЬ. КИСНЕВІ СПОЛУКИ ВУГЛЕЦЮ 829 KB
  Атоми eлeмeнтiв пiдфyпи Kpбoнy мicтять y зoвнiшньoмy eлeктpoннoмy шpi ns2np2eлeктpoнiв: пepeдocтннiй шp y тoмiв C i Si iнepтнoгзoвий звepшeний y Ge Sn i Pb 18eлeктpoнний. Hявнicть чoтиpьox eлeктpoнiв y зoвнiшньoмy eлeктpoннoмy шpi томiв eлeмeнтiв пiдгpyпи Kpбoнy є oзнкoю тогo щo вoни мoжyть бyти чoтиpивлeнтними. Oтжe eлeмeнти пiдгpyпи Kpбoнy мoжyть yтвopювти cпoлyки як з ктивними нeмeтлми тк i з мeтлми виявляючи y цьoмy pзi cтyпeнi oкиcнeння вiд 4 дo 4. У pзi пepexoдy вiд Kpбoнy дo Плюмбyмy pдiycи тoмiв зpocтють здтнicть дo...
41427. КРЕМНІЙ ТА ЙОГО СПОЛУКИ 524 KB
  Гідpoгeнo і глoгeнoвмicнi cпoлуки cилiцiю.Oкcигeнoвмicнi cпoлуки cилiцiю. Bмicт Cилiцiю y зeмнiй кopi cтнoвить 276 вiн icнyє y виглядi тpьox cтбiльниx нyклiдiв: 28Si 9227 29Si 468 т 30Si 305 . Hйбiльш пoшиpeнi oкcид cилiцiюIV SiО2 т piзнi cилiкти.