Шпаргалка по "Математическому программированию"

, i = 1, m                      , j = 1, n

 

8. Задача о выборе назначениях или о назначениях. Экономическая постановка и построение математической модели задачи.

Экономическая постановка:

Имеются n видов работ и n исполнителей. Каждый из исполнителей может выполнить любую, но только одну работу. Задана себестоимость выполнения каждой работы, каждым исполнителем. Необходимо закрепить исполнителей за работой таким образом, чтобы общая стоимость выполнения работ была минимальной.

Математическая  постановка.

Введём обозначения  заданных параметров.

i – индекс работ, i = 1, m

j – индекс исполнителей, j = 1, n

Cij  – себестоимость выполнения i-той работы j-тым исполнителем.

     Введём неизвестные переменные. В данной задаче неизвестные переменные могут принимать только два значения 0 или 1. Такие переменные называются нулевыми.

1 - если за i-той работой закреплён  j-тый исполнитель;

x ij =

0 - в противном  случае. 

В терминах введённых обозначений данная задача запишется следующим образом:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n -1)x(n-1)(n-1) + Сnnxnn → min 

I группа ограничений.

За каждой работой  должен быть закреплён только один исполнитель: 

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1 

II. группа ограничений.

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

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1 

x ij = { 0,1} i = 1, n ; j = 1, n

 

9.  Задача о раскрое материалов. Экономическая постановка и построение математической модели задачи.

Экономическая постановка.

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

Математическая  постановка.

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

i – индекс заготовок,

Аi – необходимое количество заготовок i-того типа;

j – индекс вариантов раскроя,

Сj –размер отходов при раскрое единицы исходного материала по варианту j;

а ij – количество заготовок i-того вида при раскрое единицы исходного материала по варианту j.

Введём обозначения  неизвестных переменных.

хj- количество исходного  материала раскроенного по варианту j.

В терминах введённых  обозначений данная задача запишется следующим образом: 

z = С1x1 + С2x2 + …  +Сnxn → min

а11x1 + а12x2 +…+ а1nxn = A1

а21x1 + а22x2 +…+ а2nxn = A2

…………………………….

am1x1 + аm2x2 +…+ аmnxn =Am

xj ≥ 0, j = 1, n 

     Применение  математических моделей позволяет  экономить исходные материалы до 20 %.

     Математическая  модель раскроя строится в два  этапа.

     На  первом этапе производится построение вариантов раскроя, в результате которого определяются значения количества вариантов n, количества заготовок каждого  вида, получаемых при различных вариантах раскроя (аij), а так же значения отходов (Сj).

     Построение  вариантов раскроя единицы исходного  материала осуществляется в виде следующей таблицы: 

 

Заготовки располагаются  в порядке невозрастания их размеров. Построение вариантов осуществляется методом полного перебора. 

10. Общая форма модели задач ЛП и ее особенности

Общая форма  ЗЛП имеет вид: 

Найти максимум или минимум целевой функции  z:

z = С1x1 + … + Сnxn max (min)  

При выполнении следующих ограничений: 

а11 X1 + a12 X2 + … + а1n Xn    R1         a1

а21 X1 + a22 X2 + … + а2n Xn     R2         a2

………………………………………………….

am1 X1 + аm2 X2 +…+ аmnxn      Rm        am

хj ≥ 0, j = 1, k, k ≤ n  

В общей форме  каждый символ R1 , R2 ,…, Rm означает один из знаков: ≥, = или ≤ .  

Общая форма  модели задачи ЛП обладает следующими особенностями.

1. Система ограничений представлена в виде уравнений (жестких условий) и неравенств (нежестких условий).
2. Условия неотрицательности накладываются не на все переменные
3. Целевая функция стремится либо к максимуму, либо к минимуму.

 

 

11. Стандартная форма модели задач ЛП и ее особенности

Стандартная форма имеет следующий  вид.

Найти максимум или минимум целевой  функции z: 

z = С1x1 + … + Сnxn → max (min) (1) 

При выполнении следующих ограничений: 

а11 Х1 + а12 Х2 + … + а1n Хn   ≤ а1

а21 Х1 + а22 Х2 + … + а2n Хn   ≤ а2

…………………………………………..

am1 Х1 + аm2 Х2 +… + аmn Хn ≥ аm

хj ≥ 0, j = 1, k,  k ≤ n  

     Особенности стандартной формы модели задачи ЛП следующие:

1. система ограничений представлена в виде неравенств (нежестких условий)
2. условия неотрицательности накладываются на все переменные
3. целевая функция стремится либо к max, либо к min

 

 

12. Каноническая форма модели задач ЛП и ее особенности

Каноническая  форма имеет вид:

Найти минимум  целевой функции z: 

z = С1x1 + … + Сnxn → min  

При выполнении следующих ограничений:

а11 Х1 + а12 Х2 + … + а1n Хn = а1

а21 Х1 + а22 Х2 + … + а2nxn = а2

…………………………

am1x1 + аm2 X2 +… + аmn Xn = am

Xj ≥ 0, j = 1, n 

     Особенности канонической формы следующие:

1. Система ограничений представлена в виде уравнений (жестких условий).
2. Условия неотрицательности накладываются на все переменные
3. Целевая функция стремится к

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

 

     

13. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП 

Определение 1. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами.

Определение 2. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных (ОДЗ).

Определение 3. План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным. 
 

 

     

14. Виды записей задач ЛП: развернутая, свернутая, матричная, векторная.

     Модели  задач ЛП могут быть записаны в различных видах.

     1. Развернутый вид записи модели

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am, 

Xj ≥ 0, j = 1, n. 

     2. Свернутый вид:

                              ,

Xj ≥ 0, j = 1, n. 

     3. Модель задачи ЛП в матричном  виде:

                  X ≥ 0

Где 

               а11    а12    …    а1n                         X1                           a1

  A=       a21    a22    …    a2n   ,           X=     X2  ,            A0 =    a2

               …      …     …     …                           …                            …

               am1  am2  …    amn                          X3                           am

 

     4. Модель задачи ЛП в векторном  виде:

X ≥ 0

Где    

          Х1                 a11                  a12                 a1n                 a1

  Х2    ,     a21   ,      a22   ,   a2n   ,    a2

          …                   …                   …                   …                   …

          Хn                  am1                 am2               am2               am 

 

     

15. Переход от стандартной и общей формы задач ЛП к канонической. Теорема связи

Для перехода от общей или стандартной формы к канонической используют следующие приёмы.

     1. Преобразование переменных. Если какая-то переменная Xk неположительна (Xk ≤ 0), то вводят новую переменную Xk ', так что Xk ' =  –Xk . Очевидно, что Xk ' ≥ 0. После этого в каждом ограничении и целевой функции переменную Xk заменяют на [ – Xk '].

     Если  какая-то переменная Хt может принимать любые значения, то её заменяют разностью двух неотрицательных переменных Хt’ и Хt’’,  т. е. полагают, что хt = Хt’ – Хt’’, где Хt’ 0 ≥ и Хt’’  ≥ 0.

     2. Преобразование ограничений. Если какое–либо из ограничений в модели имеет вид неравенства, то оно преобразуется в равенство прибавлением (если неравенство имеет тип ≤) или вычитанием (если неравенство имеет тип ≥) из его левой части. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая – Х7 и т.д.