Исследование операций

Размещено на Allbest.ru

Введение

линейное нелинейное программирование

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

Исследование операций в настоящее время - одна из самых быстро развивающиеся наук, завоевывающая все более обширное поле применения. В данной курсовой работе рассматриваются задачи линейного программирования на основе табличного симплекс-метода, задачи линейного программирования на основе геометрической интерпретации, задачи линейного программирования по критерию стоимости на основе метода потенциалов, задачи квадратичного программирования на основе метода Лагранжа.

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

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

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

ПОСТАНОВКА ЗАДАНИЯ

ЗАДАЧА 1.

Решить геометрически (или убедиться в неразрешимости) задачу ЛП:

max (min) F (X) =c1x1+c2x2,

Данные для расчета сведены в табл. 1.

Таблица 1

F (x)	c1	c2	a11	a12	а21	a22	a31	a32	b1	b2	b3
max	2	3	-4	-3	-2	-1	1	-1	-28	-4	-3

ЗАДАЧА 2

Решить задачу ЛП табличным симплекс-методом:

max (min) F (X) =c1x1+c2x2,

Данные для расчета сведены в табл. 2.

Таблица 2

F (x)	c1	C2	a11	a12	a21	a22	a31	a32	b1	b2	b3
max	3	-2	6	7	2	-3	-1	1	42	6	3

ЗАДАЧА 3

Решить транспортную задачу по критерию стоимости:

Данные для расчета сведены в табл. 3.

Таблица 3

c11	c12	c13	c14	c15	c21	c22	c23	c24	c25	c31	c32	c33	c34	c35	a1	a2	a3	b1	b2	b3	b4	b5
2	3	2	8	1	3	1	5	7	4	4	4	3	2	5	50	30	20	10	20	40	15	15

ЗАДАЧА 4

Решить задачу квадратичного программирования на основе метода искусственного базиса; найти графическое решение задачи.

Данные для расчета сведены в табл. 4.

c1	c2	d11	d22	d12	a11	a12	a21	a22	b1	b2
3	-2	-0. 5	-1	1	2	1	1	2	2	2

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

F (X) = c1 x1 +c2 x2 +... +cn xn,

При ограничениях неравенствах:

a11 x1 +a12 x2 +... + a1n xn b1,

a21 x1 +a22 x2 +... + a2nxn b2,

… … … …

am1 x1 +am2 x2 +... + amn xn bm.

При необходимости перехода от задачи максимизации к задаче минимизации целевой функции следует изменить знаки коэффициентов cj при переменных xj, на противоположные, т. е. задача максимизации функции F (X) = (C, X) приводится к задаче на поиск минимума функции -F (X) = (C, X).

Вектор X ={ x1, x2,..., xn }, удовлетворяющий ограничениям задачи ЛП, называется решением. При X 0 полученное решение называется допустимым. Если X обращает в максимум (минимум) целевую функцию F (X), то решение называется оптимальным.

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Графический метод основан на геометрической интерпретации задачи ЛП. Рассмотрим ограничения в виде равенств. Будем исходить из того, что число переменных n на два больше числа независимых уравнений ограничений m, т. е. n-m =2. Тогда две из переменных, например x1 и x2 можно принять в качестве свободных, а остальные m сделать базисными и выразить их через свободные. В результате получим m=n-2 уравнений вида:

x3 = 31 x1 +32 x2 +3,

x4 = 41 x1 +42 x2 +4,

.................,

xn = n1 x1 +n2 x2 +n.

где ij и i сочетани коэффициентов aij bi соответственно.

Будем искать решение задачи на плоскости в прямоугольной системе координат x10x2 (рис. 1). Допустимые решения для переменных x1 и x2 будут находиться выше оси 0x1 и правее.

Найдем на плоскости x10x2 отображения остальных переменных x3, x4,..., xn в соответствии с уравнениями (). С этой целью рассмотрим например переменную x3 и положим, что ее величина равна своему крайнему значению, т. е. x3 =0. Тогда из первого уравнения системы получим:

31 x1 +32 x2 +3 =0.

Это уравнение прямой на которой x3 =0. Заштрихованная сторона этой прямой соответствует x3 >0.

