Презентация на тему "Основная задача линейного программирования"

Содержание

• 
  Слайд 1

  Линейное программирование

  Основная задача линейного программирования

• 
  Слайд 2

  Стандартная форма

  Первая стандартная форма задачи линейного программирования имеет вид

• 
  Слайд 3
  

  Вторая стандартная форма задачи линейного программирования имеет вид

• 
  Слайд 4

  Каноническая форма

  Канонической формой задачи линейного программирования называется задача вида

• 
  Слайд 5

  Правила приведения

  Рассмотрим теперь те приёмы, которые позволяют произвольные формы задач линейного программирования приводить к указанным выше стандартным формам. 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде то, умножая её на (- 1), приведем её к виду так как смена знака приводит к смене min на max. Аналогично можно заменить max на min.                                      ,

• 
  Слайд 6
  

  2. Смена знака неравенства. Если ограничение задано в виде то, умножая на (-1), получим: Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно .

• 
  Слайд 7
  

  3. Превращение равенства в систему неравенств. Если ограничение задано в виде то его можно заменить эквивалентной системой двух неравенств или такой же системой неравенств со знаками больше либо равно. Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме.

• 
  Слайд 8
  

  4. Превращение неравенств в равенства. Для приведения задачи к канонической форме, где все ограничения имеют вид равенств, вводят дополнительные переменные , которые тоже считаются неотрицательными и записывают исходную задачу в виде

• 
  Слайд 9
  

  То есть в неравенстве со знаком меньше либо равно добавляют дополнительную неотрицательную переменную, а из неравенства со знаком больше либо равно вычитают дополнительную переменную. В целевую функцию эти дополнительные переменные включают с коэффициентом 0, т.е. фактически они в целевой функции отсутствуют. Получив решение задачи в канонической форме, для получения решения исходной задачи надо просто выбросить из решения значения введенных дополнительных переменных.

• 
  Слайд 10

  Задание

  Привести к каноническому виду задачу Привести к каноническому и стандартному виду задачу

• 
  Слайд 11
  

  Привести к канонической и стандартной форме

• 
  Слайд 12
  

  Привести к канонической форме

• 
  Слайд 13
  

  Привести к канонической форме

• 
  Слайд 14
  

  Привести к канонической и стандартной форме

• 
  Слайд 15
  

  Привести к канонической и стандартной форме