Шее симплексное отношение

b

θ0 j =

min ⎨ i ⎬,

i =1, m, (9)

aij >

aij

где j – номер вектора, вводимого в базис. Рассматривают только положитель-

ные симплексные отношения. Нулевые, отрицательные и неопределённые

(дробь со знаменателем ноль) отношения не рассматриваются.

В данном случае

j = 2, поэтому

b ⎧ 3 1 1 ⎫

θ02 =

min i = min ⎨15:; 7:;12:

⎬ = min{25;35;60} = 25.

ai 2 >0 ai 2

⎩ 5 5 5 ⎭

Симплексные отношения означают возможные объёмы производства

продукции

P 2 из имеющихся запасов сырья. Наименьшее симплексное отноше-

ние означает максимально возможный выпуск этой продукции. Действительно,

запасы сырья

S 1 позволяют изготовить не более 25 единиц продукции

P 2, в то

время как сырьё 2-го вида – 35 единиц, а 3-го – 60 единиц.

Наименьшее симплексное отношение соответствует вектору

А 3, значит,

этот вектор будет выведен из базиса. Он расположен в т.н. направляющей строке, которую выделим жирной линией и стрелкой. На пересечении направ- ляющей строки и направляющего столбца находится разрешающий элемент

a = 3, выделяемый квадратными скобками (табл. 3).

12 5

Новый базис

Б 2 = (A 3,

A 2,

A 5)

обуславливает необходимость пересчёта

симплексной таблицы. Элементы направляющего столбца (за исключением разрешающего) должны быть преобразованы в нули, а сам разрешающий эле- мент должен стать единицей.

Рекомендуем воспользоваться двумя элементарными преобразования-

ми Гаусса: 1) направляющую строку умножаем на подходящее число и при-

бавляем к другой строке; 2) направляющую строку делим на разрешающий элемент. Необходимые пояснения помещены в табл. 3.

Табл. 3. Первая симплексная таблица с полными комментариями

Б 1	С 1 Б	В 1	À 1	À 2	À 3	À 4	А 5
–4	–5
À 3				⎡ = 3⎤ ⎢ ⎥
À 4
À 5
z j − c j

↓

θ

×⎛− = 1⎞ ×⎛− = 25⎞ ×5

← 25

⎜ ⎟ ⎜ ⎟

⎣5⎦

⎝ 3⎠ ⎝

35

3 ⎠ 3

60

Например, чтобы получить 0 на месте элемента

a 22 =1/ 5, умножим на-

правляющую строку на (–1/3) и прибавим ко второй строке. Получим:

–5 − 1

+ 12

− 1 − 1

5 3

0 0 направл. строка, умноженная на (–1/3)

7 1 1 0 1 0 вторая строка

4 5

2 1 0 − 1 1 0 результат сложения

6 3

Результаты вычислений поместим в табл. 4.

Табл. 4. Вторая симплексная таблица

Б 2	С Б 2	В 2	À 1	À 2	À 3	À 4	А 5
–4	–5
À 2	–5
À 4			⎡1⎤ ⎢		− 3
À 5					−
z j − c j	–125			−

Получили второй опорный план

X Б 2

= (0; 25; 0; 2; 7). Значение целевой

/

функции:

Z (X Б 2)= −125.

В индексной строке есть положительная оценка оптимальности

23

z 1 − c 1 = 12. Следовательно, опорный план X Б 2

не является оптимальным. Не-

обходим переход к новому опорному плану. Положительная оценка оптималь-

ности единственная и, значит, наибольшая. Ей соответствует вектор

À 1, кото-

рый будем вводить в базис. Рассчитав наименьшее симплексное отношение,

получим, что вектор

À 4 следует выводить из базиса. Отмечаем направляющие

строку и столбец, разрешающий элемент, вносим пояснения (табл. 5).

После расчётов и преобразований получим табл. 6.

Табл. 5. Вторая симплексная таблица с полными комментариями

↓

θ

60

×⎛− = 5⎞ ×⎛− = 23⎞ ×6

← 12

⎜ 2 ⎟ ⎜ 2 ⎟

16 4

5

⎝ ⎠ ⎝ ⎠

Табл. 6. Третья симплексная таблица

Б 2	С Б 2	В 2	À 1	À 2	À 3	À 4	А 5
–4	–5
À 2	–5
À 4			⎡ = 1⎤ ⎢		− 3
À 5					−
z j − c j	–125			−

С