Аналогично строятся и остальные ограничивающие прямые x4 =0, x5 =0,... xn =0, для каждой из которых определяется сторона, где x1 0, x2 0,..., xn 0. Часть плоскости x10x2 (заштрихованная область), называется областью допустимых решений (ОДР). В этой области значения всех переменных положительны. Вершины ОДР называются базисными допустимыми решениями.

Для нахождения оптимального решения подставим () в выражение для целевой функции и после приведения подобных членов получим

F (x) =0 + 1 x1 + 2 x2

Запишем вместо F (x) функцию

F1 (x) = 1 x1 + 2 x2

Обе функции достигают максимума (минимума) при одних и тех же значениях переменных x1 и x2.

Найдем значения x1 и x2 доставляющие максимум (минимум) функции F1 (x). Для этого определим положение этой функции на плоскости x10x2, как показано на рисунке. При F1 (x) =0 эта функция есть прямая проходящая через начало координат. Вторая точка через которую пройдет эта прямая, определяется координатами x1=2, x2=1. Если функции F1 (x) придавать различные постоянные значения, то прямая на рисунке, отображающая эту функцию, будет перемещаться параллельно самой себе. Очевидно, максимального значения функция достигнет, когда прямая F1 (x) достигнет крайней точки С области допустимых решений.

Оптимизационные исследования задач ЛП удобно проводить, пользуясь симплекс-таблицами. Существует достаточно большое количество форм симплекс-таблиц. Воспользуемся одной из форм, по которой рекомендуется следующий порядок решения задачи ЛП:

1. Математическая модель задачи приводится к расширенной форме.

2. Определяется начальное базисное допустимое решение.

3. Составляется исходная симплекс-таблица (табл. 4), в которую вносятся следующие параметры, соответствующие начальному базисному допустимому решению:

3. 1. Весовые коэффициенты cj при переменных xj (j=1,..., n) целевой функции (строка C).

3. 2. Весовые коэффициенты cj при базисных переменных xi (i=1,..., m) целевой функции (столбец C).

3. 3. Переменные xi (i=1,..., m), которые входят в текущий базис (столбец Хр).

3. 4. Свободные коэффициенты b i (i=1,..., m) уравнений ограничений (столбец B).

3. 5. Элементы a ij (i=1,..., m; j=1,..., n) матрицы условий задачи (столбцы A1,.., An).

Таблица 4

C			c1	...	cj	...	ck	...	cn
	Хр	B	A1	...	Aj	...	Ak	...	An
c1	x1	b1	A11	...	a1j	...	a1k	...	a1n
...	...	...	...	...	...	...	...	...	...
ci	xi	bi	ai1	...	aij	...	aik	...	ain
...	...	...	...	...	...	...	...	...	...
cr	xr	br	ar1	...	arj	...	ark	...	arn
...	...	...	...	...	...	...	...	...	...
cm	xm	bm	am1	...	amj	...	amk	...	amn
S			S1	...	Sj	...	Sk	...	Sn

Оценки Sj (j=1,..., n) векторов условий Aj, которые определяются по формуле:

где ci весовые коэффициенты при базисных переменных.

Из этой формулы следует, что коэффициенты z j вычисляются для каждого столбца как сумма почленных произведений коэффициентов ci на одноименные коэффициенты j-го столбца. При заполнении симплекс-таблицы (в дальнейшем будем рассматривать задачу максимизации целевой функции) необходимо иметь в виду:

если Sj 0 для всех j=1,..., n, то полученное решение является оптимальным;

если имеются Sj <0 и в столбцах Aj, соответствующих этим отрицательным оценкам, существует хотя бы один элемент aij > 0, то возможен переход к новому решению, связанному с большим значением целевой функции;

если имеются Sk <0 и в столбце Ak все элементы aik 0, то в области допустимых решений целевая функция не ограничена сверху.

4. Определяется вектор Ak, который необходимо ввести в базис для улучшения решения, по наибольшему значению k. Переменная этого столбца xk будет новой базисной переменной, которая вводится в базис. Столбец, содержащий эту переменную, называется направляющим столбцом.

5. Определяется вектор, который нужно вывести из базиса, используя равенство:

Это условие позволяет найти направляющую строку. Переменная xr, соответствующая этой строке, выводится из базисного решения и заменяется переменной xk направляющего столбца. Элемент ark, который стоит на пересечении направляющего столбца и направляющей строки, называется направляющим элементом.

