Васильев е. П. Экономико математические методы и модели часть I

Скачать 1.03 Mb.

Название	Васильев е. П. Экономико математические методы и модели часть I
страница	5/19
Дата публикации	02.07.2015
Размер	1.03 Mb.
Тип	Учебное пособие

100-bal.ru > Экономика > Учебное пособие

1 2 3 4 5 6 7 8 9 ... 19

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

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

3.1.Метод Жордана – Гаусса решение систем линейных уравнений

Метод последовательных исключений, или Жордана- Гаусса представляет собой удобный вычислительный алгоритм, построенный на последовательном применении эквивалентных преобразований системы линейных уравнений, которые приводят к равносильной системе.

Рассмотрим систему m уравнений с n неизвестными:

Алгоритм метода Жордана - Гаусса:

Все коэффициенты системы и свободные члены (элементы расширенной матрицы системы) записывают в таблицу

Выбирают ведущий элемент a_ks0 (k=1,2,...,m; s=1,2,...,n) ,

где k- тую строку называют ведущей, s- тый столбец - ведущим.

Все элементы ведущей строки пересчитывают по формуле:

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

В ведущем столбце элементы записывают нулями, кроме ведущего.

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

,

полагая главной диагональю ту, где находится ведущий элемент:

и полученный результат всегда делится на ведущий элемент (см. пример 1).

Итак, для любого элемента

таблицы получим:

Следующая итерация проводится над элементами полученной таблицы. Все преобразования проводят до тех пор, пока система не будет приведена к единичному базису.

Систему r- уравнений, в которой столбцы коэффициентов при r неизвестных являются единичными векторами: e₁=(1,0,. . . ,0), e₂=(0,1,. . .,0), e_r=(0,0,. . .,1) называют системой уравнений, приведенной к единичному базису:

Очевидно, ранг системы равен r.

Выразив базисные переменные x₁,x₂, . . . ,x_r

через свободные x_r₊₁, x_r₊₂, .. . , x_n, получим общее решение системы линейных уравнений:

Замечания:

Если число r базисных неизвестных равно n- числу неизвестных системы, то система имеет единственное решение:

X=(

,. . .,

)

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

Если rобщее решение.
Если в общем решении неопределенной системы линейных уравнений свободным неизвестным придать нулевые значения, то полученное частное решение X=(b₁₀; b₂₀; . . .; b_r₀; 0; 0; . . .; 0), называется базисным.

Неотрицательные базисные решения системы называются опорными.

Базисное решение не единственно ,так как выбор ведущего элемента произволен. Система m уравнений с n неизвестными, у которой ранг (число базисных переменных) равен r, может иметь различных базисных решений не более, чем

Пример 7. Найти общее решение, а также все базисные и опорные решения следующей системы линейных уравнений:

Решение.

Согласно алгоритму метода Жордана - Гаусса все преобразования выполним в следующей таблице:

Базис	х₁		х₂	х₃	х₄	а_i0
х₁	1		-2	0	1	-3	ведущая строка
	3		-1	-2	0	1
	2		1	-2	-1	4
	1		3	-2	-2	7
I итерация
х₁	1		-2	0	1	-3
х₂	0		5	-2	-3	10	ведущая строка
	0		5	-2	-3	10
	0		5	-2	-3	10
II итерация
х₁		1	0	-4/5	-1/5	1
х₂		0	1	-2/5	-3/5	2
		0	0	0	0	0
		0	0	0	0	0

Выбран ведущий элемент а₁₁=1 в первой таблице, составленной по условию задачи.

I итерация:

Вторую таблицу начинают заполнять с элементов ведущей строки (она не изменилась)
В первом столбце записывают нули, кроме а₁₁=1.
а₁₃=0, следовательно, третий столбец не изменится.
Вычисление остальных элементов производят по формуле « определителя второго порядка »:

После окончания I итерации получаем в первом столбце (1,0,0,0) и базисную переменную х₁.

II итерация:

Выбран в качестве ведущего элемента а₂₂=5.
Элементы ведущей строки делят на 5.
Во втором столбце записывают нули, кроме а₂₂=1
Вычисление остальных элементов производят по формуле «определителя второго порядка». После итерации I получили три совпадающих строки, откуда следует, что два уравнения «лишние». При выполнении итерации II эти строки превратились в нулевые строки. В результате получаем два уравнения (ранг r=2), которые разрешены относительно базисных переменных х₁ и х₂.

Таким образом, данная система совместна и не определена, ее общее решение имеет вид:

Частное решение Х=(1,2,0,0) - базисное решение. Всего базисных решений будет шесть, так как

.

Чтобы найти остальные базисные решения, проводим «замещение» одной базисной переменной на другую, до тех пор пока не найдем все базисные решения системы. Следует при этом следить, чтобы на какой-то итерации не повторялся уже использованный ранее базис.

Базис	х₁	х₂	х₃	х₄	b_i₀	Базисные решения
x₁	1	0	-4/5	-1/5	1	(1,2,0,0)
x₂	0	1	-2/5	-3/5	2
I итерация
x₃	-5/4	0	1	1/4	-5/4	(0,3/2,-5/4,0)
x₂	-1/2	1	0	-1/2	3/2
II итерация
x₃	0	-5/2	1	3/2	-5	(-3,0,-5,0)
x₁	1	-2	0	1	-3

III итерация

x₄	0	-5/3	2/3	1	-10/3	(1/3,0,0,-10/3)
x₁	1	-1/3	-2/3	0	1/3
IV итерация
x₄	-5	0	4	1	-5	(0,-1,0,-5)
x₂	-3	1	2	0	-1
V итерация
x₄	1	-2	0	1	-3	(0,0,-1/2,-3)
x₃	-3/2	1/2	1	0	-1/2

Неотрицательное базисное решение системы линейных уравнений (1,2,0,0), оно и будет опорным.

1 2 3 4 5 6 7 8 9 ... 19

Похожие:

	Методические рекомендации по изучению дисциплины «экономико-математические... Методические рекомендации по изучению дисциплины «экономико-математические методы и модели»		Фгбоу впо «сгэу» от 09. 11. 2012г. № Решение ученого совета Самарского... «Математическое моделирование», «Математические модели в финансовых операциях», «Методы оптимизации», «Экономико-математические методы...
	Математические методы и модели Габрин К. Э., Математические методы и модели: Семестровое задание и методические рекомендации к решению задач. – Челябинск: Издательство...		Программа дисциплины «Экономико-математические методы и модели в... ...
	Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования		Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования
	Методические указания по выполнению реферата по учебной дисциплине... Государственное образовательное учреждение высшего профессионального образования		Экономико-математические методы и модели оценки эффективности реализации... И наступил тот месяц, и пришел тот день, и настал тот час, и свершилось событие, в которое многие верили…
	Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования... Горюшкин А. А., Хуторецкий А. Б. Математические модели и методы исследования операций: курс лекций: Учеб пос. Новосиб национ иссл...		Программа дисциплины «Экономико-математические методы и модели в... ...
	План чтения лекции по учебной дисциплине «Математические методы» Раздел №2 Учебные и воспитательные цели: изучить основные виды задач линейного программирования, их математические модели		Тема: «Математические расчеты семейного бюджета» Математическая экономика – теоретическая и прикладная наука, предметом которой являются математические модели экономических объектов...
	Методические рекомендации для студентов по изучению дисциплины «стахование... Знания в области страхования необходимы для успешного прохождения производственной практики и освоения дисциплин Экономико-математические...		Рабочая программа дисциплины «Экономико-математические методы в дорожном строительстве» Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
	Опыт использования учебно-методического интернет-ресурса в преподавании... Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины 28		Рабочая программа дисциплины «Экономико-математические методы в стратегическом управлении» Дисциплина является предшествующей для следующих дисциплин: «Корпоративные информационные системы», «Компьютерные технологии в управлении»,...

Школьные материалы