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

В исходной системе преобразуем все знаки на .

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

Преобразовав систему получим:

Составим симплекс таблицу и найдем опорное решение задачи.

Проводим анализ столбца свободных членов (СЧ). Если все свободные члены являются положительными, то решение является опорным.

В таблице 1 в столбце свободных членов есть отрицательное число -3, значит опорное решение не получено. Проанализируем коэффициенты при неизвестных переменных в соответствующей строке и выберем за разрешающий тот столбец, где находится максимальный по модулю отрицательный коэффициент, то есть столбец x₁, который обозначим k.

Таблица 1

БП	СЧ	СП	α
x1	x2
x3				10/3
x4	-3	-3	-1	r 1
x5				5/2
x6
L		k -5	-4

 

 

Разрешающая строка определяется по дополнительному соотношению ,

где S_i0 – свободный член i-ой строки; S_ik – коэффициент разрешающего столбца.

В качестве разрешающей выбирается та строка, которая имеет минимальное положительное значение a, то есть строка х₄. Разрешающую строку обозначаем как r.

На пересечении разрешающей строки и столбца получаем разрешающий элемент S_rk=-3. Для таблицы 2 разрешающую строку х₄ выводим из базиса, а разрешающий столбец х₁ вводим в базис.

Производим пересчет симплексной таблицы:

- для разрешающего элемента

;

- для разрешающей строки

; ;

- для разрешающего столбца

; ;

; ;

- для всех остальных элементов

; ;

; ;

; ;

; ;

Таблица 2

 

БП	СЧ	СП	α
x4	x2
x3
x1		-1/3	1/3
x5		2/3	1/3
x6		1/3	5/3	r 12/5
L		-5/3	k -7/3

 

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

Определяем оптимальное решение, для этого проводим анализ строки целевой функции. Если все элементы этой строки являются положительными, а целевая функция стремится к максимуму, то решение является оптимальным.

В таблице 2 в стоке целевой функции есть отрицательные значения, выбираем за разрешающий столбец, где находится максимальный по модулю отрицательный коэффициент, то есть столбец x₂. Разрешающая строка определяется аналогично опорному решению. За разрешающую принимается строка, в которой имеется минимальное положительное α, то есть строка x_6.

На пересечении разрешающей строки и столбца получаем разрешающий элемент . Для таблицы 3 разрешающую строку х₆ выводим из базиса, а разрешающий столбец х₂ вводим в базис.

Производим пересчет симплексной таблицы:

- для разрешающего элемента

;

- для разрешающей строки

; ;

- для разрешающего столбца

; ;

; ;

- для всех остальных элементов

; ;

; ;

; ;

; ;

 

 

БП	СЧ	СП	α
x4	x6
x3	23/5	4/5	-3/5	23/4
x1	1/5	-2/5	-1/5	-1/2
x5	11/5	3/5	-1/5	r 33/9
x2	12/5	1/5	3/5
L	53/5	k -6/5	7/5

Таблица 3

 

 

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

На пересечении разрешающей строки и столбца получаем разрешающий элемент . Для таблицы 4 разрешающую строку х₅ выводим из базиса, а разрешающий столбец х₄ вводим в базис.

Производим пересчет симплексной таблицы:

- для разрешающего элемента

;

- для разрешающей строки

; ;

- для разрешающего столбца

; ;

; ;

- для всех остальных элементов

; ;

; ;

; ;

; ;

Таблица 4

БП	СЧ	СП
x5	x6
x3	5/3	-4/3	-1/3
x1	5/3	2/3	-1/3
x4	11/3	5/3	-1/3
x2	5/3	-1/3	2/3
L

 

 

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

Приравняв свободные переменные к нулю, получаем x₁= , x₂= , L=15 ед.

Вывод: оптимальный план производства изделия А 5/3 единиц, изделия В 5/3 единиц, при этом максимальная прибыль составит 15 единиц.

---

Дата добавления: 2016-01-03; просмотров: 18; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!