Симплекс-метод. Определение оптимальной производственной программы предприятия

 

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

В результате симплексных преобразований получают симплексную таблицу, в которой:

1) если в строке целевой функции  имеется хотя бы один отрицательный коэффициент и в столбце, соответствующем этому коэффициенту, имеется хотя бы один положительный коэффициент, то решение может быть улучшено;

2) если в строке целевой функции  имеется хотя бы один отрицательный коэффициент, но в столбце, соответствующем этому коэффициенту, нет положительных коэффициентов, то задача не имеет решения;

3) если в строке целевой функции  нет ни одного отрицательного коэффициента, то получено оптимальное решение задачи.

Это правило применяется при решении задач на максимум.

При решении задач симплекс-методом исходным моментом является определение начального допустимого базисного решения (начального опорного плана). Все задачи, решаемые симплекс-методом, по способу нахождения начального опорного плана можно отнести к трем группам:

1) задачи линейного программирования с явно выраженным начальным опорным планом;

2) задачи линейного программирования, для нахождения начального опорного плана которых необходимо использовать простые алгебраические преобразования;

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

Рассмотрим решение задачи из каждой группы.

Пример 4.1. Предприятие выпускает продукции трех видов, расходуя при этом четыре вида ресурсов. Норма затрат ресурсов и прибыль от реализации каждого вида продукции, а также объем каждого вида ресурса представлены в табл. 4.1.

Таблица 4.1

Наименование ресурса	Объем ресурса	Норма затрат на единицу продукции
		А	В	С
Материалы, кг	24	5	7	4
Рабочая сила, чел.	80	10	5	20
Оборудование I гр., ст.-ч	10	5	2	1
Оборудование II гр., ст.-ч	6	2	1	1
Прибыль, тыс.руб.	-	18	12	8

Требуется найти такую программу производства, при которой достигается максимум прибыли от реализации продукции.

Решение

Пусть  − количество выпускаемой продукции i-гo вида, тогда система неравенства, отражающих ограничения на имеющийся объем ресурсов по каждому виду, будет следующей

Общая прибыль составит

.

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

.

Прежде чем решить задачу симплекс-методом, необходимо математическую постановку данной задачи привести к общей постановке задачи линейного программирования (канонической форме), т.е. от ограничений-неравенств перейти к ограничениям-равенствам. Для этого в каждое из неравенств вводится по одной дополнительной переменной:  В результате получаем

С экономической точкизрения дополнительные переменные  характеризуют объем неиспользуемого в плане ресурса i-го вида.

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

Для заполнения первой симплекс-таблицы необходимо представить математическую постановку задачи линейного программирования (ограничения-равенства и целевую функцию ) в удобном для этого виде

.

Первая симплекс-таблица имеет вид, представленный в табл. 4.2.

Таблица 4.2

Базисная переменная	Свободный член	Коэффициент при свободной переменной
		↑
	24	-5	7	4
	80	10	5	20
	10	5	2	1
	6	2	1	1
F	0	-18	-12	-8

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

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

1. Выбирается генеральный столбец, т.е. столбец с наибольшим по модулю отрицательным коэффициентом в строке .

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

 ,

где     -  i-й коэффициент в столбце "Свободный член";

  - i-й коэффициент в генеральном столбце.

3. На место генерального коэффициента записывается величина, обратная генеральному коэффициенту

.

4. Все значения коэффициентов генеральной строки, т.е. строки, где находится генеральный коэффициент, делятся на значение генерального коэффициента и записываются в эту же строку.

5. Все значения коэффициентов генерального столбца делятся на значение генерального коэффициента и записываются в тот же столбец с противоположным знаком.

6. Все остальные коэффициенты находятся по правилу прямоугольника

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

Таблица 4.3

Базисная переменная	Свободный член	Коэффициент при свободной переменной
			↑
	14	-1	5	3
	60	-2	1	18
	2
	2
F	36

Анализируя полученные значения коэффициентов при свободных переменных в строке целевой функции F, устанавливаем, что данное решение еще не является оптимальным, так как есть отрицательные значения коэффициентов , следовательно, необходимо продолжить решение задачи. Повторив указанные выше действия, выстраивается третья симплекс-таблица (табл. 4.4)

