Презентация на тему "Линейное программирование"

Содержание

• 
  Слайд 1

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

  Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств.

• 
  Слайд 2

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

  Для изготовления трех видов сплавов A, В и С используется медь, олово и цинк. Данные о сплавах приведены в табл. 1. Процентное содержание и общая масса компонентов Требуется определить, какое количество сплавов каждого вида следует изготовить предприятию, чтобы стоимость продукции была максимальной. Изготовленоx1кг сплава А, х2 кг сплава В и х3кг сплава С.Для производства такого количества сплавов потребуется затратить 20x1 + 10x2+ З0х3кг меди. 20x1 + 10х2 + З0х3120 000 10x1 + 80х2 + 60х3280 000 (8.2) 70x1 + 10х2 + 10х3240 000 x1 х20, х3 0. (8.1) F = 10x1 + 14х2+ 12х3 (8.3) Функция (8.3) линейная, а система (8.2) содержит линейные неравенства, задача (8.1)—(8.3) является задачей линейного программирования.  

• 
  Слайд 3

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

  Определение. Общей (основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (8.6) при выполнении условии (8.7) (8.8) (8.9) где аij, bi и cj— заданные постоянные величины и km. Определение. Функция (8.6) называется целевой функцией задачи (8.6)—(8.9), а условия (8.7)—(8.9) — ограничениями данной задачи.  

• 
  Слайд 4
  

  Определение. Канонической задачей линейного программирования называется задача, которая состоит в определений максимального значения функции (8.6) при выполнении условий (8.8) и (8.9), где k= 0 и l= n. Определение. Вектор X = (х1, х2,... хn)T, удовлетворяющий ограничениям задачи (8.7)—(8.9), называется допустимым решением, или планом. Определение. План X* = (х1*, х2*,... хn*)T, при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным. F = c1х1 +c2х2 + … + cnхn F1= -F =-c1х1 -c2х2- … - cnхn min F = max(-F)

• 
  Слайд 5
  

  Ограничение-неравенство Ограничение-равенство Ограничение-неравенство Ограничение-равенство Если переменная хkпо условию задачи отрицательна, то ее следует заменить двумя неотрицательными переменными uk и vk, приняв xk = uk- vk.

• 
  Слайд 6

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

  Записать в форме канонической задачи линейного программирования задачу нахождения максимума функции F = Зх1 - 2х2 - 5х4 + х5 при условиях Запись в форме канонической задачи =>переход от ограничений-неравенств к ограничениям-равенствам. Переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого неравенства вида «» соответствующая переменная прибавляется, а из левых частей каждого из неравенства вида «» вычитается. Каноническая задач а: максимизировать функцию F = Зх1 - 2х2+ 5х4 + х5 при условиях  

• 
  Слайд 7

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

  Определение. Непустое множество планов общей (основной) задачи линейного программирования называется многогранником решений. Свойство. Если основная задача линейного программирования имеет оптимальный план, то максимальное значение целевая функция принимает в одной из вершин многогранника решений. n– r 2, где n – число переменных, r – ранг матрицы. Определение максимального значения F = c1x1+c2x2 при условии (8.11) (8.12) Каждое из неравенств (8.11), (8.12) геометрически определяет полуплоскость соответственно с граничными прямыми аi1х1+ аi2х2 = bi, i = 1,... k,x1= 0,x2= 0.  

• 
  Слайд 8
  

  Исходная задача линейного программирования: нахождение вершины многоугольника решений, в которой целевая функция (8.10) принимает максимальное значение. Такая вершина существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. Для определения этой вершины строят линию уровня с1x1+с2х2 = h, и перемещают ее в направлении вектора = (с1, с2), ортогонального ей, до тех пор пока она не пройдет через последнюю общую точку с многоугольником решений. Координаты точки определяют оптимальный план задачи.  

• 
  Слайд 9

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

  Для изготовления двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода каждого вида сырья на изготовление единицы продукции данного вида приведены в табл. Требуется определить такой план выпуска, при котором прибыль предприятия от реализации совокупности изделий будет максимальной. Общая прибыль от реализации всей продукции составит F = 30x1+ 40x2. Найдем решение данное! задачи, используя ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных следует заменить знаки неравенств знаками точных равенств и найти соответствующие прямые.

• 
  Слайд 10
  

  Многоугольником решений является пятиугольник OABCD. Найти точку, принадлежащей пятиуголь- никуOABCD, в которой F = 30x1 + 40x2 принимает максимальное значение. Построим вектор = (30; 40) и прямую 30x1 + 40x2= h. Положим, например, h= 480 и построим прямую 30x1 + 40x2 = 480. Общей точкой прямой с многоугольником решений является точка В. Прибыль от его реализации является максимальной, и удовлетворяют уравнениям прямых Решив систему, получим х1= 12, х2 = 18. Следовательно, если предприятие изготовит 12 изделий вида Аи 18 вида В, то оно получит максимальную прибыль F= 3012 + 4018 = 1080.   Графическое решение

• 
  Слайд 11

  Аналитическое решение задач линейного программирования

  Каноническая задача линейного программирования: найти максимальное значение функции при условиях Перепишем условия в форме (8.13) (8.14) где Р0, ...Рn-m-мерные векторы-столбцы, составленные из коэффициентов aijпри неизвестных xj0, j= 1,... nи свободных членах bi (i= 1,...m) системы уравнений задачи:  

• 
  Слайд 12
  

  Определение. Если система векторов {Pj}входящих в левую часть уравнения (8.13), (8.14) с положительными коэффициентами {xj>0} линейно независима, то планX = (x1 ,х2, … хn)Tназываетсяопорным планом канонической задачи линейного программирования. Определение. Опорный планX = (x1 ,х2, … хn)Tназываетсяневырожденным, если он содержит ровноmненулевых компонент{xj> 0}, а если их меньше т, товырожденным. Необходимо обратить внимание на следующее. - Если задача линейного программирования разрешима, то максимум целевой функции достигается хотя бы при одном опорном плане. - Опорный план является угловой точкой множества планов, целевая функция принимает максимальное значение именно на множестве опорных планов задачи (в одной из вершин многогранника решений).

• 
  Слайд 13

  Симплекс-метод

  Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Нахождение решения симплекс-методом гарантируется только в том случае, когда на каждом шаге рассматриваемый опорный план является невырожденным.

• 
  Слайд 14

  Постановка задачи и определение исходного опорного плана.

  Пусть требуется найти максимальное значение функции при условиях гдеaij,biи сj— заданные постоянные числа, причем всеbi> 0. В векторной форме задача формируется следующим образом: найти максимум функции (8.15) при условиях (8.16) (8.17) где Исходным опорным планом является совокупность Х = (b1,b2,...bm,0,...0)T, которая удовлетворяет b1P1+ b2Р2 +... +bmРm+ 0Рm+1+... +0Рn= Р0.  

• 
  Слайд 15

  Проверка оптимального опорного плана.

  где - значение целевой функции при выбранном опорном плане Величина показывает, на сколько изменитсяF0при увеличении компоненты xj(j = m + 1, … n).Следует говорить только об увеличениихj, так как одним из условий задачи являетсяхj 0(j = 1,...n),а при данном опорном плане всехj =0(j = m + 1,... n). Если j0 для любогоj(j= m+ 1,... n), то очевидно, что увеличение компонентыхj (j = m + 1,... n) приведет куменьшению значения функции Если j0 для любогоj(j= 1,... n), то данный опорный план задачи (8.15)—(8.17) является оптимальным, амаксимальное значение функции найдено и равно  

• 
  Слайд 16

  Переход к новому опорному плану

  Если среди j(j = m + 1,... n) найдутся p 0, то необходимо, чтобы выполнялось условие (bi - aikxk) 0для всех aik>0 . Это условие будет выполняться при  

• 
  Слайд 17
  

  В результате получим, что (bl- alk xl) = 0 икомпоненту xlследует исключить из опорного плана, а вместо включить компоненту хk. Базисный вектор Plисключается,вместо него в базис включается вектор Pk. Значение функции при этом увеличится Возможна ситуация, когдадостигается принесколькихi.В таком случае получим, что несколько компонент нового опорного плана будут равны нулю, и невырожденный опорный план превратится в вырожденный.

• 
  Слайд 18

  Описание симплекс-таблицы

  Общий вид симплекс-таблицы В столбцеСбзаписывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса. В столбцеР0 записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают компоненты оптимального плана. Столбцы векторов Pjпредставляют собой коэффициенты разложения этих векторов по векторам данного базиса. j= zj - сj. Величина zj- скалярное произведение вектора Рj на вектор Р0.

• 
  Слайд 19

  Аналитическое решение задач линейного программирования (Пример)

  Для изготовления различных изделий A, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия, а также общее количество сырья каждого вида приведены в табл. 2. Составить план производства изделий, при котором общая стоимостьпроизведенной продукции будет максимальной. Система неравенств (8.22) Общая стоимость произведенной предприятием продукции составляет (8.23) (8.24)

• 
  Слайд 20
  

  Каноническая форма. Переход от ограничений-неравенств к ограничениям-равенствам. Вводим три дополнительные переменные. Преобразованную систему уравнений запишем в векторной форме где Поскольку среди векторов P1, ...P6имеются три единичных вектора, то можно непосредственно записать опорный план X = (0,0,0,360,192,180)T,определяемый системой трехмерных единичных векторов Р4, Р5, Р6 , которые образуют базис векторного пространства.

• 
  Слайд 21
  

  Составим симплекс-таблицу для итерации 1 и проверим исходный план на оптимальность: Для векторов базиса Таблица 1.1 Опорный план Xне является оптимальным: имеются отрицательные числа. Для определения вектора, подлежащего исключению, находим min(bi /ai3) при ai3 >0, т.е. min (360/12; 192/8; 180/3) = 192/8 = 24. Таким образом, из базиса следует исключить вектор Р5. Ограничивающим фактором для производства изделий С является имеющийся объем сырья II вида. С учетом этого предприятие может выпустить 24 изделия С.

• 
  Слайд 22
  

  Столбец Р3 и строка Р5 являются в симплекс-таблице направляющими. Составим таблицу для итерации 2 Таблица 1.2 Для определения элементов применяем правило треугольника. Элементы можно вычислены непосредственно по формулам (8.18)—(8.21). Вычислим число, являющееся первым элементом вектора Р0 . Для его вычисления находим три числа, расположенные: 1) в табл. 1.1 на пересечении столбца вектора Р0 и первой строки (360); 2) в табл. 1.1 на пересечении столбца вектора Р3 и первой строки (12); 3) в табл. 1.1 на пересечении столбца вектора Р0 и второй строки (24). 360 -12 • 24 = 72. Аналогично находим элементы столбцов Р1, Р2, Р5. Новый опорный план X = (0,24,0,72,0,108)Tи значения ’jи F’0

• 
  Слайд 23
  

  Найдем вектор, подлежащий исключению из базиса. min(72/9, 48/1, 360/3) = 72/9 = 8. Следовательно, исключению из базиса подлежит вектор Р4. Число 9 является разрешающим элементом, а столбец Р2 и строка Р4 являются направляющими. Составим таблицу итерации 3. Новый опорный план X = (0,8,20,0,0,96)Tи коэффициенты разложения векторов Pi(i = 1,... 6) через базисные векторы Р2, Р3, Р6, а также значения ’’jи F’’0 . Найденный план является оптимальным и Fmax = 400. С экономической точки зрения план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. Оптимальным планом не предусматривается изготовление изделий А.