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

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

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

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

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

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

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

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


 

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

12562. ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДА-ДЖОНСА 422 KB
  ОТЧЕТ по лабораторной работе №6 ОПРЕДЕЛЕНИЕ ПАРАМЕТРОВ ПОТЕНЦИАЛОВ ЛЕННАРДАДЖОНСА ВВЕДЕНИЕ В настоящей работе на основании исследования макроскопических свойств газа рассчитываются параметры потенциала ЛеннардаДжонса применяемого в классических и кванто
12563. СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ 1.2 MB
  СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ Отчет по лабораторной работе № 6М ВВЕДЕНИЕ Определение силы с которой жидкость действует на обтекаемое тело является одной из основных задач механики сплошных сред. В данной работе эта сила определяется экспериментально на моделях в д
12564. Адиабата. Измерение показателя адиабаты акустическим методом 611 KB
  Колебательное движение с малыми амплитудами в сжимаемой жидкости называют акустическими волнами. Процесс распространения акустических волн в идеально сжимаемой жидкости списывается поведением во времени и пространстве основных акустических параметров
12565. ЯВЛЕНИЕ МАГНИТОСТРИКЦИИ 733.5 KB
  ОТЧЕТ по лабораторной работе №4 ЯВЛЕНИЕ МАГНИТОСТРИКЦИИ ВВЕДЕНИЕ Явление магнитострикции заключается в изменении формы и размеров ферромагнетика при изменении его намагниченности в магнитном поле. Магнитострикция позволяет выяснить природу сил которые опред...
12566. ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА СОПРОТИВЛЕНИЯ ПРИ ТЕЧЕНИИ ВОЗДУХА В ЦИЛИНДРИЧЕСКОЙ ТРУБКЕ 298.5 KB
  ОТЧЕТ по лабораторной работе №4М ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА СОПРОТИВЛЕНИЯ ПРИ ТЕЧЕНИИ ВОЗДУХА В ЦИЛИНДРИЧЕСКОЙ ТРУБКЕ ВВЕДЕНИЕ Цель данной лабораторной работы заключается в ознакомлении студентов с основными закономерностями и параметрами характеризующими теч
12567. ТЕПЛОЕМКОСТЬ КРИСТАЛЛИЧЕСКИХ ТЕЛ 653 KB
  ОТЧЕТ по лабораторной работе №3 ТЕПЛОЕМКОСТЬ КРИСТАЛЛИЧЕСКИХ ТЕЛ ВВЕДЕНИЕ Цель работы ознакомление с микроскопической теорией теплоемкости кристаллических тел ознакомление с установкой для измерения теплоемкости и измерение теплоемкости двух образцов. ...
12568. БАРОЭФФЕКТ ПРИ ВЗАИМНОЙ ДИФФУЗИИ ГАЗОВ 137.5 KB
  ОТЧЕТ по лабораторной работе №2М БАРОЭФФЕКТ ПРИ ВЗАИМНОЙ ДИФФУЗИИ ГАЗОВ ВВЕДЕНИЕ Целью данной лабораторной работы является ознакомление с явлением бароэффекта при взаимной диффузии газов а также приобретение знаний и навыков в работе с ...
12569. ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ ГАЗОВ МЕТОДОМ НЕСТАЦИОНАРНОГО ПОТОКА 456 KB
  ОТЧЕТ по лабораторной работе №1М ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ ГАЗОВ МЕТОДОМ НЕСТАЦИОНАРНОГО ПОТОКА ВВЕДЕНИЕ Целью данной лабораторной работы является ознакомление с существующими методами измерения коэффициентов динамической вязкости газов на примере ...
12570. СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ. ЛАБОРАТОРНАЯ РАБОТА 243 KB
  ОТЧЕТ по лабораторной работе №6м СОПРОТИВЛЕНИЕ ОБТЕКАЕМЫХ ТЕЛ Введение Целью данной лабораторной работы является ознакомление с существующими методами измерения расхода скорости газа и силы с которой газ действует на oбтекаемое тело в дозвуковой аэродина...