6. Заполняется таблица соответствующая новому базисному решению. В этой таблице, прежде всего заполняются клетки строки r с вводимой переменной xk. Для этого все элементы этой строки делятся на направляющий элемент. Получаются элементы новой строки:

Остальные элементы новой таблицы определяются по формулам исключения (на основании метода полного исключения Гаусса) :

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

ТРАНСПОРТНАЯ ЗАДАЧА

Классическая транспортная задача формулируется следующим образом.

Имеется m пунктов отправления (производства) A1, A2,..., Am, в которых расположены запасы некоторого однородного продукта (груза). Объём этого продукта в пункте Ai составляет ai единиц. Кроме того, имеется n пунктов потребления B1, B2,..., Bn. Объём потребления в пункте Bj составляет bj единиц.

Предполагается, что из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления. Известна также стоимость cij перевозки единицы продукта из пункта Ai в пункт Bj.

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

При такой постановке данную задачу называют транспортной задачей по критерию стоимости.

Условия транспортной задачи (Т-задачи) можно представить в виде табл. 5.

Таблица 5

ПП ПО	B1	B2	...	Bn	Запасы ai
A1	c11	c12	...	c1n	a1
A2	c21	c22	...	c1n	a2
...	...	...	...	...	...
Am	cm1	cm2	...	cmn	am
Заявки bj	b1	b2	...	bn

В табл. 5 приняты обозначения: ПО - пункты отправления продукта; ПП - пункты потребления. Равенство, приведенное в нижнем правом углу таблицы, означает, что сумма заявок пунктов потребления равна сумме запасов продуктов в пунктах отправления.

Составим математическую модель сформулированной задачи. Обозначим xij - количество продуктов, отправляемых из i-го пункта Ai в j-й пункт Bj. Требуется определить множество переменных xij 0 (число которых очевидно равно mn), удовлетворяющих условиям:

и доставляющих целевой функции

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

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

Из (1) и (2) следует, что Т-задача имеет mn ограничений-равенств.

Переменные {xij}, удовлетворяющие условиям (1) и (2), записываются в виде матрицы:

Матрица X носит название плана перевозки или просто плана Т-задачи, а переменные xij называются перевозками. План X* называют оптимальным, если целевая функция имеет минимальное значение, т. е. стоимость всех перевозок является наименьшей.

Рассмотрим решение Т-задачи, основанное на преобразовании табл. 5 и состоящее из следующих основных этапов:

определение опорного плана;

оценка опорного плана;

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

Опорным планом Т-задачи называют любое ее допустимое базисное решение.

План называют допустимым, если он удовлетворяет условиям (1) и (2).

Нахождение опорного плана покажем с помощью метода “ северо-западного “ угла. Заполнение таблицы начинается с левого верхнего элемента x11 матрицы X:

x11 = min (a1, b1)

при этом возможны три случая:

если a1 < b1, то x11 = a1, а оставшаяся часть первой строки, начиная со второго элемента, заполняется нулями;

если a1 > b1, то x11 = b1, а оставшиеся элементы первого столбца заполняются нулями;

если a1 = b1, то x11 =a1=b1, а оставшиеся элементы первых строк и столбца заполняются нулями.

Затем вычисляются x12 =min (a x11, b2) при a1 > b1 или x21=min (a2, b2 x11) при a1 < b1.

Этот процесс повторяется до тех пор, пока матрица X не будет полностью заполнена.

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

Правило “минимального элемента“ позволяет построить опорный план с учетом матрицы стоимости перевозок C. Это сокращает количество итераций при поиске оптимального решения.

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

Определяется элемент cij матрицы C, который соответствует наименьшей стоимости перевозки. Начиная с этого элемента последовательно нумеруются элементы матрицы C в порядке их возрастания. Затем в том же порядке определяются элементы xij матрицы X, используя процедуру правила “северо-западного угла”.

Улучшение опорного плана можно обеспечить, используя, например метод потенциалов, сущность которого состоит в следующем.

Для опорного плана определяются потенциалы ui и vj, соответствующие базисным клеткам, по условию:

ui + vj = cij

Таких уравнений будет mn1, а переменных будет mn. Для их определения одну из переменных полагают равной любому постоянному значению. Обычно принимают ui =0. После этого для небазисных клеток опорного плана определяются оценки ,

где .

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

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ

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

Модель задачи квадратичного программирования имеет следующую структуру:

найти максимальное (минимальное) значение функции

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

