Алгоритм пересчета симплексной таблицы

 

Шаг 1. Выбрать главный столбец симплексной таблицы. Для минимизирующей функции он находится как максимальное среди положительных элементов , стоящих в последней строке таблицы:

(3.10)

Для максимизирующей функции он находится как минимальное среди отрицательных элементов , стоящих в последней строке таблицы:

(3.11)

Шаг 2. Выбрать главную строку. Для этого произвести построчное деление столбца свободных членов на главный столбец (в делении участвуют только положительные элементы). Главная строка находится как минимальное из найденных частных:

(3.12)

Шаг 3. В новой симплексной таблице на место базисной неизвестной по главной строке поставить переменную по главному столбцу.

Шаг 4. Рассчитать элементы новой симплексной таблицы, стоящие на месте главной строки:

, (3.13)

(3.14)

Шаг 5. Рассчитать остальные элементы для новой симплексной таблицы:

, , (3.15)

, , (3.16)

, (3.17)

. (3.18)

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

Процесс перехода к новым решениям продолжается до тех пор, пока не будет получено оптимальное решение.

Пример решения задачи ЛП симплексным методом

Пример №3.1.

Минимизировать

, (1*)

при условиях:

(2*)

и

(3*)

Решение.

Шаг1.

Данную задачу не требуется приводить к каноническому виду, т.к. система ограничений содержит только равенства.

Матрица условий-ограничений для данной задачи будет иметь вид:

m=2 n=5.

Для удобства решения исходные данные задачи следует представить в виде:

.

Шаг 2.

В качестве базисных неизвестных выбираются x₁ и x₂, т.к. каждая из них входит только в одно условие–ограничение с коэффициентом +1 и в остальные условия–ограничения с коэффициентом 0.

Одним из допустимых решений задачи ЛП (1*) – (3*) является базисное неотрицательное решение системы (2*)

Ему соответствует значение целевой функции, равное

.

Шаг 3.

определяется по формуле (3.7).

;

;

;

;

.

При использовании формулы вычисления имеют вид:

;

;

;

;

.

Первая симплексная таблица имеет вид:

1 симплексная таблица

	Базис	B			-9
x1	x2	x3	x4	x5
	x1					–6
	x2				–7
		87–F			-25	–30

Шаг 4.

В последней строке симплексной таблицы есть положительный коэффициент при свободной неизвестной x₅. При этой неизвестной в системе уравнений есть положительные коэффициенты. Следовательно, полученное базисное решение не является оптимальным и согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Шаг 5.

Выбор главного столбца симплексной таблицы:

,

s=5, главный столбец x₅.

Выбор главной строки:

,

r=1, главная строка x₁.

Неизвестная x₅ становится базисной, x₁— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы:

1) новые элементы главной строки:

, , , , ;

:

2) остальные новые элементы таблицы:

, , , , ; ;

, , , , ;

.

Вторая симплексная таблица имеет вид:

2 симплексная таблица

Базис	B	x1	x2	x3	x4	x5
x5		1/3			–2
x2		-1/3		–8
	30–F	-19/3		-44

В последней строке симплексной таблицы есть положительный коэффициент при свободной неизвестной x₄, и при этой неизвестной в системе уравнений есть один положительный коэффициент. Следовательно, полученное базисное решение не является оптимальным и согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Шаг 6.

Процесс перехода к новым и новым решениям продолжается до тех пор, пока не будет получено оптимальное решение.

Выбор главного столбца симплексной таблицы:

,

s=4, главный столбец x₄.

Выбор главной строки:

,

r=4, главная строка x₄.

Неизвестная x₄ становится базисной, x₂— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы:

1) новые элементы главной строки:

, , , , ;

;

2) остальные новые элементы таблицы:

, , , , ; ;

, , , , ;

.

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

3 симплексная таблица

Базис	B	x1	x2	x3	x4	x5
x5	9/2	1/6	1/2	-3
x4	3/4	-1/12	1/4	–2
	24–F	-17/3	-2	-28

В третьей симплексной таблице среди элементов последней строки нет ни одного положительного. Поэтому данное базисное решение является оптимальным.

 

Ответ.

Оптимальное базисное решение:

Наименьшее значение линейной формы:

.

Пример №3.2.

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

.

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

Решение.

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

найти производственную программу

(x₁, x₂, x₃, x₄)

максимизирующую прибыль

при ограничениях по ресурсам

и по смыслу задачи , , , .

Система ограничений состоит из неравенств. Следовательно, ее необходимо привести к каноническому виду при помощи дополнительных неотрицательных неизвестных x₅, x₆, x₇:

.

Дополнительные переменные x₅, x₆, x₇ имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений, удовлетворяющих условию неотрицательности

, , , , , ,

надо найти то решение, при котором целевая функция примет наибольшее значение.

Базисными неизвестными являются дополнительные переменные x₅, x₆, x₇.

Одним из допустимых решений задачи является базисное неотрицательное решение системы ограничений

Ему соответствует значение целевой функции, равное

.

Для составления первой симплексной таблицы необходимо вычислить :

– коэффициенты при базисных неизвестных;

;

;

;

;

;

;

.

1 симплексная таблица

	Базис	B
x1	x2	x3	x4	x5	x6	x7
	x5
	x6
	x7
		0–F	-40	-20	-29	-54

В последней строке симплексной таблицы есть отрицательные коэффициенты при свободных неизвестных x₁, x₂, x₃ и x₄. При любой из этих неизвестных в системе уравнений есть хотя бы один положительный коэффициент. Следовательно, согласно правилу №3 необходимо искать оптимальное решение путем пересчета симплексной таблицы.

Выбор главного столбца:

,

s=4, главный столбец x₄.

Выбор главной строки:

Т.к. две дроби равны и являются минимальными, то можно взять любую из них. Пусть r=2, главная строка x₆.

Неизвестная x₄ становится базисной, x₆— свободной.

Расчет новой симплексной таблицы производится в соответствии с формулами (3.13 – 3.18) алгоритма пересчета симплексной таблицы. Вторая симплексная таблица имеет вид:

2 симплексная таблица

Базис	B	x1	x2	x3	x4	x5	x6	x7
x5	55/2	-1	-13/2				-3/2
x4	49/2		3/2	2/3			1/6
x7	1/2	-2	-17/2				-3/2
	1323–F

 

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

Ответ.

Используя план производства , предприятие получает наибольшую прибыль, равную .

При этом остаток ресурса первого вида , второго вида x₆ = 0, третьего вида .

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. II. Алгоритм процесса кибернетического моделирования.
2. Алгоритм 1.1. Расчет описательных статистик
3. Алгоритм 2.1. Расчет внутригрупповых дисперсий результативного признака
4. Алгоритм 3. Снятие заливки области построения
5. Алгоритм Data Encryption Stantart (DES).
6. Алгоритм «сдвиг-свертка» для грамматики операторного предшествования
7. АЛГОРИТМ АВАРИЙНОЙ И ЭКСТРЕННОЙ ОСТАНОВКИ 1 И 2 СТУПЕНИ КОМПРИМИРОВАНИЯ ДКС, БПТПиИГ
8. Алгоритм анализа переключательной схемы
9. Алгоритм банкира для несколько видов ресурсов
10. Алгоритм ВСК БРЗУ (упрощенный).
11. Алгоритм выполнения курсового проекта
12. Алгоритм вычисления кодов Шеннона — Фано