Курсовая работа по «Теории принятия решения»

Министерство  науки и образования

 

Московский  Государственный Горный Университет

 

Кафедра АСУ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая работа

по дисциплине

«Теория принятия решения»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2013

Задание.

 

№ 1.40. Решить ЗЛП симплекс методом:

 

min z = -2x₁ + 3x₂ - 6x₃ - x₄

2x₁ + 2x₂ + 4x₃ ≤ 22

x₁ - x₂ + 2x₃ ≥ 10

x_j ≥ 0

 

 

№ 2.36. Решить транспортную задачу:

 

						ai
	6	7	3	5		100
С=	1	2	5	6		150
	8	10	20	1		50
bi	75	80	60	85

№ 5.10. Решить задачу дискретного программирования:

 

max z = x₁ + 4x₂

2x₁ + 4x₂ ≤ 17

10x₁ + 3x₂  ≤ 15

x₁, x ₂ ≥ 0

x₁, x ₂ – целые

 

 

 

 

 

 

 

Содержание.

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

1.1. Симплекс метод решения ЗЛП 4

1.1.1.Построение  опорного(начального плана 4

1.1.2.Признак  оптимальности опорного плана.  Симплексные таблицы 6

1.1.3.Переход  к нехудшему опорному плану 7

1.1.4.Симплексные преобразования 8

1.2. Блок-схема  решения задачи 10

1.3. Физическая  интерпретация задачи  11

1.4. Аналитическое решение задачи 11

2. Транспортная  задача линейного программирования 13

2.1. Определение  транспортной задачи 13

2.1.1. Формулировка  ТЗЛП 13

2.1.2. Математическая  формулировка ТЗЛП 13

2.1.3. Нахождение  начального плана транспортировок.  Метод северо-западного угла 14

2.1.4. Оптимальный  план транспортной задачи. Метод  потенциалов. 15

2.1.5. Получение оптимального плана транспортной задачи с использованием метода потенциалов 15

2.2. Блок-схема  решения задачи 17

2.3. Физическая  интерпретация задачи 18

2.4. Аналитическое  решение задачи 18

3. Дискретное  программирование 26

3.1. Пример целочисленной задачи линейного программирования. Алгоритм метода Гомори 26

3.1.1. Процесс  формирования правильного отсечения 27

3.2. Блок-схема  решения задачи 28

3.3. Физическая  интерпретация задачи 29

3.4. Аналитическое  решение задачи 29

Список  используемой литературы 35

 

 

 

 

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

 

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

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

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

 

1.1. Симплекс метод решения ЗЛП.

 

Идея симплекс метода состоит в  умении рационально перебирать крайние точки многогранника решений. Переход от одной крайней точки к еще лучшей (не худшей) осуществляется до тех пор, пока в одном из этих точек не будет достигнуто оптимальное решение, т.е. целевая функция обратится в max или min.

Симплекс метод (метод последовательных улучшений) плана предполагает следующие  этапы:

• определение опорного (начального) плана;
• определение наличия признака оптимальности плана;
• переход к нехудшему (оптимальному) опорному плану.

 

1.1.1. Построение опорного (начального) плана.

 

Пусть ЗЛП представлена системой ограничений  в каноническом виде:

Говорят, что ограничение ЗЛП имеет  предпочтительный вид, если при неотрицательности  правой части  левая часть ограничения содержит переменную, входящую с коэффициентом равным единице, а в остальные ограничения-равенства – с коэффициентом равным нулю. Если каждое ограничение-равенство ЗЛП в каноническом виде содержит переменную, входящую в левую часть с коэффициентом равным единице, а во все остальные с коэффициентом равным нулю (при неотрицательности правых частей), то это значит, что система ограничений представлена в предпочтительном виде. В этом случае легко найти ее опорное решение (базисное с неотрицательными координатами), все свободные переменные нужно приравнять к нулю, тогда базисные переменные будут равны свободным членам.

Пусть система ограничений имеет вид: 

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

которая имеет предпочтительный вид. И начальный опорный план примет вид:

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю:                                      

Пусть система ограничений имеет вид:

Сведем ее к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему:

Однако теперь система ограничений  не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть с коэффициентами, равными -1, поэтому базисный план:

является недопустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида добавляют искусственные переменные ω_i. В целевую функцию искусственные переменные ω_i вводятся с коэффициентом М в случае решения задачи на min и с коэффициентом -М для задачи на max, где М – большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.

Пусть исходная ЗЛП имеет вид:    

             (1)

   

 

 

 

причем ни одно из ограничений не имеет предпочтительной переменной.

М-задача запишется так:

   

где знак «-» в функции (4) относится к задаче на max. Задача (4 – 6) имеет предпочтительный вид. Ее начальный (опорный) план:

Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Таким образом для того что бы решить задачу с ограничениями не имеющую предпочтительного вида вводится искусственный базис и решается М-задача, которая имеет начальный (опорный) план x₀=(0; 0; …; 0; b₁; b₂; …; b_m)

Решение исходной задачи симплекс методом  путем введения искусственной переменной W_i называется симплекс методом с искусственным базисом.

Теорема 1.  Если в оптимальном плане                  

М-задачи 4 – 6 все искусственные переменные , то план

является оптимальным планом исходной задачи 1 – 3.

Теорема 2. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов.

 

1.1.2. Признак оптимальности опорного плана.

Симплексные таблицы.

 

Любую ЗЛП можно представить  в эквивалентном предпочтительном виде:

Выразим базисные переменные x₁, x₂, ..., x_m из равенств (10) через свободные x_m+1, x_m+2, ...,x_n и подставим их в целевую функцию. После группировки подобных членов получается

Z= (c₁b₁+c₂b₂+...+c_mb_m) – ((c₁a_1,m+1+c₂a_2,m+1+...+c_ma_m,m+1) – c_m+1)x_m+1 +

(( c₁a_1,m+2+c₂a_2,m+2+...+c_ma_m,m+2) - c_m+2)x_m+2 +...+

                            + ((c₁a_1n+c₂a_2n+...+c_ma_mn) – c_n)x_n)                        (12)

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

                                 ∆₀= c₁b₁+c₂b₂+...+c_mb_m = с_БА₀                         (13)

              ∆_j= (c₁a_1j+c₂a_2j+...+c_ma_mj) – c_j = с_БА₀ - c_j           (14)