Второе слагаемое в выражении (*) называется квадратичной формой переменных х1, х2, …, хn и представляются в виде:



Матрица коэффициентов квадратичной формы предполагается симметричной (dkj = djk). Диагональные элементы dkk этой матрицы являются коэффициентами при , а недиагональные элементы (dkj = djk) равны половине коэффициента при xkxj

Можно использовать следующий порядок нахождения решения решения задачи квадратичного программирования:

Составляется функция Логранжа.

Записываются ограничения.

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

Находится оптимальное решение при выполнении условий п. (2).

РАСЧЕТНАЯ ЧАСТЬ

ЗАДАЧА 1

Целевая функция F (x) =2x1 + 4x2 max;

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

Для приведения к положительным правым частям умножаем необходимые ограничения на (-1) и записываем в виде:

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

Неравенства ограничений приведем к равенствам, используя дополнительные переменные x 3, x 4 и x 5 :

х1, х2 - свободные переменные.

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

Выразим систему ограничений относительно базисных переменных и приравняем полученные уравнения к нулю:

где x 1, x 2, x 3, x 4, x 5 >0

переменные x 3, x 4 и x 5 примем в качестве базисных и выразим через свободные x 1 и x 2

Прямые, соответствующие граничным значениям переменных x3 = x4 = x5= 0 представлены на рис. 2. Заштрихованная область будет областью допустимых решений.

Рис. 2, 3

Максимального значения целевая функция достигает в крайней точке B области допустимых решений. Координаты точки A будут оптимальным решением задачи:

ЗАДАЧА 2

Решить задачу методом симплекс - таблиц.

Целевая функция F (x) = 3x1-2x2 max;

Уравнения ограничения

Запишем уравнения ограничения в расширенной форме:

6x1 + 7x2 + x3 = 42,

2x1 - 3x2 +x4 = 6,

-x1 + x2 + x5 = 3,

x1, x2 0.

Целевая функция примет вид: F (x) = 2x1-2x2 +0x3 +0x4 +0x5 max

Обозначим векторы условий задачи через A1 A5. Векторы A3, A4, A5 образуют единичную матрицу, которую примем за базис. В результате начальное базисное допустимое решение будет иметь вид X (0, 0, 42, 6, 0, 3).

Составим исходную симплекс-таблицу (табл. 6), в которой рассчитаем элементы строки

Таблица 6

C			c1 3	c2 -2	c3 0	c4 0	c5 0
	ХP	B	A1	A2	A3	A4	A5
c3 0	X3	42	6	7	1	0	0
c4 0	X4	6	2	-3	0	1	0
C5 0	X5	3	-1	1	0	0	1
S		0	3	-2	0	0	0

В индексной строке табл. 6 имеются Sj > 0, что позволяет улучшить решение задачи.

Вводим в новый базис вектор A1, которому соответствует наибольшее значение S1 = 3, а в новое базисное решение переменную x1. Столбец, содержащий вектор A1 будет направляющим.

Составим отношения вида , по которым определим направляющую строку. Для этого находим:

Таким образом направляющая строка вторая, направляющий элемент a21 (в таблице заключен в прямоугольник). Из базиса выводится вектор A4, а из базисного решения переменная x4.

Рассчитаем и заполним новую таблицу соответствующую новому базисному решению.

Таблица 7

C			c1 3	c2 -2	c3 0	c4 0	c5 0
	ХP	B	A1	A2	A3	A4	A5
C3 0	X3	24	0	16	1	-3	0
C1 3	X1	3	1	-3/2	0	1/2	0
С5 0	Х5	6	0	-1/2	0	1/2	1
S		9	0	2, 5	0	-3/2	0

В индексной строке табл. 7 имеются Sj > 0, что позволяет улучшить решение задачи.

Вводим в новый базис вектор A2, которому соответствует наибольшее значение S2 = 2, 5, а в новое базисное решение переменную x2. Столбец, содержащий вектор A2 будет направляющим.

Составим отношения вида , по которым определим направляющую строку. Для этого находим:

Таким образом направляющая строка вторая, направляющий элемент a12 (в таблице заключен в прямоугольник). Из базиса выводится вектор A3, а из базисного решения переменная x3.

Рассчитаем и заполним новую таблицу соответствующую новому базисному решению.

Таблица 8

