по Математическому моделированию (стр. 2 из 8)

Решение.

Для начала попытаемся выразить одни переменные системы через определенный набор других переменных. С этой целью будем рассматривать расширенную матрицу системы ограничений и путем элементарных преобразований этой матрицы, выделим в ней единичную подматрицу :

Воспользуемся последней расширенной матрицей и выразимпеременные

,

и

через оставшиеся переменные

и

. Помня, что

, получаем новые ограничения :

Подставив эти значения вместо переменных

,

и

в исходную задачу, для целевой функции получим:

Итак, преобразовав полученные неравенства и целевую функцию, имеем задачу, эквивалентную исходной с ограничениями « = » , но уже с ограничениями «

»:

min,

5. Решить задачу линейного программирования симплекс-методом.

Решение.

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

Все свободные члены системы ограничений неотрицательны, значит, выполнено одно из необходимых условий применения симплекс-метода. Осталось все условия системы представить в виде уравнений. Для этого к левой части 1-го неравенства системы ограничений прибавляем неотрицательную переменную

, к левой части 2-го неравенства прибавляем неотрицательную переменную

, а к левой части 3-го - неотрицательную переменную

, тем самым мы преобразуем неравенства в равенства:

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

Переменная

входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом 0, т.е.

- базисная переменная. Аналогично переменные

и

являются базисными. Остальные переменные являются свободными. Приравняв свободные переменные к 0 в системе ограничений, получаем опорное решение:

= ( 0 , 0 , 1 , 3 , 2 ).

Теперь непосредственно составим таблицу:

Базисныепеременные						Свободные переменные	Отношение
	2	-1	1	0	0	1	-
	1	3	0	1	0	3	1
	1	-2	0	0	1	2	-
J(x)	-2	-3	0	0	0	0	-

В качестве ведущего выступает 2-ой столбец, поскольку -3 - наименьший элемент в строкеJ(x). За ведущую строку принимаем строку 2, т. к. отношение свободного члена к соответствующему элементу выбранного столбца для 2-ой строки является наименьшим из неотрицательных. Разделим элементы 2-ой строки на 3, чтобы получить в качестве ведущего элемента 1:

Базисныепеременные						Свободные переменные	Отношение
	2	-1	1	0	0	1	-
		1	0		0	1	1
	1	-2	0	0	1	2	-
J(x)	-2	-3	0	0	0	0	-

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

От элементов строки 1 отнимаем соответствующие элементы строки 2, умноженные на -1.

От элементов строки 3 отнимаем соответствующие элементы строки 2, умноженные на -2.

От элементов строки J(x) отнимаем соответствующие элементы строки 2, умноженные на -3. В результате имеем:

Базисныепеременные						Свободные переменные	Отношение
		0	1		0	2
		1	0		0	1	3
		0	0		1	4
J(x)	-	0	0	1	0	3	-

За ведущий столбец выберем столбец 1 ( по тому же правилу) , а за ведущую строку - строку 1. Разделим элементы 1-ой строки на

: