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

                                                                                                                          (2.5.4)

 

Решение системы линейных уравнений (2.5.2) вида X = (b₁, b₂, …, b_m, 0, 0) определяются базисом P₁, …, P_m , который называется псевдопланом задачи (2.5.1)-( 2.5.3), если ≥ 0, для (j от 1 до n).  

• Если в псевдоплане, определенном базисом P₁,…, P_m , есть хотя бы одно отрицательное число b_i , такое, что все y_ij ≥ 0 (j от 1 до n), то задача (2.5.1)-( 2.5.3) вообще не имеет плана.     
• Если в псевдоплане имеется отрицательные b_i, такие, что все y_ij ≥ 0 (j от 1 до n), то можно перейти к новому псевдоплану, при котором значение целевой функции Y не меняется.        

 

 

 

 

 

 

 

 

 

 

 

3 Решение реальной производственной  задачи

 

3.1 Постановка  задачи

 

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

Таблица 3.1.1. Расход сырья на производство одного изделия.

Вид ресурса	Нормы затрат ресурса  на одно вычисление (у.е.)			Общее количество ресурсов
I	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Важность вычислительной операции	9	10	16

 

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

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

 

 

3.2 Решение  задачи

1) Составим математическую  модель.

Обозначим искомый выпуск изделий  через , B через , через .

Целевая функция имеет  вид:

         (3.2.1)

 

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

       (3.2.1’)

Ограничения записываются следующим образом:

         (3.2.2)

Или в общем виде:

,       (3.2.2’)

где .         (3.2.3)

Запишем эту задачу в  форме основной задачи линейного  программирования (ОЗЛП). Для этого  перейдём от ограничений неравенств к равенствам:

        (3.2.4)

В общем виде ограничения в виде равенств записываются так:

      (3.2.4’)

Преобразуем систему (3.2.4) к векторной форме.

      (3.2.5)

;  ;  ;  ; 

;  ;  .

Запишем опорный план (базисное решение).

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

2) Составим симплексную  таблицу для первой итерации. Для этого по приведённым ниже формулам найдём следующие значения и запишем их в симплекс-таблицу.

Сначала положим, что  предприятие вообще не выпускает  изделий, и поэтому целевая функция  принимает нулевое значение:

,                                                                                                 (3.2.6)

где

 

Далее найдём начальные  частичные суммы целевой функции z_i - c_i.

  

  

  

 

 

 

Таблица 3.2.2. Симплекс-таблица для первой итерации.

Базис			9 ( )	10 ( )	16 ( )	0 ( )	0 ( )	0 ( )
	0 ( )	360 ( )	18 ( )	15 ( )	12 ( )	1	0	0
	0 ( )	192 ( )	6 ( )	4 ( )	8 ( )	0	1	0
	0 ( )	180 ( )	5 ( )	3 ( )	3 ( )	0	0	1
		0 ( )	-9 ( )	-10 ( )	-16 ( )	0 ( )	0 ( )	0 ( )

 

Как видно из таблицы 3.2.2, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи.

Эти значения переменных отвечают такому «плану», при котором  ничего не производится, сырьё не используется и значение целевой функции равно нулю (стоимость произведённой продукции отсутствует). Естественно, такой план не является оптимальным.

Это видно из четвертой строки таблицы 3.2.2, так как в ней имеются три отрицательных числа Напомним, что условие оптимальности указывает на то, что в последней строке не должно быть отрицательных чисел. Эти отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции. Так число означает, что при включении в план производства одного изделия обеспечивается увеличение выпуска продукции на руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий . Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в четвертой строке столбца . Следовательно, в базис введём вектор .

Определяем вектор, подлежащий исключению из базиса. Для этого  находим  для a_i3>0, то есть . Найдя число 192/8 = 24, мы тем самым с экономической точки зрения определили, какое количество изделий C предприятие может изготавливать с учётом нормы расхода и имеющихся объёмов сырья каждого вида. Так как сырья данного вида имеется 360, 192 и 180 кг, а на одно изделие C требуется затратить сырья каждого вида 12, 8 и 3 кг соответственно, то максимальное число изделий C, которое может быть изготовлено предприятием, равно min(360/12; 192/8; 180/3)=192/8=24, то есть ограничивающим фактором для производства изделий C является имеющийся объём сырья II вида. С учётом его наличия предприятие может изготовить 24 изделия C. При этом сырьё II вида будет полностью использовано. Следовательно, вектор подлежит исключению из базиса. Столбец вектора и вторая строка являются направляющими.

3) Составим таблицу для второй итерации.

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

 

 

 

 

 

Таблица 3.2.3. Симплекс-таблица для второй итерации.

Базис			9	10 ( )	16 ( )	0 ( )	0 ( )	0 ( )
	0 ( )	72	9	9	0	1		0
	16 ( )	24			1	0		0
	0 ( )	108			0	0		1
		384	3	-2	0	0	2	0

 

При этом в столбце  записываем коэффициент С₃=16, стоящий в столбце вводимого в базис вектора . Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов подставляем единицы. Что же касается остальных элементов, то будем полагать, что они равны нулю.

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

1) Число, стоящее на месте этого элемента в предыдущей таблице. В нашем случае это число, стоящее в таблице 3.2.2 на пересечении столбца вектора и первой строки (360);

2) Число, стоящее в той же строке что и искомый элемент, а также в столбце вектора, вводимого в базис из предыдущей симплекс-таблицы. В нашем случае это число, стоящее в таблице 3.2.2 на пересечении столбца вектора и первой строки (12);

3) Число в строке введённого в базис вектора и в столбце искомого элемента в текущей симплекс-таблице. В нашем случае это число, стоящее в таблице 3.2.3 на пересечении столбца вектора и второй строки (24).

Вычитая из первого числа  произведение двух других, находим  искомый элемент: 360-12*24=72.

Записываем его в первой строке столбца вектора таблицы 3.2.3. Аналогичным образом находим и все остальные элементы:

180 - 3*24 = 108;

18 - 12*3/4 = 9;

15 - 12*1/2 = 9;

0 - 12*1/8 = -3/2;

5 - 3*3/4 = 11/4;

3 – 3*1/2 = 3/2;

0 – 3*1/8 = -3/8.

По окончании расчёта всех элементов таблицы 3.2.3 в ней получены новый опорный план и коэффициенты разложения векторов ( ) через базисные векторы , , и значения и . Как видно из этой таблицы, новым опорным планом задачи является план Х = [0; 0; 24; 72; 0; 108]. При данном плане производства изготовлены 24 изделия C и остаётся неиспользованным 72 кг сырья I вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора таблицы 3. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они были значительно изменены. Изменились данные и других столбцов, а их экономическое содержание стало более сложным.

Так, например, возьмём  два столбца вектора  . Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и 3/2 в первой и третьей строках вектора показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В. Это обеспечит увеличение выпуска продукции в выражении стоимости на 2 руб. Другими словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на ½ ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастёт на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми «нормами» затрат сырья I и III вида на изготовление одного изделия В (как видно из таблицы 3.2.2, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.