Таблица 4.4

Базисная переменная	Свободный член	Коэффициент при свободной переменной
				↑
F

Далее строится четвертая симплекс-таблица (табл. 4.5).

Таблица 4.5

Базисная переменная	Свободный член	Коэффициент при свободной переменной
	1
	5	9
	1
	3
F	54		1

Все значения коэффициентов при свободных переменных в строке целевой функции  неотрицательны, следовательно, получено оптимальное базисное решение (план)

.

Таким образом, при выпуске предприятием продукции вида А в объеме 1 ед., вида В − 1 ед., вида С − 3 ед. максимальная прибыль составит 54 тыс.руб. При этом материалы, оборудование I и II групп используется полностью, а рабочая сила на 5 человек недоиспользуется.

Пример 4.2. Предприятие располагает тремя группами технологического оборудования, на котором может изготавливаться семь видов изделий. Трудоемкость обработки и прибыль от реализации каждого вида изделия, а также фонд времени работы оборудования представлены в табл. 4.6.

Таблица 4.6

Группа оборудования	Фонд времени работы оборудования, ст.-ч	Трудоемкость обработки изделия
		А	В	С	D	Е	F	G
I	1100	2	2	1	4	2	1	3
II	1800	4	1	6	2	1	2	2
III	1500	0	3	8	1	3	1	2
Прибыль, тыс.руб.	-	4	6	7	5	4	2	8

Требуется организовать такую программу производства, при которой достигается максимум прибыли от реализации продукции, причем изделий вида А необходимо изготовить не менее 30 шт., вида В − не более 30 шт., вида С − ровно 10 шт., видов Е и F – в комплектности 1:3 и вида G − не менее 10 шт. и не более 50 шт.

Решение

Решение задачи начинается с математической постановки задачи. Все условия (ограничения) данной задачи можно разделить на две группы:

1) ограничения по ресурсу

где   -  количество выпускаемой продукции i-гo вида, .

2) ограничения по ассортименту

       (ограничение снизу);

       (ограничение сверху);

       (жесткое ограничение);

 (условие комплектности);

 (двустороннее ограничение).

Целевая функция для данной задачи имеет вид

Одно из ограничений по ассортименту является жестким. Это позволяет исключить из дальнейшего рассмотрения изделия вида C (т.е. условие выполняется, изделий вида Cвыпущено ровно 10 шт.), что повлечет за собой корректировку фонда времени работы оборудования. Математическая постановка задачи примет следующий вид:

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

- ограничение по ассортименту

- целевая функция

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

и .

Для нахождения начального допустимого базисного решения таких задач можно использовать простые алгебраические преобразования. Метод простых алгебраических преобразований для нахождения начального опорного плана используется в задачах, содержащих неравенства вида «≥», которые связывают только одну переменную . В рассматриваемой задаче это условие соблюдается.

Идея метода простых алгебраических преобразований заключается в переходе от старых переменных к новым следующим образом

, ,    Þ , ;

,    Þ ;

;

,    Þ ;

, ,   Þ , .

Математическая постановка в новых переменных имеет следующий вид:

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

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

;

;

;

- целевая функция

.

Путем введения дополнительных переменных  осуществляется переход от ограничений-неравенств к ограничениям-равенствам

;

.

Начальное допустимое базисное решение будет иметь вид

(свободные переменные);

  (базисные переменные).

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

Для получения оптимального решения задачи построим симплекс-таблицы (табл. 4.7 - 4.10).

Таблица 4.7

Базисная переменная	Свободный член	Коэффициент при свободной переменной
					↑
	1000	2	2	4	5	3
	1600	4	1	2	7	2
	1400	0	3	1	6	2
	30	0	1	0	0	0
	40	0	0	0	0	1
F	270	-4	-6	-5	-10	-8

Таблица 4.8

Базисная переменная	Свободный член	Коэффициент при свободной переменной
			↑
	200
	200
	200
	30	0	1	0	0	0
	40	0	0	0	0	1
F	2270	0	-2	3	2	-2

Таблица 4.9

Базисная переменная	Свободный член	Коэффициент при свободной переменной
						↑
	188
	254
	182
	30	0	1	0	0	0
	40	0	0	0	0	1
F	2330	0	2	3	2	-2

Таблица 4.10

Базисная переменная	Свободный член	Коэффициент при свободной переменной
	164
	342
	246
	30	0	1	0	0	0
	40	0	0	0	0	1
F	2410	0	2	3	2	2

В последней симплекс-таблице (табл. 4.10) содержится оптимальное решение

.

Затем осуществляется переход к старым переменным

.

Таким образом, при выпуске изделия вида A в объеме 30 шт., вида В − 30 шт., вида С − 10 шт., изделия вида D не выпускаются, вида Е − 164 шт., вида F − 492 шт., вида G − 50 шт. будет получена максимальная прибыль в размере 2410 тыс.руб.

Для планирования объемов производства характерны также задачи на минимум. Они имеют некоторые особенности. Например, при структуре ограничений, изображенной на рис. 4.1, не имеет смысла решать задачу на минимум, поскольку целевая функция всегда будет проходить через начало координат и равняться нулю. Если же среди ограничений будут неравенства вида «≥», получаем иную структуру области допустимых решений и оба типа оптимизации экономически содержательны.

Рис. 4.1. Графическое представление оптимальных планов задач

на минимум и максимум:

 - целевые функции для решения задач на минимум и максимум;

 - точки оптимума для задач обоих типов;

 - оптимальные планы задач обоих типов

Смысл ограничения вида “≥” поясним в нижеследующих задачах.

Пример 4.3. Месячная производственная программа состоит из трех видов изделий. Изделия проходят обработку на двух операциях. Трудоемкость обработки, себестоимость и оптовая цена каждого вида изделия, а также фонды времени работы оборудования приведены в табл. 4.11.

Таблица 4.11

Номер операции	Фонды времени работы оборудования, ст.-ч	Трудоемкость обработки изделия, ст.-ч
		А	B	C
1	900	1	1	3
2	1000	2	4	2
Оптовая цена, тыс.руб.		7	9	6
Себестоимость, тыс.руб.		4	5	2

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

Решение

Осуществляем математическую постановку задачи.

Пусть  − количество выпускаемой продукции i-го вида:

.

Тогда ограничения по ресурсу

и целевая функция

.

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

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

.

Также как переменная  вводится в равенство, то необходимо, чтобы она равнялась нулю. Однако если переменные  и  принять равными нулю, то переменная  будет равна 1800. Для того чтобы привести её к нулю, формируется ещё одна целевая функция f, имеющая вид

.

Тогда математическая постановка задачи будет следующей

;

.

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

.

Для того чтобы воспользоваться алгоритмом на максимум, умножим обе целевые функции на -1

;

.

Затем базисные переменные следует выразить через свободные переменные и представить ограничения-неравенства и целевые функции в виде, удобном для заполнения симплекс-таблицы

;

.

В первых двух симплекс-таблицах (табл. 4.12, 4.13) предпоследняя строка отводится для целевой функции -F, а последняя строка – -f. Решение ведётся по последней строке -f. Завершается применение метода искусственного базиса лишь в том случае, если значение целевой функции -f и коэффициентов при свободных переменных в этой функции станут равными нулю, за исключением коэффициента при переменной , который будет иметь значение 1.

Таблица 4.12

Базисная переменная	Свободный член	Коэффициент при свободной переменной
			↑
	900	1	1	3	0
	1000	2	4	2	0
	1800	7	9	6	-1
	0	4	5	2	0
	-1800	-7	-9	-6	1

Таблица 4.13

Базисная переменная	Свободный член	Коэффициент при свободной переменной
	700
	200
	200
	-1000
	0	0	1	0	0

Из табл. 4.13 следует, что

,

.

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

.

Зная начальное допустимое базисное решение, можно найти оптимальное решение данной задачи (табл. 4.14, 4.15).

Таблица 4.14

Базисная переменная	Свободный член	Коэффициент при свободной переменной
			↑
	700
	200
	200