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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

 

Математическая модель задач поиска наилучшего (экстремального) решения:

Целевая функция

при ограничениях

В зависимости от вида функций и задачи поиска наилучшего (экстремального) решения относятся к различным классам.

 

Если целевая функция и функции ограничений являются линейными, то такие задачи относятся к классу задач линейного программирования – ЗЛП.

Если или целевая функция и/или функции ограничений являются нелинейными, то такие задачи относятся к классу задач нелинейного программирования – ЗНП.

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

Задача об использовании сырья.

Для изготовления продукции двух видов П1, П2 требуется сырье видов .

Запасы сырья ограничены и составляют усл. ед. Известно aij – количество сырья вида i для изготовления продукции П j, i =1,4, j =1,2. Доход предприятия от реализации единицы продукции П j составит cj ден. ед.

Требуется:

Составить такой план производства продукции двух видов, при котором доход от реализации всей продукции будет максимальным.

Виды сырья Виды продукции Запасы сырья
П1 П2
s1 a11 a12 b1
s2 a21 a22 b2
s3 a31 a32 b3
s4 a41 a42 b4
доход c1 c2  

 

Математическая модель задачи

1. Пусть x 1 единиц – объем выпуска продукции П1,

x 2 единиц – объем выпуска продукции П2.

2. Цель задачи – максимизировать доход (c 1 x 1+ c 2 x 2)

3. Потребность в сырье s1: (a 11 x 1+ a 12 x 2).

Запасы сырья ограничены, поэтому (a 11 x 1+ a 12 x 2) ≤ b 1 . Аналогичные неравенства можно построить для всех видов сырья.

Итак,

F =(c 1 x 1+ c 2 x 2)→max

(a 11 x 1+ a 12 x 2) ≤ b 1

(a 21 x 1+ a 22 x 2) ≤ b 2

(a 31 x 1+ a 32 x 2) ≤ b 3

(a 41 x 1+ a 42 x 2) ≤ b 4

x 1≥0, x 2≥0.

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

 

 

Задача об использовании мощностей оборудования.

Предприятие имеет план производства по времени и номенклатуре: за время Т выпустить N1 ед. продукции вида П1 и N2 ед. продукции вида П2.

Продукция каждого вида может производиться на оборудовании А1 и А2, каждое из которых определенной производительности: aij – количество единиц продукции j -го вида, производящейся на i -м оборудовании.

Затраты, связанные с производством продукции вида j на оборудовании вида i составляют cij в ед. времени.

Требуется: составить оптимальный план работы оборудования, то есть определить сколько времени должно быть занято оборудование А1 и А2 при производстве П1 и П2 с тем, чтобы затраты на производство всей продукции были бы минимальные при условии выполнения плана по времени и номенклатуре.

Математическая модель задачи:

 

  1. Пусть xij – время работы i -го оборудования при производстве j -го продукта, i =1, m, j =1, n
  2. Цель задачи – минимизировать затраты, связанные с производством продукции:

 
 

  1. Выполнение плана по времени для оборудования А1:

 
 

Выполнение плана по номенклатуре для продукта П1:

 
 

Итак,

 
 

 


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

 

Матричная форма основной ЗЛП

Заданы:

 
 

Целевая функция:

Система линейных ограничений:

Определение 1.

Система (2) называется системой линейных ограничений ЗЛП. В системе (2) могут быть ограничения как в виде равенств =, так и в виде неравенств и . Система (2) не задает условий неотрицательности переменных: x1 ≥0, …

Определение 2.

Всякое неотрицательное решение системы (2) называется допустимым решением или планом ЗЛП.

Определение 3.

Допустимое решение системы (2), минимизирующее линейную форму F, называется оптимальным решением или оптимальным планом. Оптимальное решение может быть единственным, или решений может быть бесконечное множество.

 

Условия существования оптимального решения ЗЛП.

ЗЛП имеет смысл, когда система (2) совместна. Система совместна, если ранги основной и расширенной матриц системы совпадают.

Пусть r – ранг, n – число неизвестных.

1. r = n. В этом случае решение единственное, его можно определить поправилу Крамера.

2. r<n. В этом случае, если существует допустимое решение, значит существует и оптимальное (если значение хотя бы одной компоненты вектора решений отрицательно, решение ЗЛП не существует!)

 

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

  1. Алгебраический метод решения ЗЛП.

ЗЛП должна быть представлена в основной форме (1) и (2):

- Линейная форма

- ограничения системы в виде равенств.

а) .

Введем . Тогда . При этом вектор решений ЗЛП не изменится.

 

б) Пусть в системе линейных ограничений имеется неравенство:

Введем переменную , связанную с вектором переменных ЗЛП уравнением

 
 