C			c1 3	c2 -2	c3 0	c4 0	c5 0
	ХP	B	A1	A2	A3	A4	A5
C2 -2	X2	3/2	0	1	1/16	-3/16	0
C1 3	X1	21/4	1	0	3/32	7/2	0
С5 0	Х5	27/4	0	0	1/32	13/2	1
S		51/4	0	0	-5/32	-87/8	0

В таблице все Sj 0. Поэтому полученное решение является оптимальным:

ЗАДАЧА 3

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

3 5

Целевая функция F = c ij xij;

i=1 j=1

Условия транспортной задачи представлены в табл. 9

Табл. 9

ПП ПО	В1	В2	В3	В4	В5	Запасы
А1	2	3	2	8	1	50
А2	3	1	5	7	4	30
А3	4	4	3	2	5	20
Заявки	10	20	40	15	15

Определим опорный план, используя правило “северо-западного угла”.

Результаты сведены в табл. 10.

Таблица 10

2 10	3 20	2 20	8	1	50
3	1	5 20	7 10	4	30
4	4	3	2 5	4 15	20
10	20	40	15	15

Таким образом опорный план имеет вид:

Полученное решение является опорным (начальным базисным допустимым решением), в котором переменные имеют значения: х11=10; х12=20; х13=20; х23=20; х24=10; х34=5; х35= 15.

Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость: F = 10*2 + 20*3 + 20*2 + 20*5 + 10*7 + 5*2 + 15*5 = 375.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

u1 + v1 =2; u1 = 0, v1 = 2;

u1 + v2 =3; v2 = 3;

u1 +v3 = 2; v3 = 2;

u2 + v3 = 5; u2 =3;

u2 + v4 = 7; v4 = 4;

u3 + v4 = 2; u3 = -2;

u3 +v5 = 5; v5 =7;

Находим для небазисных клеток оценки с учетом значений потенциалов ui и vj:

Так как среди оценок имеются положительные, то план можно улучшить, осуществляя перевозки по замкнутому циклу. Начальная вершина цикла соответствует небазисной клетке с наибольшей положительной оценкой (). Таким образом перевозки осуществляем по следующему циклу x15 x35 x34 x24 x23 x13 x15.

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

2 10	3 20	2 10	8	1 10	50
3	1	5 30	7	4	30
4	4	3	2 15	5 5	20
10	20	40	15	15

Новый опорный план:

Проверим на вырожденность опорный план m+n-1=7. Опорный план не вырожден.

Стоимость полученного плана найдем умножив каждую перевозку на соответствующую стоимость:

F = 10*2 + 20*3 + 10*2 + 10*1 + 30*5 + 15*2 + 5*5 = 315.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

u1 + v1 =2; u1 = 0, v1 = 2;

u1 + v2 =3; v2 = 3;

u1 +v3 = 2; v3 = 2;

u1 +v5 = 1; v5 = 1;

u2 + v3 = 5; u2 = 3;

u3 + v5 = 5; u3 = 4;

u3 + v4 = 2; v4 = -2;

Находим для небазисных клеток оценки с учетом значений потенциалов ui и vj:

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

x22 x12 x13 x23 x22.

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

Таблица 12

2 10	3	2 30	8	1 10	50
3	1 20	5 10	7	4	30
4	4	3	2 15	5 5	20
10	20	40	15	15

Новый опорный план:

Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость:

F = 10*2 + 30*2 + 10*1 + 20*1 + 10*5 + 15*2 + 5*5 =215.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

u1 + v1 =2; u1 = 0, v1 = 2;

u1 + v3 =2; v3 = 2;

u1 +v5 = 1; v5 = 1;

u2 + v3 = 5; u2 = 3;

u2 + v2 = 1; v2 =-2;

u3 + v5 = 5; u3 = 4;

u3 +v4 = 2; v4 = -2.

Находим для небазисных клеток оценки с учетом значений потенциалов ui и vj:

Так как среди оценок имеются положительные, то план можно улучшить осуществляя перевозки по замкнутому циклу. Начальная вершина цикла соответствует небазисной клетке с наибольшей положительной оценкой (). Таким образом перевозки осуществляем по следующему циклу x33 x13 x15 x35 x33.

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

Таблица 13

2 10	3	2 25	8	1 15	50
3	1 20	5 10	8	4	30
4	4	3	2 15	5 0	20
10	20	40	15	15

