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

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

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

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

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

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

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

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


 

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

8923. Метрологическое обеспечение измерений при контроле качества и испытаниях продукции 49.5 KB
  Метрологическое обеспечение измерений при контроле качества и испытаниях продукции Студент должен иметь представление: - о классификации испытательного оборудования и требованиях к его метрологическому обеспечению знать:...
8924. Очистка природного газа и переработки кислых газов с получением товарной продукции (серы) на Карачаганакском месторождении 1.08 MB
  Введение Сформировавшемуся в последнее время нефтегазовому комплексу Республики Казахстан отводится ведущая роль в топливно-энергетическом балансе и экономике страны. При нынешних темпах развития производительных сил и освоения углеводородных ресурс...
8925. Отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта 131.5 KB
  Цель работы: Целью работы является отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта. - коэффициент жесткости с упругого звена - посто...
8926. Лекции по теории автоматов Часть 1 Теория абстрактных автоматов 241 KB
  Лекции по теории автоматов Часть 1 Теория абстрактных автоматов Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления. ОГЛАВЛЕНИЕ Часть 1. Теория абстрактных автоматов...
8927. Енергозбереження - шлях до віддалення глобальної катастрофи 115.5 KB
  Тема 10. Енергозбереження - шлях до віддалення глобальної катастрофи Людська цивілізація знаходиться на порозі чергової кризи, звязаної з наслідками її діяльності, а саме - глобальним забрудненням довкілля, зокрема парниковими газами...
8928. Інвестиційна політика в галузі енергозбереження 122 KB
  Тема 9. Інвестиційна політика в галузі енергозбереження З таблиці 2 теми 1 бачимо, що обсяг капіталовкладень, які необхідні для забезпечення ефективної політики в галузі енергозбереження на Україні, становить у розрахунку на 2005 рік...
8929. Утилізація вторинних енергоресурсів 284.5 KB
  Утилізація вторинних енергоресурсів Будь-які енергоносії, чи енергія у формі тепла або стиснених газів, що отримуються внаслідок основних технологічних процесів, наприклад, коксування вугілля, металургійних процесів, роботи ГТУ чи ТЕС, називаються в...
8930. Лекции по теории автоматов. Логические основы цифровых автоматов 620.5 KB
  Лекции по теории автоматов. Логические основы цифровых автоматов. Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления..
8931. Нетрадиційні та поновлювані джерела енергії 644 KB
  Нетрадиційні та поновлювані джерела енергії Сучасна енергетика базується на викопному органічному паливі: камяному вугіллі, нафті та газі. Розвіданих і прогнозних запасів викопного палива при сучасних темпах енергоспоживання достатньо на 90-15...