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

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

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

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

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

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

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

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


 

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

2820. Методика составления рейтинга надежности банков 28.76 KB
  Методика составления рейтинга надежности банков C разрешения автора Профиль (№20(92) от 01.06.1998) приводит более подробное изложение методики к.э.н. В.С.Кромонова. Параметры баланса В качестве исходных данных для составления рейтинга испол...
2821. Современные требования к жилью 90.5 KB
  Современные требования к жилью Качество жилых зданий, сооружений, систем инженерного оборудования и городских территорий Жилище — квартиру, дом, окружающую его территорию — рассматривают как части системы человек — среда обитания. И...
2822. Топливо–измерительные комплексы. Расходомеры 619.54 KB
  Назначение топливо- измерительных комплексов На большинстве самолетов устанавливаются две системы. Одна включает устройства для измерения количества топлива в баках, управления порядком заправки его на земле и выработки в полете, другая...
2823. Инженерное оборудование городских территорий 32 KB
  Инженерное оборудование городских территорий Классификация систем инженерного обеспечения города Инженерные коммуникации бывают подземными, наземными и надземными. К подземным инженерным сетям относятся трубопроводы, кабели и коллекторы. Используютс...
2824. Производственный менеджмент 1.69 MB
  Экономика производства Экономика производства – отрасль знаний, изучающая теорию и практический опыт хозяйствования производственных предприятий. Она включает рассмотрение широкого спектра факторов, участвующих в сфере производства и реали...
2825. Особенности сложившейся застройки разных периодов строительства 27.5 KB
  Особенности сложившейся застройки разных периодов строительства. Характеристика застройки разных периодов с позиций необходимости и возможности ее реконструкции. Результаты и социально-экономический эффект реконструкции сложившейся застройки. Особен...
2826. Канал измерения запаса топлива 1.83 MB
  Виды топливомеров. Приборы, измеряющие объемное или весовое количество топлива в баках, называются топливомерами. Они позволяют экипажу самолета в любой момент полета определить, сколько топлива имеется в баках, и оценить время, в течение которого...
2827. ОБЩАЯ ФИЗИОЛОГИЯ ВЫСШЕЙ НЕРВНОЙ ДЕЯТЕЛЬНОСТИ (ВНД) 200 KB
  Определение высшей и низшей нервной деятельности. Виды ННД и ВНД. Учение И.П. Павлова о ВНД. Врожденные и приобретенные формы поведения. Принципы работы коры. Безусловные и условные рефлексы (классификация, характеристика, сравнительная характеристика БР и УР). Правила формирования УР. Торможение в коре. Физиология памяти.
2828. Факторы, оценивающие качество застройки 26 KB
  Факторы, оценивающие качество застройки. Комплексное понятие качества. Критерии рациональности и комфортности. Показатели экономической целесообразности, капитальности, безопасности, функциональности и гигиены. Учет и повышение качества застройки пр...