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

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. Нахождение начального плана транспортировок.

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