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

РефератПомощь в написанииУзнать стоимостьмоей работы

Из последней системы ограничений можно выделить базисные переменные y1, y2, y3,y4,y5. Решение первого варианта задачи линейного программирования симплекс методом. Принимает максимальное значение, при условии следующих ограничений: Теперь мы можем сформировать начальную симплекс-таблицу. Найти значения переменных x1… x2, при которых функция: Оптимальное значение функции S (x)= 36.666 666 666 667… Читать ещё >

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

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

1. Привести задачу к каноническому виду.
2. Найти начальное опорное решение с «единичным базисом» (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости Привести системы ограничений).
3. Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода.
4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается.
5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

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

Найти значения переменных x1… x2, при которых функция:


S =.		x₁			x₂

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


x₁-x₂?5.	(1).
x₁?10.	(2).
3x₁+4x₂?60.	(3).
— 5x₁+2x₂?10.	(4).
2x₁+x₂?10.	(5).
x₁?0.
x₂?0.

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4, 5 неотрицательные балансовые переменные y1, y2, y3, y4, y5.


x₁-x₂₊y₁₌5.	(1).
x₁+y₂=10.	(2).
3x₁+4x₂₊y₃=60.	(3).
— 5x₁+2x₂+y₄=10.	(4).
2x₁+x₂+y₅=10.	(5).
x₁, x₂, s₁, s₂, s₃, s₄, s₅? 0.

Ищем в системе ограничений базисные переменные.

Из последней системы ограничений можно выделить базисные переменные y1, y2,y3,y4,y5.

Теперь мы можем сформировать начальную симплекс-таблицу.

Начальная симплекс-таблица.


БП.	x₁	x₂	y₁	y₂	y₃	y₄	y₅	Решение.	Отношение.
y₁		— 1.							5/1=5.
y₂									10/1=10.
y₃									60/3=20.
y₄	— 5.								-;
y₅									10/2=5.
S.									-;

Итерация 1.


БП.	x₁	x₂	y₁	y₂	y₃	y₄	y₅	Решение.	Отношение.
y₁		— 1.5.					— 0.5.		-;
y₂		— 0.5.					— 0.5.		-;
y₃		2.5.					— 1.5.		45/2.5=18.
y₄		4.5.					2.5.		35/4.5=7.7 777 777 777 778.
x₁		0.5.					0.5.		5/0.5=10.
S.		1.5.					— 2.5.	— 25.	-;

Итерация 2.


БП.	x₁	x₂	y₁	y₂	y₃	y₄	y₅	Решение.	Отношение.
y₁						0.33 333 333 333 333.	0.33 333 333 333 333.	11.666 666 666 667.	-;
y₂						0.11 111 111 111 111.	— 0.22 222 222 222 222.	8.8 888 888 888 889.	-;
y₃						— 0.55 555 555 555 556.	— 2.8 888 888 888 889.	25.555 555 555 556.	-;
x₂						0.22 222 222 222 222.	0.55 555 555 555 556.	7.7 777 777 777 778.	-;
x₁						— 0.11 111 111 111 111.	0.22 222 222 222 222.	1.1 111 111 111 111.	-;
S.						— 0.33 333 333 333 333.	— 3.3 333 333 333 333.	— 36.666 666 666 667.	-;

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Оптимальное значение функции S (x)= 36.666 666 666 667? 36.7.

Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.

Оптимальное значение функции S (x)= 36.666 666 666 667? 36.7.

достигается в точке с координатами:


x₁=.	1.1 111 111 111 111.
x₂=.	7.7 777 777 777 778.
y₁=.	11.666 666 666 667.
y₂=.	8.8 888 888 888 889.
y₃=.	25.555 555 555 556.
y₄=.
y₅=.

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

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

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

Синергетический анализ сложноорганизованных систем

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

Реферат