Новый опорный план:

Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость:

F = 10*2 + 25*2 + 15*1 + 20*1 + 10*5 + 5*3 + 15*2 =200.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

u1 + v1 =2; u1 = 0, v1 = 2;

u1 + v3 =2; v3 = 2;

u1 +v5 = 5; v5 = 5;

u2 + v3 = 5; u2 = 3;

u2 + v2 = 5; v2 =-2;

u3 + v3 = 3; u3 = 1;

u3 +v4 = 2; v4 = 1.

Находим для небазисных клеток оценки с учетом значений потенциалов ui и vj:

Так как среди оценок имеются положительные, то план можно улучшить осуществляя перевозки по замкнутому циклу. Начальная вершина цикла соответствует небазисной клетке с наибольшей положительной оценкой (). Таким образом перевозки осуществляем по следующему циклу x21 x11 x13 x23 x21.

Полученные результаты представим в табл. 14. Таблица 14

2	3	2 35	8	1 15	50
3 10	1 20	5 0	7	4	30
4	4	3 5	2 15	5	20
10	20	40	15	15

Новый опорный план:

Стоимость полученного плана найдем, умножив каждую перевозку на соответствующую стоимость:

F = 35*2 + 15*1 + 10*3 + 20*1 + 0*5 + 5*3 + 15*2 =180.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

Находим значения потенциалов ui и vj, соответствующие базисным клеткам, принимая для удобства u1=0.

u1 + v3 =2; u1 = 0, v3 = 2;

u1 + v5 =1; v5 = 1;

u2 +v3 = 5; u2 = 3;

u2 + v1 = 3; v1 = 0;

u2 + v2 = 1; v2 =-2;

u3 + v3 = 3; u3 = 1;

u3 +v4 = 2; v4 = 1.

Находим для небазисных клеток оценки с учетом значений потенциалов ui и vj:

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

F* = 35*2 + 15*1 + 10*3 + 20*1 + 0*5 + 5*3 + 15*2 =180.

ЗАДАЧА 4

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

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

2х1 + х2 2;

х1 +2 х2 2;

х1, х2 0.

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

Составим матрицу D и рассмотрим ее определители:

D =; ?1= -1 < 0

Составим функцию Лагранжа.

Запишем условие Куна - Таккера:

Систему линейных неравенств перепишем в виде:

х1 - х2 + 21 +2 3

х2 - 2х1 - 1 -22 2

2х1 + х2 2

х1 + 2х2 2

Получим систему линейных неравенств, т. е. задача приведена к задаче линейного программирования. Используя дополнительные переменные v1, v2, w1, w2 приведем неравенства к равенствам.

х1 - х2 + 21 +2 - v1 = 3;

х2 - 2х1 - 1 - 22 + v2 = 2; (*)

2х1 + х2 + w1 = 2;

х1 + 2х2 + w2 = 2;

Дополним равенства условиями, которые представим в виде:

v1x1 = 0; v2x2 = 0; w11 = 0; w22 = 0. (**)

Найдем базисное дополнительное решение системы (*) с учетом (**). Для этого воспользуемся методом искусственного базиса, вводя искусственные переменные z1 и z2.

Получим:

F (x) = -Mz1 -M z2

2х1 - 2х2 + 21 - 2 - v1 + z1 = 2;

4х2 - 2х1 + 1 + 2 - v2 + z2 = 2;

2х1 + х2 + w1 = 4;

- х1 + х1 + w2 = 2;

Для нахождения решения графическим методом, построим линии уровня исходной функции F (x1, x2) и линии ограничения (ОДР) (рис. 3).

Рис. 4

На рис. 3 видно, что значения

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

Полученные результаты:

ЗАДАЧА 1:

ЗАДАЧА 2:

ЗАДАЧА 3:

, F* =180.

ЗАДАЧА 4:

СПИСОК ЛИТЕРАТУРЫ

Пичугин Е. Д. Методы оптимизации. Учеб. пособие для вузов. -Одесса, ОГПУ. 1998

Дегтярев Ю. И. Исследование операций: Учеб. для вузов ? М. : Высш. шк. 1986.

Зайченко Ю. П. Исследование операций: Учеб. для вузов ? К. : Вища шк., 1988.

Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и студентов ВТУЗов. - М. : ”Наука” 1981. -720 с.

Размещено на Allbest.ru