Полученное ограничение-равенство эквивалентно ограничению-неравенству, если . Т.о. допустимым решением системы (2) будет вектор .

Пример.

 
 

n =5; r =3; k =5-3=2.

x 1 и x 2 – свободные переменные;

x 3, x 4 и x 5 – базисные переменные.

Пусть x 1=0 и x 2=0, тогда решением системы будет вектор X =(0,0,12,8, -6).

Необходимо увеличить x 5.

Это означает, что x 5 необходимо перевести в свободные переменные, а какую-то свободную - x 1 или x 2 в базисные:

при , при .

x 5 и x 2 – свободные переменные. Выразим

 
 

Проанализируем результат

Имеем целевую функцию

При ,

При .

Необходимо увеличить x 5.

Это означает, что x 5 необходимо перевести в базисные переменные, а какую-то из базисных в свободные.

 
 

x 3 и x 2 – свободные переменные.

 
 

Увеличиваем x 2

 

 
 

x 3 и x 4 – свободные переменные.

 
 

Получили оптимальное решение

 

Алгебра симплекс-метода (4 часа).

Имеется ЗЛП, представленная в форме с ограничениями-равенствами:

 
 

Пусть ранг системы , где k – свободные переменные,
r – базисные.

 
 

Пронумеруем переменные так, чтобы первые k из них были бы свободными, и выразим через них остальные – базисные. Получим:

Получили базисное решение, отвечающее выбору свободных неизвестных:

 
 

Предположим, что решение – допустимое, то есть , при этом .

Перейдем от одного допустимого базисного решения к другому допустимому базисному, так чтобы получить уменьшение целевой функции F. Для этого:

Представим задачу (3), (4) в виде

 

 

 
 

Введем обозначения: .

В новых обозначениях

 
 

Алгоритм решения

  1. Для заданного набора коэффициентов в линейной форме (5) и в системе линейных ограничений (6) строится симплекс-таблица.
  β x1 xs xj xk
F γ0   γ1   γs     γj     γk  
                             
xk+1 β1   α11   α1s     α1j     α1k  
                             
 
xk+l βl   αl1     αls   αlj     αlk  
                             
 
xk+i βi   αi1     αis     αij     αik  
                               
 
xn βr   αn1     αns     αnj     αnk  
                               
                                     

 

  1. Выбрать генеральный элемент согласно правилам:

Найти столбцы с положительными коэффициентами . При этом не учитывается. Пусть это будет . Если все , то базисное решение будет оптимальным.

- Составить отношения ;

- Выбрать наименьшее среди этих отношений ;

- Вычислить - генеральный элемент и .

3. Величину λ заносим в правый нижний угол i -й строки и j -го столбца.

4. В нижние углы i -й строки записываем произведения .

5. В нижние углы j -го столбца записываем произведения .

  β x1 xs xj xk
F γ0   γ1   γs     γj     γk  
                    -λγj        
xk+1 β1   α11   α1s     α1j     α1k  
                    -λα1j        
 
xk+l βl   αl1     αls   αlj     αlk  
  βl                 -λαlj        
 
xk+i βi   αi1     αis     αij     αik  
  λβi   λαi1       λαis       λ       λαik
 
xn βr   αn1     αns     αnj     αnk  
                      -λαnj        
                                     

 

6. Выделяем в i -той строке верхний угол, в j -м столбце – нижний.

 

  β x1 xs xj xk
F γ0   γ1   γs     γj     γk  
                    -λγj        
xk+1 β1   α11   α1s     α1j     α1k  
                    -λα1j        
 
xk+l βl   αl1     αls   αlj     αlk  
  βl                 -λαlj        
 
xk+i βi   αi1     αis     αij     αik  
  λβi   λαi1       λαis       λ       λαik
 
xn βr   αn1     αns     αnj     αnk  
                      -λαnj        
                                     

 

7. Заполняем остальные клетки симплекс-таблицы. В нижний угол заносится произведение:

верхний угол i -той строки × нижний угол j-го столбца

 

  β x1 xs xj xk
F γ0   γ1   γs     γj     γk  
-λγj γ0 -λγj γ0   -λγj γ0     -λγj γ0     -λγj γ0
xk+1 β1   α11   α1s     α1j     α1k  
-λα1j             -λα1j      
 
xk+l βl   αl1     αls   αlj     αlk  
  βl                 -λαlj        
 
xk+i βi   αi1     αis     αij     αik  
  λβi   λαi1       λαis       λ       λαik
 
xn βr   αn1     αns     αnj     αnk  
                      -λαnj        
                                     

 

8. Строится следующая таблица. Свободная переменная меняется местами в таблице с базисной переменной .

9. Заполняются i-я строка и j-й столбец: Элементы из нижних углов выделенных строки и столбца переносятся в верхние углы соответствующей клетки.

 

 

  β x1 xs xk+i xk