где С_Б = (с₁; с₂; ...; с_m) – вектор коэффициентов целевой функции при базисных переменных;

А₀ = (b₁; b₂; ...; b_m)^Т – вектор-столбец свободных членов;

А_j = (a_1j; a_2j; ...; a_mj)^Т – вектор-столбец коэффициентов при переменных x_j.

С учетом равенств (12) – (14) задача (9) – (11) примет вид:

где ∆₀ = с_БА₀; ∆_j= с_БА₀ - c_j   .

Задача (15) – (17) записывается в таблицу (Табл.1), которая называется симплексной.

Табл. 1

Бп	Сб	А0	х1	х2	...	xi	...	xm	xm+1	...	xj	...	xn
			c1	c2	...	ci	...	cm	cm+1	...	сj	...	cn
x1	c1	b1	1	0	...	0	...	0	a1,m+1	...	a1j	...	a1n
x2	c2	b2	0	1	...	0	...	0	a2,m+1	...	a2j	...	a2n
...	...	...	...	...	...	...	...	...	...	...	...	...	...
xi	ci	bi	0	0	...	1	...	0	ai,m+1	...	aij	...	ain
...	...	...	...	...	...	...	...	...	...	...	...	...	...
xm	cm	bm	0	0	...	0	...	1	am,m+1	...	amj	...	amn
zj - cj		Δ0	0	0	...	0	...	0	Δm+1	...	Δj	...	Δn

 

Последнюю m+1 строку называют индексной строкой (строкой целевой функции), число ∆₀ = с_БА₀ – значение целевой функции для начального опорного плана х₀, т.е. ∆₀ = z(x₀) = С_БА_0. Числа ∆_j= С_БА₀ - c_j   называются оценками свободных переменных.

Если все оценки (при решении задачи на максимум) и (при решении задачи на минимум), то опорный план оптимален. Если план не оптимален, то нужно перейти к новому не худшему опорному плану.

 

1.1.3. Переход к нехудшему опорному плану.

 

Пусть решается ЗЛП с системой ограничений в предпочтительном виде:                         

                               

Ее опорный план х₀ = (b₁; ...; b_m; 0; ...; 0). Значение целевой функции z(x₀)= с_БА₀ =∆₀.

Рассматривается задача на максимум.

Если все  , то опорный план х₀ оптимален. Пусть существует j₀, для которого Δ_j0< 0. Вектор-столбец А_j0, для которого Δ_j0< 0, называется разрешающим, соответствующая переменная х_j0 – перспективной.

Для определения переменной исключенной  из базиса находится симплексное отношение:                           

Если это условие выполняется  при нескольких i, то в качестве i₀ можно выбрать любое. Строку i₀ называют разрешающей, элемент же a_i0j0 – разрешающим.

В результате преобразований получен новый опорный план х₁, в котором переменная x_i0 заменена на x_j0, причем ∆₀ - ∆_j0q = z(x₀) -  ∆_j0q. Но ∆_j0<0, следовательно, z(x₁)³ z(x₀). Новый план х₁ не хуже начального х₀.

В случае решения задачи на максимум число шагов, как правило уменьшается, если разрешающий столбец выбрать по правилу max½Δ_j½   (Δ_j<0), т.е. в базис вводить переменную, соответствующую максимальной по абсолютной величине отрицательной оценке.

В случае задачи на минимум разрешающий  столбец нужно выбирать по правилу max Δ_j (Δ_j>0). Далее процесс повторяется. Проверяется, является ли план х₁ оптимальным. Если да, то задача решена. Если нет, то следует перейти к нехудшему опорному плану х₂, смежному с х₁, и т.д.

 

1.1.4. Симплексные преобразования.

 

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

1. Элементы строки i₀ новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разрешающий элемент: