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

Таблица 34.

Исходная симплексная таблица

Базисные переменные,λi	Свободные члены, bi	Небазисные				Единичный баланс
		x1	x2	x3	x4	y1	y2	y3	y4	y5	y6	y7
1	2	3	4	5	6	7	8	9	10	11	12	13
y1	-31	-1,2	-0,5	-0,3	-0,2	1
y2	-3,17	-0,13	-0,05	-0,033	-0,02	1
y3	-7	-1	1
y4	12	1	1
y5	-10	-1	1
y6	40	1	1
y7	60	1	1
F	0	-12	-4,2	-2,4	-1,2	0	0	0	0	0	0	0

Признаком наличия опорного решения, т. е. выполнения условий при x_j = 0 будут положительные свободные члены. При наличии хотя бы одного отрицательного свободного члена опорное решение будет отсутствовать. В нашем случае опорное решение отсутствует. Для его поиска сведем информацию в табл. 34.

Переменные столбца 1 согласно (4), исходя из значений которых начинаем поиск оптимального решения, будут базисными. Базисные переменные согласно 4, т. е. в случае, когда искомые переменные х₁ х₂, х₃, х₄ равны нулю, будут равны свободным членам. Их значения заносим в столбец 2. Остальные переменные, в нашем случае x_j (х₁ х₂, x₃, х₄), небазисные. Они равны нулю.

На пересечении базисных и небазисных переменных записываем коэффициенты системы уравнений 3, т. е. в клетку k₁₁ = -1,2; k₁₂ = -0,5 и т.д. При записи коэффициентов F -строки, т. е. целевой функции, их знаки меняем на противоположные.

Приступаем к поиску опорного решения. Для этого необходимо, чтобы в процессе преобразований отрицательные свободные члены стали положительными. При этом с целью упрощения расчетов и уменьшения размерности матрицы исключим столбцы единичного базиса, т. е. y₁/y₇.

6.1. Методика определения опорного решения

Среди отрицательных свободных членов b_i =b₁/b₇ выбираем любой (с целью упрощения расчетов, особенно, когда они выполняются вручную, лучше начать решение с отрицательного свободного члена, в строке которого стоят единицы). Допустим, берем отрицательный свободный член b₃=-7. Затем в строке взятого отрицательного свободного члена находим первый отрицательный коэффициент. Им будет а₃₁ =-1. Делим свободные члены на соответствующие коэффициенты столбца, в котором мы взяли отрицательный элемент, т. е. делим значения столбца свободных членов на соответствующие коэффициенты столбца x₁ (при этом соответствующими будем считать коэффициенты, стоящие в одной и той же строке). В нашем случае получим:

Коэффициент F строки и столбца 12 x₁ принадлежит целевой строке и в расчетах по поиску разрешающего элемента не участвует.

В случае, если частное от деления на выбранный нами отрицательный элемент получится наименьшим по сравнению с другими частными, то этот отрицательный коэффициент станет разрешающим элементом¹. В нашем случае от деления на коэффициент a₃₁ = - 1 получено частное 7, которое меньше других: 25,8; 24,4; 12. Значит, элемент a₃₁ = - 1 будет разрешающим.

Разрешающий элемент показывает, какая из небазисных переменных заменит базисную. В нашем случае базисная переменная у₃ заменит небазисную x₁. С точки зрения экономической введение x₁ в число базисных переменных обозначает, что переменная вошла в план, т. е. получит не нулевое значение.

Может получиться, что частное от деления на отрицательный элемент не будет самым меньшим. Например, пусть от деления свободных членов на коэффициенты вектор-столбца x₁ получим значения 25,8; 6,8; 7; 12. В этом случае

не будет меньшим положительным числом и, следовательно, коэффициент а₃₁ = - 1 нельзя брать за разрешающий. Тогда поступаем следующим образом.

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

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

где a_rk - разрешающий элемент, стоящий в строке г и столбце k при r0i, k0j;

i - номер строки, i= 1 ... m;

j - номер столбца, j = l...n. Разрешающий элемент обводим кружком;

a¹_rk --новый коэффициент вместо разрешающего. Он a¹₃₁

равен

2. Новые коэффициенты строки разрешающего элемента a¹_rj равны предыдущим (a_rj), деленным на разрешающий, т. е.

при j ≠ k, т. е. это правило не распространяется на разрешающий элемент. В нашем случае

3. Новые коэффициенты столбца разрешающего элемента (a¹_ik) равны предыдущим, деленным на разрешающий элемент с противоположным знаком.

при i≠r, т. е. правило не распространяется на разрешающий элемент. В нашем случае

4. Новые коэффициенты, не стоящие в строке и столбце разрешающего элемента (a_ij ), равны частному от деления разности произведения коэффициентов в главной и побочной диагонали на разрешающий элемент

при i≠r, j≠k, т.е. правило не распространяется на коэффициенты строки и столбца разрешающего элемента. При этом коэффициенты прямоугольника с учетом разрешающего относятся к главной диагонали.

Например, чтобы найти новый коэффициент вместо а¹₄₀=12, мысленно строим прямоугольник, главная диагональ которого составлена коэффициентом а₄₀=12 и разрешающим элементом a₃₁, a побочная а₃₀ и a₄₁

Тогда

Аналогично определяем новый коэффициент вместо а_FO = 0. Прямоугольник для него включает a_FO , а_F1, , а₃₀, а₃₁

В табл. 2 опорное решение отсутствует, так как три свободных члена - отрицательные.

По изложенным выше правилам ищем разрешающий элемент в строке отрицательного свободного члена y₅. Им будет а₅₂ = -1, так как при делении свободных членов на соответствующие коэффициенты столбца х₂ наименьшее положительное частное получено при делении на коэффициент a₅₂*.

По правилам l/4 делаем преобразования, т. е. находим новые коэффициенты симплексной таблицы 3. При этом базисную переменную уа поменяем местом с небазисной основной переменной х₂.

Таким образом, получаем таблицу 35.