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

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

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

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

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

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

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

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


 

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

26250. Внесение удобрений 70.5 KB
  Домашнее задание Внесение удобрений Цель и задачи. Сформировать умение оперативно принимать решение по выбору оптимальных норм способов и сроков внесения удобрений в различных агротехнологиях в зависимости от изменяющихся агроэкологических и производственных условий. Рассматриваются нормы сроки и способы внесения удобрений в том числе микроудобрений в зависимости от агроэкологических и производственных условий. Сроки и способы внесения удобрений.
26251. Оценка устойчивости ландшафтов и агроландшафтов и их антропогенной преобразованности 71 KB
  13 Практическое задание Оценка устойчивости ландшафтов и агроландшафтов и их антропогенной преобразованности Цели и задачи. Сформировать представление об устойчивости природных ландшафтов и агроландшафтах видах экологической устойчивости определяющих ее факторах о цене экологической устойчивости агроландшафтов и принципах ее обеспечения. Затраты на ее поддержание определяют цену устойчивости агроландшафта. Дать характеристику экологической агрономической и экономической устойчивости определенного агроландшафта.
26252. Оценка экологической емкости агроландшафта 49 KB
  14 Домашнее задание Оценка экологической емкости агроландшафта Цели и задачи. Сформировать представление о способности агроландшафта воспринимать антропогенную нагрузку при сохранении экологической устойчивости и критериях ее оценки. Формируется понятие экологической емкости агроландшафта и определяющие ее условия. Дать оценку экологической емкости агроландшафта на примере конкретного земельного массива Оценка экологическая емкость агроландшафта Чтобы обеспечить экологическую устойчивость агроландшафта необходимо задать такие параметры...
26253. Значение и место альтернативных технологий в земледелии 47 KB
  Сформировать представление об агротехнологиях альтернативного земледелия как социальном явлении их формах причинах агрономических ограничений возможностях использования. Принципы и источники альтернативного земледелия его мотивации. Основателем данного направления считают австрийского философа Рудольфа Штайнера сформулировавшего в 1924 году принципы так называемого биодинамического земледелия как развитие созданного им мистического учения антропософии. В то же время продукция органического земледелия отнюдь не застрахована от природных...
26254. Агроэкологические требования сельскохозяйственных культур как исходный критерий агрооценки земель 38.5 KB
  Близкие по условиям возделывания конкретных сельскохозяйственных растений ЭАА объединяются в агроэкологические типы земель в пределах которых формируются производственные участки. Пока что не все аспекты агроэкологической оценки растений разработаны с достаточной полнотой особенно почвенные некоторые трудно поддаются формализации. Следует ускорить разработку региональных рекомендаций по данному вопросу с учетом местных условий культур сортов растений. Отношение растений к свету: размещение растений по реакции на продолжительность дня...
26255. Выбор, размещение и сельскохозяйственных культур и сортов и разработка агроэкологических карт в АгроГИС 64 KB
  Ключевые слова: виды сорта культур агроэкологическая оценка интенсивные пластичные устойчивые сорта агроэкологическая карта категории пригодности. Выбор культуры и сорта. Выбор культуры и сорта Выбор культур для региона конкретного хозяйства и поля осуществляют на основе оценки их биологических требований и средообразующего влияния. Показатели агроэкологической оценки культур указанные в паспорте сорта сравниваются с соответствующими параметрами агроландшафта.
26256. Управление продукционным процессом сельскохозяйственных культур и агроценозами 54 KB
  В процессе генерации технологических решений с помощью специально разработанного интерфейса СППР автоматически формируется задание на выполнение конкретной операции в режиме точного земледелия которое затем загружается в бортовой компьютер сельскохозяйственной техники. В зависимости от режима реализации операции различают два типа задания: Карта операции режим функционирования offline Карта агротребований на выполнение операции режим online Карта операции электронная карта поля где для каждого однородного участка поля указана...
26257. Защита растений от вредителей и болезней в агроценозах 327.5 KB
  Практическое занятие Защита растений от вредителей и болезней в агроценозах Цели и задачи. Развить способность практиковать интегрированный подход к защите растений и умение использовать современные методы и средства борьбы с вредителями и болезнями. Рассматриваются агротехнические химические и биологические методы защиты растений от болезней и вредителей при различных уровнях интенсификации агротехнологий и интегрированном подходе. Разработать систему мер по защите растений в заданном севообороте при заданной фитосанитарной ситуации.
26258. Создание картограмм агрофизического состояния почв и интерпретация результатов в геоинформационных системах (ГИС) 384 KB
  Практическое занятие Создание картограмм агрофизического состояния почв и интерпретация результатов в геоинформационных системах ГИС Цели и задачи. Приобретение навыков картографирования агрофизического состояния почв с использованием педотрансферных функций и ГИСтехнологий. Рассматривается методика разработки картограмм агрофизических свойств почв в геоинформационных системах на примере плотности почв и запасов продуктивной влаги. Освоить методику картографирования физических и воднофизических свойств почв на конкретном первичном...