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

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

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

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

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

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

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

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


 

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

30702. Приём антитезы в произведениях русской литературы 2-й половины XIX века. Ф.М. Достоевский «Преступление и наказание» 132.77 KB
  I антитеза ос6новное идейно композиционный принцип романа Преступление и наказание II функции антитезы. Приём антитезы при создании образа главного героя: А замечательная внешность Раскольникова и одежда нищего; Б описание каморки и страшная теория Раскольникова; В бесчеловечность теории и её неприятие сердцем сны Раскольникова. Приём антитезы в основе системы персонажей: А двойники Раскольникова Лужин и Свидригайлов; Б правда Сони Мармеладовой и правда Раскольникова.
30703. И. А. Бунин. Тема любви 15.98 KB
  Тема любви. В теме любви Бунин раскрывается как человек удивительного таланта тонкий психолог умеющий передать состояние души раненной любовью. На протяжении столетий многие художники слова посвящали свои произведения великому чувству любви и каждый из них находил чтото неповторимое индивидуальное этой теме. Эта тайна бытия становится темой бунинского рассказа Грамматика любви1915.
30704. Образ нигилиста Базарова и тема смены поколений в романе И.С. Тургенева «Отцы и дети». Тургеневский принцип «тайной психологии» в изображении человеческих характеров 13.82 KB
  Сюжет строится на столкновение двух враждебных идеологий – разночиннодемократической к которой относится Евгений Базаров и либеральнодворянской.Взгляды Базарова главного героя романа сводятся к резкой критике того положения которое сложилось в стране. Но Базаров не видит силы и в народе.
30705. Философское звучание стихотворения А.С. Пушкина «Вновь я посетил…» 12.03 KB
  Так в стихотворении начинает звучать мотив жизни и смерти. Мотив семьи таким образом перерастает в тему смены поколения вечного непрестанного обновления жизни. Так к финалу стихотворения мотив смерти преобразуется в мотив памяти а воспоминание о своем личном приобретает характер всеобщий философский.
30706. Новая социалистическая «волна» в Западной Европе: приход к власти лейбористов в Великобритании, социалистов во Франции, социал-демократов в Германии (опыт 1990-х гг.) 27.5 KB
  Германия В Западной Германии СоцДемокрПартГерм выиграла выборы в ФРГ в 1969 и находилась у власти до 1982 правительства в эти годы возглавлял Вилли Брандт а затем с 1974 Гельмут Шмидт. Вначале СДПГ выступала против перевооружения Западной Германии и вступления её в НАТО но впоследствии её позиция резко изменилась. В советском секторе оккупации где впоследствии была провозглашена ГДР СДПГ и Коммунистическая партия Германии объединились в Социалистическую единую партию Германии.
30707. Буржуазно-демократические революции в Германии, Австрии, Венгрии (1918): общее и особенное 23.5 KB
  Вслед за Германией буржуазнодемократические революции начались в Австрии и Венгрии что привело к свержению монархии и провозгласило республику во главе с коалиционным правительством и с буржуазнодемократическими правами и свободами. В Венгрии была объявлена республика а потом ее провозгласили Советской республикой по примеру России но она не сумела удержать власть и распалась в 1919 г. в Венгрии была установлена авторитарная диктатура и она была провозглашена монархическим государством.
30708. Политика правящих кругов и усиление левой оппозиции во Франции (1919 – 1923 гг.) 22.5 KB
  В отношении рабочего класса применялась политика уступок которые чередовались репрессиями. Политика правящих кругов также отразилась и на политическом уровне – впервые были проведены выборы в парламент и объединение в Национальный блок целью которого стала борьба с большевизмом.
30709. Проблемы антифашистской борьбы в Европе 1920 – 1930 гг 23.5 KB
  В 1935 во Франции был создан Народный фронт в состав которого вошли как коммунистические и социалистические партии так и левобуржуазные политические организации. Народный фронт представляет собой политический союз который как правило объединяет левые и центральные силы для осуществления противодействия правым силам представителей власти. Основной целью возникновения народных фронтов стала борьба за защиту экономических интересов рабочего класса и противопоставление войне и фашизму. Самый первый народный фронт был образован во...
30710. Основные тенденции и итоги развития Европейского Сообщества в 1990-е 23.5 KB
  ЕЕА провозгласил создание Европейского Союза на основе существующих Сообществ и углубление компетенции союза ЕС в области координации экономической валютной социальной политики социальноэкономического сплочения исследований и технологического развития защиты окружающей среды а также развитие европейского сотрудничества в области внешней политики. Амстердамский договор 1997 подтвердил основные цели Союза и дополнил раздел общей внешней политики и политики безопасности. При анализе политики Европейского Союза...