Материал: Методические указания для организации выполнения курсовой работы по курсу Высшая математика. Пантелеев И.Н

Смотрите также:

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

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

Вслучае А - решение единственное (точка А).

Вслучае B - бесконечное множество решений (отрезок [А,B]).

В	случае С -	решений	нет,	так	как	область допустимых
решений в направлении поиска решений не замкнута.
В	случае D –	решений	нет,	так	как	ограничения в задаче
несовместны.
				27


Алгоритм симплекс-метода
Замечание	№1. При решении задачи симплекс-методом
ограничения	на знак		переменных не		участвуют	ни в
подготовке задачи к решению, ни в самом счете.
Решение задачи симплекс методом включает два						этапа:
этап подготовки задачи к решению и этап вычислений.
Этап подготовки задачи к решению
1. Симплекс-метод		ищет		максимум	функции. Если
требуется найти минимум,			умножить целевую функцию на
(-1) и перейти к задаче поиска максимума.
2. Правые	части	ограничений		должны	быть 0.≥ Если

правая часть ограничения < 0, умножить его левую и правую

части

на (-1)

изменить

знак

ограничения

на

Переменная, которой соответствует в столбце максимальная

противоположный.

положительная

симплекс-разность,

вводится

базис.

3. Привести

задачу к

каноническому видуперейти

от

Соответствующий столбец пометим - Z.

задачи

ограничениями

типа

неравенств

задаче

БP

ограничениями типа равенств, вводя, если это необходимо,

3. Высчитать величины ri

по формуле: ri =

Z i

дополнительные

переменные. Ввести

дополнительные

Переменная,

которой

соответствует

строке

переменные в целевую функцию с коэффициентами равными 0.

минимальная

неотрицательная

величина

выводится из

4. Выписать

столбцы

коэффициентов

при

переменных в

базиса. Соответствующую

строку

пометим-

Элемент,

ограничениях. Если

среди

выписанных

столбцов

имеетсяm

(по числу ограничений) базисных

столбцов -

столбцов

стоящий на пересечении Z-столбца и Z -строки - разрешающий

единичной матрицы размерности m x m, перейти к п. 6.

элемент - R .

5. Если

нужное

число базисных столбцов не найдено

4. Построить новую таблицу, пересчитав предыдущую.

перейти к решению М-задачи:

П е р е с ч е т т а б л и ц ы

5.1 . дописать недостающие столбцы искусственно;

5.2. поставить

им

соответствие

искусственные

4.1. Заполнить

новой

таблице: строку

коэффициентов

переменные;

функции, столбец Б п

и столбец С i Б .

5.3. переписать

ограничения

с учетом

искусственных

4.2. Пересчитать

Z-строку,

содержащую

разрешающий

переменных;

элемент и записать в новую таблицу под тем же номером:

5.4. ввести искусственные переменные в целевую функцию

новая строка = старая строка / R.

с коэффициентами равными (-М) , где М - большое

Полученная строка - разрешающая.

положительное число.

4.3. Пересчитать все остальные строки таблицы и записать

6. Выписать

переменные

при

базисных

столбцахэти

их под теми же номерами в новую таблицу:

переменные базисные. Записать начальное базисное решение:

новая строка К= старая строка К −(разрешающая

базисные

переменные равны правым частям ограничений,

строка) * Коэффициент Пересчета,

которые они входят, все остальные переменные равны 0.

здесь

Коэффициент

Пересчета-

элемент,

стоящий на

пересечении строки К и Z-столбца в старой таблице.

Э т а п в ы ч и с л е н и й

5. Повторить

процедуру 2-4

до тех пор, пока

все

симплекс-

разности не станут < 0, тогда последнее базисное решение есть

Алгоритм

решение задачи.

Замечание №2. Если в процессе решения оказалось, что в

1. Составить таблицу №1.

базис вводится некоторая переменная(существует симплекс-

2. Выписать базисное решение. Вычислить симплекс-разности

разность >

0),

среди

величин r i

нет

ни

одной

для небазисных переменных по формуле:

неотрицательной, значит, задача не имеет решения вследствие

D j

= C j

- Ci Б × Aj

не замкнутости области допустимых решений.

	Замечание	№3.	Если	в	таблице, соответствующей		следовательно	задача	имеет	бесконечное множество
решению задачи, в строке симплекс-разностей содержится0							решений на отрезке [В, С], здесь B = (3, 2), C = (6, 0).
больше, чем число ограничений в задаче, значит, задача имеет
бесконечное множество решений, одно из которых найдено.
	Замечание №4. Если при решении М-задачи найдено
решение (все симплекс-разности < 0), но в составе базисных
переменных осталась искусственная переменная не равная0,
то	исходная		задача	не	имеет	решения	вследствие
несовместности ограничений.
	Пример 1. Дано:
	f (x) = 2x1 + 3x2 ® max

2x1 + 3x2 £12

-2x1 + 6x2 £ 6 x1 ³ 0, x2 ³ 0

Решить задачу графически и симплекс-методом.

Г р а ф и ч е с к о е р е ш е н и е з а д а ч и

1. Множество допустимых решений (МДР), определяемое ограничениями, выделено на чертеже штриховкой.

2.	æ 2	ö	, на чертеже это вектор с
2.	Градиент функции: Df (x) = ç	÷	, на чертеже это вектор с
	è 3	ø
началом в точке (0, 0) и концом в точке (2, 3).
3.	Уравнение линии уровня функции:
	f (x) = C;		Р е ш е н и е з а д а ч и с и м п л е к с м е т о д о м
			Р е ш е н и е з а д а ч и с и м п л е к с м е т о д о м

		2x1 + 3x2	= C.
Уравнение линии уровня функции в точке (0, 0):
		2x1 + 3x2	= 0 .
На	чертеже	линия	уровня	функциипрямая
перпендикулярная градиенту.
4. Для поиска максимума перемещаем линию уровня						в
направлении градиента до последнего				касания	с	МДР,
очевидно,	что касание	произойдет на		отрезке	[В, С],
		31

Подготовка задачи к решению симплекс-методом

1.Выполнено (ищем максимум).

2.Выполнено (правые части ограничений неотрицательны).

3.Приведем задачу к каноническому виду, для этого введем в

каждое ограничение неотрицательную переменную:

Замечание. Если ограничение имеет знак«<», то вводится переменная со знаком «+», если же ограничение имеет знак «>», то вводится переменная со знаком«-», если исходное ограничение имеет знак «=», то дополнительные переменные не вводятся.

2 x1 + 3 x2 + x3 = 1 2

- 2 x1 + 6 x 2 + x 4 = 6

x3 , x4 ³ 0 - д о п о л н и т е л ьн ы е п е р е м е н н ы е

( д о п о л н я ю т н ер а в е н с т в а д о р а в е н св ).

4. Выпишем столбцы коэффициентов при переменных в ограничениях:

	x1		x2		x3		x4
æ 2 ö			æ 3 ö		æ1 ö		æ 0 ö
ç	-2	÷	ç	÷	ç	÷	ç	÷
è	-2	ø	è 6	ø	è0	ø	è1	ø

ÝÝ

Среди

столбцов

имеется

два

столбца

единичной матрицы

размерности (2 х 2), они отмечены символом Ý , значит базис есть.

5. Начальное базисное решение: х3,

х4 - базисные переменные

(переменные

отмечены

символом Ý ), эти

переменные равны

правым частям ограничений, в которых они находятся:

х 3 = 12,

х4

= 6. Остальные переменные x1 = x2 = 0.

Э т а п в ы ч и с л е н и й

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

Коэффициенты

функции

Таблица 1

C j

C i

Б п

Б р

x 1

x 2

x 3

x 4

x 3

x 4

-2

∆

Коэффициенты	Правые части	Столбцы
Коэффициенты	Правые части	коэффициентов
функции при	ограничений –	при переменных
базисных	начальное базисное	в ограничениях
переменных	решение	в ограничениях
переменных	решение
	33

Базисное решение соответствующее табл. №1:

x1 = 0 x2 = 0 x3 = 12 x4 = 6

Оно соответствует в исходных переменных точке 0(0,0).

Вычислим симплекс-разности для небазисных переменных:

D1 = 2 -	æ0		ö	æ2 ö
D1 = 2 -	ç	0	÷ g	ç	÷	= 2 - (0 + 0) = 2
	è	0	ø	è	-2 ø

Коэффициенты

Столбец

коэффициентов

функции при

коэффициентов

при переменной

переменной x 1

С i Б

x 1

æ0 ö

æ3 ö

- (0

+ 0) = 3

= 3 -ç ÷

×ç ÷ = 3

è0 ø

è6 ø

Для базисных переменных симплекс разности равны 0.

Таблица 1

C j

C i

Б п

Б р

x 1

x 2

x 3

x 4

r i

x 3

x 4

-2

∆

Z-столбец

Т.к. ∆2 является максимальной положительной величиной в строке симплекс разностей, то в базис вводится переменная х2. Соответствующий этой переменной столбец - Z-столбец. Вычислим величины r i , как отношения элементов столбца Бр

к элементам Z-столбца:

r =	12	= 4 r =	6	= 1.
r =		= 4 r =		= 1.
1	3	2	6
	3		6
		34

									Таблица 1
			2	3		0	0	C j
C i	Б п	Б р	x 1		x 2	x 3	x 4	r i
0	x 3	12	2		3	1	0	4
0	x 4	6	-2	6		0	1	1	Z-строка
		∆	2		3	0	0

Z-столбец

Коэффициент	Разрешающий
пересчета	элемент
Из базиса выводится	переменнаях 4 , т.к. ей по строке

соответствует минимальная неотрицательная величинаr2, соответствующая ей строка - Z-строка.

На пересечении Z-столбца и Z-строки находится разрешающий элемент R = 6.

Осуществим пересчет таблицы:

•запишем коэффициенты функции в верхнюю строку новой таблицы 2;

•запишем в новую таблицу 2 новые базисные переменные

х2 и х3;

• запишем коэффициенты функции при новых базисных

переменных в первый столбец таблицы 2								Таблица 2
								Таблица 2
				2	3	0	0	C j
	C i	Б п	Б р	x 1	x 2	x 3	x 4	ri
	0	x 3
	3	x 2
			∆

• пересчитаем Z-строку:			разделим Z-строку на
разрешающий элемент,			результат запишем в таблицу №2
на своё место - получится разрешающая строка;
Z-строка	(		6	- 2	6	0	1 ) / 6
Результат		1		-1/ 3	1	0	1/ 6

								Таблица 2
			2	3		0	0	C j
C i	Б п	Б р	x 1	x 2		x 3	x 4	r i
0	x 3
3	x 2	1	-1/3	1		0	1/6
		∆
					Разрешающая строка

• пересчитаем оставшуюся строку: умножим разрешающую строку на коэффициент пересчета - 1-й элемент Z-столбца из табл. 1 - это число 3, и вычтем из 1-й строки табл. 1, результат запишем в таблицу №2 на свое место:

									Таблица 2
				2	3		0	0	C j
	C i	Б п	Б р	x 1		x 2	x 3	x 4	r i
	0	x 3	9	3		0	1	-1/2
	3	x 2	1	-1/3	1		0	1/6
			∆
Базисное решение, соответствующее табл. 2:
x1 = 0		x2 = 1		x3 = 9			x4 = 0

Оно соответствует в исходных переменных точке А = (0,1).

Далее проводим расчет по аналогии.

Вычислим симплекс-разности для небазисных переменных:

Источник: https://studfile.net/preview/16565055/

Строка 1 табл.1

Разрешающая строка×(3)

!Контрольная работа (задание)
'Свадьба'. Керамика
«Предмет, метод предпринимательского права и принципы предпринимательского права» (Понятие предмета и метода российского предпринимательского права)
«Українська література в першій половині ХХ століття»
0303_Болкунов_ВО_ЛР1
1
1 анализ организации работ в цехе то2 9 1 Характеристика локомотивного депо Хабаровск ii 9
1 Верно Баллов 1,00 из 1,00 Отметить вопрос Текст вопроса Уточнение правильности выполнения деталей техники, исправление ошибок является целью этапа Выберите
1 Понятие
1_MicroBio_возбудители Кишечных инфекций