F               -λγj      
                             
xk+1                 -λα1j      
                             
 
xk+l               -λαlj      
                             
 
xj λβi λαi1   λαis   λ     λαik
                               
 
xn                 -λαnj      
                               
                                     

 

10. Заполняются верхние углы остальных клеток таблицы: Верхние углы клеток новой таблицы равны алгебраической сумме верхнего и нижнего угла соответствующих клеток предыдущей таблицы.

 

 

  β x1 xs xk+i xk
F           -λγj      
                             
xk+1                 -λα1j      
                             
 
xk+l               -λαlj      
                             
 
xj λβi λαi1   λαis   λ     λαik
                               
 
xn               -λαnj    
                               
                                     

 

Таким образом получено новое базисное решение. Решение является оптимальным, если все . Если хотя бы один коэффициент при неизвестных в целевой функции F положительный, преобразование симплекс-таблицы продолжается, начиная с п. 2.

Все переменные в строке таблицы являются свободными и равны 0.

Базисные переменные – в столбце равны:

 
 

Значение целевой функции:

 

Определение.

Основная ЗЛП является невырожденной, если в любом ее допустимом базисном решении, значения всех ее базисных переменных строго положительны.

Введем предположения:

  1. ЗЛП – невырожденная.
  2. ЗЛП имеет, по крайней мере, одно допустимое базисное решение.
  3. Целевая функция F ограничена снизу на множестве допустимых решений.

(Существует такое с, что при любом допустимом решении, .)

При введенных предположениях справедлива следующая теорема:

Теорема.

При выполнении предположений (1)-(3) основная ЗЛП имеет, по крайней мере, одно оптимальное базисное решение. Это решение может быть достигнуто симплекс-процессом, исходя из любого допустимого базисного решения за конечное число шагов.

Замечания по реализации симплекс-процесса.

Рассмотрим 2 случая.

  1. Процесс перехода от одной симплекс-таблицы к другой невозможен:

а) в строке F нет положительных коэффициентов. В этом случае получено минимальное значение линейной формы F.

б) в F есть , но в выбранном столбце для поиска генерального элемента нет положительных коэффициентов . Это означает, что F не ограничена снизу. То есть, при все базисные переменные останутся положительными.

 
 

Пример.

 

  1. Минимум линейной формы F не достигнут, и переход от одной к другой симплекс-таблице возможен. Но в процессе переходов симплекс- таблицы повторяются, то есть происходит «зацикливание».

Рекомендация:

Сменить столбец или строку, то есть выбрать другой генеральный элемент.

Двойственность в ЗЛП

Понятие двойственности имеет значение

- Теоретического характера. Позволяет анализировать изменение оптимального решения ЗЛП в зависимости от варьирования параметров задачи (Анализ устойчивости решения);

- Практического характера. Позволяет осуществлять совершенствование методов планирования и управления.

Пример 1. Задача об использовании сырья

 
 

Оценим стоимость сырья в зависимости от доходов, которое оно приносит предприятию.

Каждый i -й ресурс имеет стоимость - .

Стоимость используемых ресурсов при производстве единицы j-го продукта будет составлять:


Стоимость используемых ресурсов не может быть меньше дохода - .

Стоимость ресурсов для производителя должна быть минимальной:

 
 

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

Рассмотренные постановки ЗЛП называются взаимодвойственными.

 

I. Прямая задача II. Двойственная к ней

Матрицы коэффициентов

 
 

Знаки неравенств

 

Условия задачи

max min

 
 

Свободные коэффициенты в системе линейных ограничений

       
   
 

Коэффициенты в линейной форме

 
 

 

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

1. Если прямая задача имеет целью , то двойственная имеет целью , и наоборот.

2. Каждому ограничению прямой задачи соответствует двойственная переменная, и наоборот.

3. Матрицы ограничений прямой и двойственной задач взаимно транспонированы.

4. Коэффициенты при неизвестных в линейной форме прямой задачи являются свободными членами в ограничениях двойственной, а коэффициенты при неизвестных в линейной форме двойственной задачи являются свободными членами в ограничениях прямой.

5. Каждой неотрицательной переменной прямой задачи соответствует ограничение в виде неравенства в двойственной; переменной, которая может принимать как положительные, так и отрицательные значения, соответствует ограничение типа равенство и наоборот.

6. Перед построением двойственной задачи необходимо привести знаки всех ограничений в соответствие с линейной формой.

Если в прямой задаче , то знаки в ограничениях должны быть ≤.

Если в прямой задаче , то знаки в ограничениях должны быть ≥.

Теоремы.

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

 



Поделиться:


Последнее изменение этой страницы: 2016-04-25; просмотров: 1012; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.21.100.34 (0.152 с.)