Симплекс метод решения задачи линейного программирования

ЗадачаПомощь в написанииУзнать стоимостьмоей работы

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец. Оценки (?j) вычисляются по формуле, где — коэффициент из первой строки таблицы. На пересечении направляющей строки и столбца находится направляющий элемент. Максимальное значение функции F max =400 достигается в точке с координатами: Задача № 1 (Симплекс метод решения задачи линейного программирования.) В строке… Читать ещё >

Симплекс метод решения задачи линейного программирования (реферат, курсовая, диплом, контрольная)

Задача № 1 (Симплекс метод решения задачи линейного программирования.)

Найти F _max = 9x₁+ 10x₂ + 16x₃_, при ограничениях:

Запишем задачу в каноническом виде:

F=9x₁+ 10x₂ + 16x₃ > max

Заполним начальную таблицу:

Таблица 0.


						Отношение, и
i		Базис



	?j		— 9	— 10	— 16
	Zj

Zj вычисляется по формуле

Оценки (?j) вычисляются по формуле, где — коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «и», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент.

Заполняем новую таблицу

Таблица 1.


				Отношение, и
i		Базис


				;
	?j		— 2
	Zj

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

Столбец становится базисным, то есть единичным.

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «и»

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

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.

Таблица 2.


				Отношение, и
i		Базис
				;	______
			;		______
				;	______
	?j
	Zj

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

Ответ:

Максимальное значение функции F _max =400 достигается в точке с координатами:

=20

=96

Задача № 2 (Метод Литтла) Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.

Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

и т. д.)



	18,87	49,48	51,86	80,51	97,42
18,87		32,06	34,48	65,15	84,01
49,48	32,06		31,76	61,19	83,20
51,86	34,48	31,76		32,14	53,15
80,51	65,15	61,19	32,14		22,14
97,42	84,01	83,20	53,15	22,14

Предположим что кратчайший путь будет следующим:

т.1> т.2> т.3> т.4> т.5> т.6>т.1 и составит

Решение: Первый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам

(в строке вычитаем из каждого элемента минимальный, затем в столбцах)



	18,87	49,48	51,86	80,51	97,42	18,87
18,87		32,06	34,48	65,15	84,01	18,87
49,48	32,06		31,76	61,19	83,20	31,76
51,86	34,48	31,76		32,14	53,15	31,76
80,51	65,15	61,19	32,14		22,14	22,14
97,42	84,01	83,20	53,15	22,14		22,14



		30,61	32,99	61,64	78,55
		13,19	15,61	46,28	65,14
17,72	0,30			29,43	51,44
20,10	2,72			0,38	21,39
58,37	43,01	39,05	10,00
75,28	61,87	61,06	31,01



		30,61	32,99	61,64	78,55
		13,19	15,61	46,28	65,14
17,72	0,30			29,43	51,44
20,10	2,72			0,38	21,39
58,37	43,01	39,05	10,00
75,28	61,87	61,06	31,01

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (5 — 6)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6−5 ставим ?).



		30,61	32,99	61,64
		13,19	15,61	46,28
17,72	0,30			29,43
20,10	2,72			0,38
75,28	61,87	61,06	31,01

Далее повторяем шаги 1 — 4, пока не дойдем до одной клетки.

Второй этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



		30,61	32,99	61,64
		13,19	15,61	46,28
17,72	0,30			29,43
20,10	2,72			0,38
75,28	61,87	61,06	31,01
				0,38



		30,61	32,99	61,26
		13,19	15,61	45,90
17,72	0,30			29,05
20,10	2,72
75,28	61,87	61,06	31,01

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (1 — 2)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 2 — 1 ставим ?).



	13,19	15,61	45,90
17,72			29,05
20,10
75,28	61,06	31,01

Третий этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



	13,19	15,61	45,90
17,72			29,05
20,10
75,28	61,06	31,01
17,72



	13,19	15,61	45,90	13,19
			29,05
2,38
57,56	61,06	31,01		31,01



		2,42	32,71
			29,05
2,38
26,55	30,05

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (4 — 5)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 — 4 ставим ?).



		2,42

26,55	30,05

Четвертый этап.

Шаг 1. Приведем матрицу расстояний по строкам и столбцам.



		2,42

26,55	30,05		26,55



			2,42

		3,50

Шаг 2. Определим оценки нулевых клеток:

Шаг 3. Вычеркиваем клетку с максимальной оценкой. Включаем данную клетку в путь обхода. (3 — 4)

Шаг 4. Переписываем матрицу расстояний, накладывая запрет на одну из клеток для исключения преждевременного замыкания контура (в клетку 6 — 3 ставим ?).

Пятый этап.

Остались не задействованными связи 2 — 3 и 6 — 1.

В результате получаем следующую цепочку:

1> 2> 3 > 4> 5> 6 >1

Длина пути составляет:

L=18,87+32,06+31,76+32,14+22,14+97,42=234,39

это и есть кратчайший путь.

Показать весь текст

Заполнить форму текущей работой

Другие работы

Сравнительная характеристика браузеров

Давайте отмотаем время назад и посмотрим на то, что в настоящий момент представляет собой Интернет. Население Земли приближается к семи миллиардам человек, а в Сеть выходят около двух. В то же время США и ряд европейских стран являются «насыщенными» рынками. То есть рост количества пользователей Сети там уже остановился. Двигателями роста аудитории интернета являются другие регионы — Азия, Африка…

Реферат