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

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

 

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

 

Кафедра АСУ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 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₀ новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разрешающий элемент:

2. Элементы разрешающего столбца j₀ новой таблицы равны нулю, за исключением :

    

3. Чтобы найти любой другой элемент новой симплексной таблицы, нужно воспользоваться правилом прямоугольника (рис.1), вытекающим из формул:

                             

 

 

 

 

 

 

 

Диагональ, содержащую разрешающий  и искомый элементы новой таблицы, называют главной, а другую – побочной. Чтобы получить элемент (i=i₀; j¹j₀) новой симплексной таблицы, нужно из произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент, выделенный рамкой. Это правило прямоугольника.

Как следует из равенств (19), любой элемент новой таблицы можно найти по правилу треугольника: для получения любого элемента новой симплексной таблицы нужно из соответствующего элемента прежней таблицы вычесть произведение элемента разрешающей строки на элемент разрешающего столбца, разделенное на разрешающий элемент.

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

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

 

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

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

 

Для изготовления четырех сортов пива: A₁, А₂, А₃, А₄ использует два вида сырья: х₁ - солод, х₂ - хмель.

Прибыль, полученная от реализации каждого  сорта пива, указана в таблице (Табл.2). В ней так же указано, сколько единиц каждого сырья необходимо для изготовления каждого сорта пива и общее количество сырья (причем количество первого сырья должно быть не больше 22, а количество второго сырья больше 10).

При этом 1 единица второго вида сырья (хмель) оказывает нежелательное воздействие на второй сорт пива. Прибыль, полученная от реализации A₁, А₃, А₄ сортов пива, оказывается недостаточной.

Табл.2

Вид сырья	Сорта пива				Количество сырья (кг)
	A1	А2	А3	А4
х1	2	2	4	0	22
х2	1	-1	2	0	10
Прибыль от реализации продукции (у.е.)	-2	3	-6	-1

 

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

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

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

x₁ - x₂ + 2x₃ ≥ 10

x_j ≥ 0

Сведем задачу к каноническому  виду. Для этого введем дополнительные переменные - x₅ и x₆. В первом неравенстве переменная x₅  прибавляется к левой части (т.к. неравенство имеет знак ≤), во втором неравенстве переменная x₆ отнимается от левой части (т.к. неравенство имеет знак ≥ ).

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

2x₁ + 2x₂ + 4x₃ + x₅ = 22

x₁ - x₂ + 2x₃ - x₆ = 10

x_j ≥ 0 ; (j=1,6)

Второе ограничение имеет предпочтительный вид, а первое нет, поэтому введем искусственную переменную W. И перейдем к М-задаче.

min z = -2x₁ + 3x₂ - 6x₃ - x₄ + 0x₅ + 0x₆ + MW

2x₁ + 2x₂ + 4x₃ + x₅ = 22

x₁ - x₂ + 2x₃ - x₆ + W= 10

 

Запишем условия М-задачи в симплекс таблицу (табл.3).

Табл.3

Бn	Cб	А0	x1	x2	x3	x4	x5	x6	W
			-2	3	-6	-1	0	0	M
x5	0	22	2	2	4	0	1	0	0
W	M	10	1	-1	2	0	0	-1	1
Zj - Ci		0	2	-3	6	1	0	0	0
		10M	M	-M	2M	0	0	-M	0

Начальный опорный план равен Х=(0;0;0;0;22;10). Для задачи  минимизации условием оптимальности опорного плана является Δ_j ≤ 0. В данном случае в индексной строке имеются положительные оценки, поэтому данный опорный план не оптимален. Разрешающим элементом будет а₂₃=2.

Табл.4

Бn	Cб	А0	x1	x2	x3	x4	x5	x6
			-2	3	-6	-1	0	0
x5	0	2	0	4	0	0	1	2
x3	-6	5	1/2	-1/2	1	0	0	-1/2
Zj - Ci		-30	-1	0	0	1	0	3

 

В данном случае в индексной строке имеются положительные оценки, поэтому данный опорный план не оптимален. Разрешающим элементом будет а₁₆=2.

Таб.5

Бn	Cб	А0	x1	x2	x3	x4	x5	x6
			-2	3	-6	-1	0	0
x6	0	1	0	2	0	0	1/2	1
x3	-6	5 1/2	1/2	1/2	1	0	1/4	0
Zj - Ci		-33	-1	-6	0	1	-11/2	0

 

Задача не имеет решения так  как данном случае в индексной строке имеется положительная оценка, а элементы столбца равны нулю.

 

 

 

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

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

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

 

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

Имеется m пунктов отправления А1,А2,…,Аm, в которых сосредоточены запасы груза в количестве а1,а2,…,аm единиц. Кроме того имеется n пунктов назначения B1,B2,…,Bn подавших заявки соответствующие b1,b2,…bn единиц товара. Предполагается, что сумма всех заявок равна сумме всех запасов:

Известна стоимость cij перевозки единицы товара из назначенного пункта Ai в пункт Bj.

Требуется найти такой план перевозок, при котором все заявки были бы выполнены , при этом общая стоимость  всех перевозок была бы минимальна. Показателем эффективности является стоимость.

 

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

 

xij – количество груза отправленного из аi пункта в bj пункт назначения.

Неотрицательные переменные x11,…,x1m, число которых равно n*m , должны удовлетворять условиям:

1. Суммарное количество груза  отправленного из начального  пункта отправления во все  пункты назначения должно быть равно запасу груза в данном пункте.

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

 

3.Суммарная стоимость всех перевозок  xij cij должна быть минимальна.

Знак «∑∑» показывает, что суммарное  произведение по всем комбинациям индексов i [1,m]  j[1,n]. Обратим внимание, что все коэффициенты при переменных в уравнении 2 и 3 равны единице, а это значит, что задача может быть решена более просто чем при использовании симплекс метода.

Условия  2 и 3 связаны одной линейной зависимостью и из них только m+n-1 являются линейно не зависимыми и таким образом ранг состемы 2 и 3 равен r=m+n-1.

А следовательно разрешить эти  уравнения относительно m+n-1 базисных переменных, выразив их через остальные свободные. Количество свободных переменных будет равно k=(m-1)(n-1).

Любая совокупность значений xij называется планом перевозок или просто планом. Он называется допустимым, если удовлетворяет условиям 2 и 3. Опорный план это допустимый план, если в нем отличных от нуля  не более r=m+n-1 базисных перевозок, а остальные перевозки равны нулю. План xij называется оптимальным, если он среди всех допустимых планов приводит к наименьшей стоимости перевозок. Методы решения ТЗЛП сводятся к операции с таблицей(табл.6).

Табл.6

ПН ПО	B1	B2	…	Bn	Запасы ai
А1	c11	c12	…	c1n	a1
А2	c21	c22	…	c2n	a2
…	…	…	…	…	…
Аn	cn1	cn2	…	cnn	an
Заявки bj	b1	b2	…	bn

 

Как уже отмечалось, ранг системы  r=m+n-1, где m – число строк, n – число столбцов. Значит в каждом опорном плане, включая оптимальный, будут отличны от нуля не более чем m+n-1 перевозок.

  Ячейки с отличными от нуля перевозками называются базисными, а остальные пустые – свободными. Таким образом решение ТЗ сводится к следующему. Найти такие значения положительных перевозок, поставленные в базисных клетках удовлетворяли условиям:

1. Сумма перевозок в каждой  строке должна быть равна запасам  данного ПО.

2. Сумма перевозок в каждом  столбце должна быть равна заявке ПН.

3. Общая стоимость минимизации.

 

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

 Метод северо-западного угла.