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

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

При этом расход времени на создание изделия на оборудовании каждого вида будет равен:

b1 = 15;

b2 = 9;

b3 = 18.

Ответ: X = (0;3;0;0); Y=150.

 

 

2.3 Алгоритм метода искусственного базиса

Для того, чтобы воспользоваться стандартной процедурой симплекс-метода на первом этапе, необходимо выполнить замену. Ввести искусственную целевую функцию F′ = -F.

Представление исходной системы неравенств ограничений в виде системы равенств:

ai1∙x1 + … + aij∙xj = bi                                                                                       (2.3.1)

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

Zi = bi - (ai1∙x1 + … + aij∙xj)                                                                               (2.3.2)

Формирование искусственной целевой функции, выраженной через искусственные переменные:

F = Z1 + Z2 + … + Zm → min                                                                            (2.3.3)

Используем симплекс-метод для минимизации целевой функции, при этом возможны 2 пути:

* Fmin > 0

В этом случае система уравнений, исходная система ограничений не имеет неотрицательных решений, а это значит, что и исходная задача ЛП с такой системой ограничений не имеет решений

* Fmin = 0

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

На этом первый этап закончен и приступаем к оптимизации имеющегося плана.

 

 

2.4 Двойственный симплекс-метод

Непосредственное приложение теории двойственности к вычислительным алгоритмам линейного программирования позволило разработать еще один метод решения ЗЛП, получивший название двойственного симплекс-метода, или метода последовательного уточнения оценок. Впервые он был предложен Лемке в 1954 г.

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

Идея двойственного симплекс-метода состоит в том, что, переходя от одной двойственно допустимой  базы к другой, нужно получить такую базу, для которой qi0 ≥ 0 (i = 1, 2, …, s).

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

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

Пусть дана задача линейного программирования, в которой единичными являются m производственных векторов Pj (P1, P2, … , Pm).

Y = c1x1 + c2x1+ … + cnxn → max                                                                    (2.4.1)

x1P1 + x2P2 +… + xmPm + xm+1Pm+1 + xnPn = b                                                  (2.4.2)

xj ≥ 0 (j = 1, …, n)                                                                                             (2.4.3)

Где  P1 = [1, 0, 0, …, 0, 0]

P2 = [0, 1, 0, …, 0, 0]

…

Pm = [0, 0, 0, …, 0, 1]

Pm+1 = [a11, a21, …, am1]

…

Pn = [a1n, a2n, …, amn]

Среди bi есть отрицательные.

В данном случае X = (b1,b2,…,bm,0,0) - решение системы (2). Однако оно не является решением (1)-(3), т.к. bi может быть отрицательным числом.

Поскольку P1, … ,Pm - единичные, каждый из Pj (j от 1 до m) можно представить виде линейной комбинации данных векторов, причем коэффициенты разложения Pj по P1,…,Pm - некоторые числа yij (i от 1 до m; j от 1 до n), так что можно найти Dj:

                                                 

                                                                                                                          (2.4.4)

 

Решение системы линейных уравнений (2.4.2) вида X = (b1, b2, …, bm, 0, 0) определяются базисом P1, …, Pm , который называется псевдопланом задачи (2.4.1)-( 2.4.3), если ≥ 0, для (j от 1 до n).  

• Если в псевдоплане, определенном базисом P1,…, Pm , есть хотя бы одно отрицательное число bi , такое, что все yij ≥ 0 (j от 1 до n), то задача (2.5.1)-( 2.5.3) вообще не имеет плана.     
• Если в псевдоплане имеется отрицательные bi, такие, что все yij ≥ 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.1)

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

         (3.2.2)

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

,              (3.2.2.1)

где .         (3.2.3)

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

        (3.2.4)

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

             (3.2.4.1)

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

      (3.2.5)

;  ;  ;  ; 

;  ;  .

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

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

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

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

,                                                                                                 (3.2.6)

где

 

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

  

  

  

 

 

 

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

Определяем вектор, подлежащий исключению из базиса. Для этого находим для ai3>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. Симплекс-таблица для второй итерации.