Б 3	Б	В 3	À 1	À 2	À 3	À 4	А 5
–4	–5
À 2	–5				2,5	–2,5
À 1	–4				–2
À 5					0,5	–2,5
z j − c j	–148			–4,5	–11,5

3

Третий опорный план

X Б 3

= (12; 20; 0; 0; 2)

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

среди оценок оптимальности

z j − c j

нет положительных чисел. Значение целе-

вой функции:

Z min = −148.

Полученный оптимальный план является единственным, потому что сво-

бодные векторы

À 3 и

À 4 имеют отрицательные оценки оптимальности

z 1 − c 1 = −4, 5 и

z 2 − c 2 = −11, 5, соответственно.

Если хотя бы одни из свободных векторов имеет нулевую оценку опти- мальности, то существует ещё как минимум один оптимальный план. Для его нахождения надо попытаться ввести данный вектор в базис, а вывести вектор с наименьшим положительным симплексным отношением. Общее решение зада- чи ЛП запишется как выпуклая линейная комбинация оптимальных планов.

Задача (4)-(6) решена. Возвращаемся к исходной задаче ЛП (1)-(3). Опти-

мальный план выпуска продукции

x * =12

т. и

x * = 20

т., при котором доход от

реализации будет максимальным и составит

JJG*

Z max =148 тыс. грн.

Ответ:

X = (12; 20),

Z max =148.

2. Приведём алгоритм симплексного метода и замечания к нему:

1) Задачу ЛП записываем в каноническом виде.

2) Находим опорное решение (в каждом уравнении должна быть пере-

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

3) Составляем симплексную таблицу. Проверяем знаки оценок оптималь-

ности

z j − c j. Если все

z j − c j ≤ 0, то оптимальное решение найдено и опреде-

лён минимум Z. Если же имеются

z j − c j

> 0, то вектор с наибольшей положи-

тельной оценкой оптимальности вводят в базис. Из базиса выводят вектор с наименьшим положительным симплексным отношением. Составляем новую симплексную таблицу с помощью элементарных преобразований Гаусса.

4) В новой симплексной таблице снова проверяем знаки чисел в индекс-

ной строке. Преобразования продолжаем до тех пор, пока не получим в индекс-

ной строке все числа равные нулю или меньше нуля.

5) Записываем оптимальный план и минимальное значение целевой функции для задачи ЛП в каноническом виде.

6) Возвращаемся к исходной задаче ЛП. Записываем оптимальный план и оптимальное значение целевой функции.

Замечание 1. Если в оптимальном плане свободный вектор

À j имеет ну-

левую оценку оптимальности и среди его координат есть положительные числа,

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

À j, найдем ещё

Замечание 2. Если на некотором этапе решения возникнет j -й столбец с

членами

ai ′ j ≤ 0

и оценкой оптимальности

z j − c j

> 0, то

Z → −∞.

Домашнее задание. Заводской цех выпускает 4 вида деталей, для произ- водства которых использует сырьё, материалы и комплектующие изделия. Для выпуска деталей 1-го вида требуется 2 ед. сырья и 2 ед. комплектующих, 2-го вида – 2 ед. сырья, 1 ед. материалов и 1 ед. комплектующих, 3-го вида – 4 ед. сырья и 2 ед. материалов, 4-го вида – 5 ед. сырья, 2 ед. материалов и 6 ед. ком- плектующих. Производственные запасы имеются в количестве 28 ед. сырья, 10 ед. материалов и 14 ед. комплектующих изделий. Прибыль цеха от продажи од- ной детали 1-го вида составляет 2 тыс. грн., 2-го вида – 4 тыс. грн., 3-го вида – 6 тыс. грн. и 4-го вида – 1 тыс. грн. Необходимо спланировать выпуск продукции таким образом, чтобы прибыль от реализации выпущенных деталей была наи- большей.

Ответ: Оптимальные планы

JJG*

X 1

= (4; 6; 2;0)

JJJG*

и X 2

= (2;10; 0; 0),

Z max = 44

тыс. грн. Общее оптимальное решение

JG*

X

JJG*

= λ X 1

J JG*

+ (1 − λ) X 2

, 0 ≤ λ ≤1.

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

JJG*

X = (4λ;6λ; 2λ;0) + (2 − 2λ;10 −10λ; 0; 0) = (2 + 2λ;10 − 4λ; 2λ;0).

По смыслу задачи, количество деталей – неделимая величина. Значит,

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

1) (4; 6; 2; 0), 2) (2;10; 0; 0), 3) (3;8;1; 0).

Дата добавления: 2014-01-07