Лекция 3. Алгоритм симплексного метода

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

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

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

Имеется несколько вариантов алгоритма симплекс-метода: обычный, m -метод (искусственного базиса) и др.

Рассмотрим вариант, позволяющий осуществлять наиболее прос-тые вычисления.

Алгоритм симплекс-метода включает несколько этапов:

1) подготовка информации (включает введение переменных и формирование ограничений);

2) преобразование ограничений и запись их в матрицу;

3) поиск опорного решения;

4) поиск оптимального решения.

К примеру, имеем следующую экономико-математическую задачу:

Преобразование ограничений связано в первую очередь с превращением неравенств в уравнения. Если при этом ограничения приведены к типу «≤», то процедура вычислении значительно упрощается. Для этого ограничения типа «≥» умножим на (–1).

Превращение неравенств в уравнения связано с введением дополнительных переменных. В ограничениях типа «≤» дополнительные переменные обозначают величину недоиспользования ресурсов, в ограничениях типа «≥» – величину превышения ресурсов над минимумом потребности в них.

В уравнения дополнительные переменные не вводятся (или вводятся равными нулю):

При этом всякое решение осуществляется из допущения, что

тогда

, .

Решение получаем поиском опорного и оптимального решений.

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

При этом переменные, исходя из значений которых начинаем решение, будут базисными.

В первой симплексной таблице (табл. 7) такими базисными будут дополнительные переменные, т. е. вектор дополнительных переменных. Остальные переменные, обозначающие вектор-столбцы, будут небазисными. В табл. 7 небазисными будут основные переменные.

Т а б л и ц а 7. Симплексная таблица № 1

Базисные переменные	Свободные члены	Небазисные переменные
х ₁	х ₂	х ₃	…	х_n
y ₁	A ₁	a ₁₁	a ₁₂	a ₁₃	…	a _{1 n}
y ₂	A ₂	a ₂₁	a ₂₂	a ₂₃	…	a _{2 n}
y ₃	–A ₃	–a ₃₁	–a ₃₂	–a ₃₃	…	–a _{3 n}
……………………………………………………………………
	A_m	a_m ₁	a_m ₂	a_m ₃	…	a_mn
F					…

Если в столбце дополнительных переменных есть нуль, то это свидетельствует об искаженности базиса, т. е. отсутствии опорного решения. Таким образом, полученная запись при х_j = 0 свидетельствует о том, что базисное решение отсутствует по двум признакам, а именно:

– имеются отрицательные свободные члены;

– имеются нуль-значения среди базисных переменных.

Всю информацию при допущении, что х_j = 0, заносим в таблицу; табл. 7 содержит т + 2строк (где т – число строк ограничений) и п + 2столбцов (где п – число небазисных переменных).

Коэффициенты целевой функции в табл. 7 записываются с противоположным знаком.

Нахождение опорного решения предполагает замену базисных переменных небазисными или поиск нового базиса. Чтобы исключить нуль с вектора базисных переменных, необходимо в нуль-строке найти такой коэффициент, от деления на который коэффициента А_m получим наименьшее положительное частное. Для этого вектор-столбец свободных членов делим на соответствующие коэффициенты столбцов х ₁, х ₂, х ₃, ..., х_п. Допустим, что при делении на коэффициенты первого столбца, т. е. , отношение . Это означает, что требование не выполняется. В другом случае (при ) . Допустим, что при делении отношение меньше всех других значений.

Тогда коэффициент а_тп можно принять за разрешающий.

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

Для записи формул, по которым определяются коэффициенты новой симплексной таблицы (табл. 8), введем условные обозначения, в частности, а_ij – коэффициент, стоящий в строке i и столбце j. При этом F- строка будет иметь значение i + 1, а столбец свободных членов j = 0.

Т а б л и ц а 8. Симплексная таблица № 2

Базисные переменные	Свободные члены B_i	Небазисные переменные
х ₁	х ₂	х ₃
y ₁	A^/ ₁	a^/ ₁₁	a^/ ₁₂	a^/ ₁₃	a^/ _{1 n}
y ₂	A^/ ₂	a^/ ₂₁	a^/ ₂₂	a^/ ₂₃	a^/ _{2 n}
y ₃	–A^/ ₃	a^/ ₃₁	–a^/ ₃₂	a^/ ₃₃	–a^/ _{3 n}
……………………………………………………………..			……………………………………………………………………
x_n	A^/_m	a^/_m ₁	a^/ _m ₂	a^/_m ₃	a^/_mn
F

Допустим, что коэффициент а_rk – разрешающий, т. е. стоит в строке r и столбце k при . При делении значений столбца свободных членов на соответствующие коэффициенты столбца k частное от деления А_i на а_rk было наименьшим.

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

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

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

(при ),

т. е. в данном случае – при .

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

(при ), или (при ).

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

или (при ,

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

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

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

Если , то получим меньшее значение, чем от деления других частных .

Допустим, что в данном случае частное меньше всех других. Следовательно, коэффициент () является разрешающим.

Меняем местами x ₁ и у ₃,после чего проводим расчеты (табл. 9).

Т а б л и ц а 9. Симплексная таблица № 3

Базисные переменные	Свободные члены	Небазисные переменные
у ₃	х ₂	х ₃
y ₁
y ₂
х ₁
……………………………………………………………………………………………
x_n
F	F ₂

В этой таблице содержится опорное решение. Оно получено при следующих значениях переменных:

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

Чтобы найти оптимальное решение, выбираем разрешающий столбец. Им будет тот, в F -строке которого стоит наибольшее по модулю отрицательное значение при решении задачи на максимум и наибольшее положительное – на минимум.

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

Допустим, что от деления на было получено наименьшее положительное частное. Следовательно, х ₂и х ₁меняются местами, и мы находим новое решение по четырем правилам.

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

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

Рассмотрим пример реализации данного алгоритма.

Пусть необходимо определить минимальный по стоимости (у.е.) состав рациона для головы крупного рогатого скота. Для содержания животного требуется не менее 30 ц к. ед., 3,17 ц переваримого протеина, от 7 до 12 ц концентратов, не менее 10 ц сена, неболее 40 ц сенажа, не более 60 ц зеленого корма.

Неизвестными этой задачи является масса кормов, ц: х ₁– концентраты; х ₂ – сено; х ₃ – сенаж; х ₄ – зеленый корм.

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

Следовательно, требуется найти массу отдельных кормов в рационе (х ₁, х ₂, х ₃, х ₄)при следующих условиях:

1) содержание кормовых единиц в рационе составляет не меньше минимума: 1,2 х ₁ + 0,5 х ₂ + 0,3 х ₃ + 0,2 х ₄≥31;

2) содержание перевариваемого протеина в рационе составляет не меньше минимума: 0,13 х ₁ + 0,05 х ₂ + 0,033 х ₃ + 0,02 х ₄ ≥ 3,17;

3) нижняя граница по массе концентратов х ₁≥7;

4) верхняя граница по массе концентратов х ₁ ≤ 12;

5) нижняя граница по массе сена х ₂ ≥ 10;

6) верхняя граница по массе сенажа х ₃ ≤ 40;

7) по массе зеленого корма х ₄ ≤60.

Минимальная стоимость рациона выражается уравнением

F = 12 x ₁ + 4,2 x ₂ + 2,4 x ₃ +1,2 x ₄ → min.

Система неравенств задачи имеет следующий вид:

1) 1,2 х ₁ + 0,5 х ₂ + 0,3 х ₃ + 0,2 х ₄ ≥ 31;

2) 0,13 х ₁ + 0,05 х ₂ + 0,033 х ₃ + 0,02 х ₄ ≥ 3,17;

3) х ₁ ≥ 7;

4) х ₁≤ 12; (6)

5) х ₂ ≥ 10;

6) х ₃ ≤ 40;

7) х ₄ ≤ 60;

F _min= 12 х ₁+ 4,2 х ₂+ 2,4 x ₃ + 1,2 x ₄.

Приводим все ограничения к типу «меньше – равно» (≤). Для этого ограничения типа «≥», т. е. 1, 2, 3, 5, умножаем на –1:

1) –1,2 х ₁ – 0,5 х ₂ – 0,3 х ₀– 0,2 х ₄ ≤ –31;

2) –0,13 х ₁ – 0,05 х ₂ – 0,033 х ₃ – 0,02 х ₄ ≤ –3,17;

3) – х ₁≤ –7;

4) х ₁ ≤ 12; (7)

5) – х ₂ ≤ –10;

6) х ₃ ≤ 40;

7) х ₄ ≤ 60;

F = 12 х ₁+ 4,2 х ₂+ 2,4 x ₃ + 1,2 x ₄ → min.

Превращаем неравенства в уравнения. Для этого вводим дополнительные переменные у_i,где i – номер ограничения. При этом дополнительных переменных вводим столько же, сколько имеется ограничений типа «≤». В нашем случае вводим семь дополнительных переменных:

1) –1,2 х ₁ – 0,5 х ₂ – 0,3 х ₃– 0,2 х ₄ + y ₁= –31;

2) –0,13 х ₁ – 0,05 х ₂ – 0,033 х ₃ – 0,02 х ₄ + y ₂= –3,17;

3) – х ₁ + y ₃= –7;

4) х ₁ + y ₄= 12; (8)

5) – х ₂ + y ₅= –10;

6) х ₃ + y ₆= 40;

7) х ₄ + y ₇= 60;

F = 12 х ₁ + 4,2 х ₂+ 2,4 x ₃ + 1,2 x ₄ → min.

С экономической точки зрения дополнительные переменные обозначают величину недоиспользования ресурсов, если исходные ограничения имеют вид «меньше – равно» (≤), или величину превышения минимума, если исходные ограничения имеют вид «больше – равно» (≥).

К примеру, согласно системе неравенств (6) первое ограничение по содержанию кормовых единиц

1,2 х ₁ + 0, 5х ₂ + 0,3 х ₃ + 0,2 х ₄≥ 31

имеет вид «больше – равно». Допустим, что сумма произведений переменных левой части данного неравенства на коэффициенты по результатам решения равна 32. В этом случае 32 > 31. В ограничении системы неравенств (7) имеем –32 < –31. Тогда у ₁в системе (8) равен 1, т. е. –32 + 1 = –31. Поскольку число 31 является минимальной нормой, а 32 – фактически полученной, то у ₁ = 1 есть величина превышения минимума содержания кормовых единиц.

Решение задачи включает два этапа: поиск опорного, т. е. допустимого, и оптимального решений.

Опорное решение получается при значениях переменных, которые, будучи подставленными в условия (ограничения) задачи, обеспечивают выполнение всех ее условий. Поиск опорного решения начинается с допущения, что искомые переменные (т. е. x_j) равны нулю. В нашем случае x ₁, х ₂, х ₃, х ₄ = 0. Тогда, подставив эти значения в систему уравнений (8), получим: у ₁ = –31, у ₂ = 3,17, у ₃ = –7, у ₅ = – 10, у ₆ = 40, у ₇ = 60, F = 0.

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

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

Т а б л и ц а 10. Симплексная таблица № 1

Базисные переменные

Свободные члены B_i

Небазисные переменные

Единичный базис

х ₁

х ₂

х ₃

х ₄

у ₁

у ₂

у ₃

у ₄

у ₅

у ₆

у ₇

у ₁

–31

–1,2

–0,5

–0,3

у ₂

–3,17

–0,13

–0,05

–0,033

–0,024

у ₃

–7

у ₄

у ₅

–10

–1

у ₆

у ₇

F _min

–12

–4,2

–2,4

–1,2

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

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

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

, ,

, .

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

В случае, если частное от деления на выбранный отрицательный элемент получится наименьшим по сравнению с другими частными, то этот отрицательный коэффициент станет разрешающим элементом. В нашем случае от деления на коэффициент = –1 получено частное 7,0, которое меньше 25,8; 24,4 и 12,0. Следовательно, элемент = –1 будет разрешающим.

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

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

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

1. Новый коэффициент вместо разрешающего равен единице, деленной на разрешающий;

где – новый коэффициент вместо разрешающего;

– разрешающий элемент, стоящий в строке r и столбце k при ;

i – номер строки, ;

j – номер столбца, .

Разрешающий элемент обводим кружком.

Т а б л и ц а 11. Симплексная таблица № 2

Базисные переменные	Свободные члены	Небазисные переменные
y ₃	х ₂	x ₃	x ₄
y ₁	–22,6	–1,2	–0,5	–0,3	–0,2
y ₂	–2,26	–0,13	–0,05	–0,033	–0,02
x ₁		–1
y ₄			0
y ₅	–10
y ₆
y ₇
F _min		–12	–4,2	–2,4	–1,2

2. Новые коэффициенты строки разрешающего элемента равны предыдущим коэффициентам , деленным на разрешающий. В нашем случае

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

В нашем случае

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

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

Тогда

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

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

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

По данным правилам делаем преобразования, т. е. находим новые коэффициенты симплексной таблицы № 2. При этом базисную переменную у ₅поменяем местами с небазисной основной переменной х ₂.Таким образом, получаем симплексную таблицу № 3 (табл. 12).

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

Т а б л и ц а 12. Симплексная таблица № 3

Базисные переменные	Свободные члены	Небазисные переменные
y ₃	y ₅	y ₃	y ₄
y ₁	–17,6	–1,2		–0,3	–0,2
y ₂	–1,76	–0,13	–0,05	–0,033	–0,02
x ₁		–1
y ₄
x ₂			–1
y ₆
y ₇
F	126,0	–12,0	–4,2	–2,4	–1,2

Так как в табл. 12 опорное решение отсутствует, то продолжаем его поиск.

Выбираем любой из двух оставшихся отрицательных свободных членов. Например, –17,6. Первый отрицательный коэффициент в его строке = – 1,2 не является разрешающим, так как от деления на него меньшее положительное частное не получается. Проверка показывает, что = –0,5. Коэффициент является разрешающим. При этом в равной мере разрешающим может быть также и коэффициент во второй строке ( = –0, 05), так как полученные частные одинаковы:

Заменяем небазисную переменную у ₅базисной у ₁и делаем преобразования (табл. 13).

Т а б л и ц а 13. Симплексная таблица № 4

Базисные переменные	Свободные члены,	Небазисные переменные
y ₃	y ₁	х ₃	x ₄
y ₅	35,2	2,4	–2,0	0,6	0,4
y ₂	0,000	–0,010	–0,100	–0,033	0,000
x ₁		–1
y ₄
x ₂	45,2	2,4	–2,0	0,6	0,4
y ₆
y ₇
F	272,54	–1,92	–8,40	0,12	0,48

Итак, опорное решение (план) получено при следующих значениях основных переменных: x ₁= 7,0; х ₂= 45,2; дополнительных – у ₅ = 35,2; y ₂ = 0; у ₄ = 5; у ₆ = 40; у ₇ = 60 и F = 272,54 у.е.

Таким образом, после подстановки значений x ₁ и х ₂в систему неравенств (6) все условия будут выполнены.

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

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

В данном случае в F -строке для переменной х ₄ имеется наибольший положительный коэффициент (0,48). Следовательно, столбец х ₄является разрешающим. Чтобы найти разрешающий элемент, делим столбец свободных членов на соответствующие коэффициенты разрешающего столбца. Разрешающим будет элемент, от деления на который получается меньшее положительное частное. В данном случае таковым будет = 1, так как

Меняем местами переменные х ₄и у ₇и определяем по изложенным выше правилам новые коэффициенты (табл. 14).

Т а б л и ц а 14. Симплексная таблица № 5

Базисные переменные	Свободные члены	Небазисные переменные
y ₃	y ₁	х ₃	y ₇
y ₅	11,2	2,4	–2,0		–0,4
y ₂	0,00	–0,01	–0,10	–0,03	0,00
x ₁		–1
y ₄
х ₂	21,2	2,4	–2,0	0,6	–0,4
y ₆	40,00	–4,00	3,30	1,00	0,66
х ₄
F	243,74	–1,92	–8,40	0,12	–0,48

Оптимальное решение здесь отсутствует, так как в F -строке столбца х ₃ имеется положительный коэффициент. Этот столбец будет разрешающим. По отношению значений столбца свободных членов и соответствующих коэффициентов столбца x ₃ определяем, что разрешающим будет коэффициент = 0,6.

Заполняем новую таблицу, меняя при этом местами переменные у ₅ и х ₃(табл. 15).

Т а б л и ц а 15. Симплексная таблица № 6

Базисные переменные	Свободные члены	Небазисные переменные
y ₃	y ₁	y ₅	y ₇
x ₃	18,54	4,00	–3,30	1,70	–0,66
y ₂	0,050	0,012	–0,010	0,005	–0,002
x ₁		–1
y ₄
x ₂				–1
y ₆	21,46	–4,00	3,30	–1,70	0,66
x ₄
F	241,5	–2,4	–8,0	–0,2	–0,4

Таким образом, оптимальное решение получено. Минимум функции составляет 241,50 денежной единицы при значениях переменных x ₁= 7, х ₂ = 10, х ₃ = 18,54, х ₄ = 60. Значения дополнительных переменных составили: у ₃, у ₁, у ₅, у ₇, у ₆.Подставим значения переменных в систему неравенств (8):

1) –1,2 x ₁ – 0,5 x ₂ – 0,3 х ₃ – 0,2 х ₄+ у ₁ = –31,

или

–1,2 × 7 – 0,5 × 10 – 0,3 × 18,54 – 0,24 × 60 + y ₁= –31;

–31 + y ₁ = –31; y₁ = 0.

В табл. 15 имеем то же, а именно: у ₁ = 0;

2) –0,13 × 7 – 0,05 × 10 – 0,033 × 18,54 – 0,02 × 60 + у ₂ = –3,17;

–3,22 + y ₂ = –3,17; y ₂ = 0,05.

Превышение над минимумом составляет 0,05;

3) –7 + у ₃ = –7; у ₃ = 0;

4) 7 + у ₄ = 12; у ₄ = 5,

что и в симплексной таблице № 6, т. е. ресурс недоиспользован на 5 единиц (ц);

5) –10 + у ₅ = –10; у ₅ = 0;

6) 18,54 + у ₆ = 40; у ₆ = 21,46,что и в симплексной таблице № 6;

7) 60 + у ₇ = 60; у ₇ = 0.

F _min= 12 × 7 + 10 × 4,2 + 18,54 × 2,4 + 60 × 1,2 = 241,5 денежной единицы. Следовательно, все условия задачи выполнены, решение получено.

В отдельных случаях среди ограничений задачи могут быть уравнения. Допустим, что в данной задаче условие (6) имеет вид х ₁ = 7.Тогда вводить дополнительную переменную у,как это сделано в системе (8), не требуется. Вместо у ₃в табл. 10 в числе базисных переменных стоял бы нуль. Свободный член был бы равен 7, а коэффициент a ₃₁ = 1. Наличие нуля в базисных переменных (как и отрицательных свободных членов) свидетельствует об отсутствии опорного решения. Для получения опорного решения требуется избавиться от отрицательных свободных членов и переместить нули из базисных переменных в небазисные. Методика переноса нулей состоит в том, что в строке с нулем в базисных переменных находят разрешающий элемент по обычному правилу, т. е. по наименьшему положительному частному от деления свободного члена на коэффициент. В данном случае при делении свободных членов на соответствующие коэффициенты столбца x ₁ коэффициент a ₃₁ = 1 стал бы разрешающим. Выполнив преобразования по изложенным выше правилам, мы имели бы в небазисных переменных вместо х_j нуль, а в базисных переменных вместо нуля – х ₁.После этого следует вычеркнуть весь нуль-столбец и продолжать решение, но с тремя вектор-столбцами небазисных переменных.

Лекция 4. ЭКОНОМИЧЕСКОЕ СОДЕРЖАНИЕ

СИМПЛЕКС-МЕТОДА

Экономическое содержание коэффициентов

Пропорциональности

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

П р и м е р. Рассчитать размеры отраслей с целью получения максимальной прибыли.

1. Ограничение по использованию пашни, га:

х ₂ + х ₂ + х ₃ ≤ 1000.

2. Ограничение по использованию труда, чел.-дн.:

9 х ₁ + 22 х ₂ + 8 х ₃ + 20 х ₄ ≤ 20000.

3. Ограничение по использованию фондов, у.е.:

600 х ₁ + 1200 х ₂ + 300 х ₃ + 1500 х ₄ ≤ 1352000.

4. Ограничение по использованию и производству кормов, ц к.ед.:

50 х ₄ ≤ 5000 + 15 х ₁+ 20 х ₂ + 30 х ₃.

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

F = 300 x ₁ + 600 x ₂ + 1000 х ₄ → mах,

где х ₁ – площадь зерновых, га;

х ₂ – площадь картофеля, га;

х ₃ – площадь силосных, га;

х ₄ – поголовье коров, гол.

Сведем эту исходную информацию в табл. 16.

Т а б л и ц а 16. Симплексная таблица № 1

Базисные переменные	Свободные члены,	Небазисные переменные
x ₁	х ₂	х ₃	х ₄
у ₁
у ₂
у ₃
у ₄		–15	–20	–30
F		–300	–600		–1000

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

Т а б л и ц а 17. Симплексная таблица № 2

Базисные переменные	Свободные члены,	Небазисные переменные
х ₁	х ₂	х ₃	у ₄
у ₁
у ₂					0,4
у ₃					–30
х ₄		–0,3	–0,4	–0,6	0,02
F		–600	–1000	–600

С экономической точки зрения новый коэффициент (вместо разрешающего) означает то, сколько единиц переменной х ₄ можно получить за счет единицы ресурса у ₄(0,02). При этом

Новые коэффициенты столбца разрешающего элемента показывают, сколько единиц ресурсов требуется при знаке «плюс» (или сколько их получим при знаке «минус»), если в план или в базис введем небазисные переменные в размере, равном значению нового коэффициента вместо разрешающего (0,02). При этом

Новые коэффициенты строки разрешающего элемента показывают, на сколько единиц увеличивается ранее введенная в план переменная, если в план или в базис введем небазисную переменную в размере 1 (увеличивается при знаке «минус» и уменьшается при знаке «плюс»). Например, согласно данным табл. 16 при введении в план х ₁ в размере 1 требуется: первого ресурса – 1, второго – 9, третьего – 600, а четвертого получим 15 единиц. Согласно табл. 17 за счет 15 единиц четвертого ресурса можно иметь приращение х ₄ на 0,3 (так как на единицу х ₄требуется 50 ц к. ед. ресурса у ₄),при введении х ₂ = 1 – приращение х ₄на 0,4 и т. д.

при .

Согласно данным табл. 16 при введении в базис х ₁ в размере 1 требуется ресурсов: у ₁ = 1, у ₂ = 9, у ₃ = 600 и получаем ресурс у ₄ = – 15, а значение F ( = –300) возрастет. Согласно данным табл. 17 при введении х ₁ = 1 значение х ₄возрастет на 0,3 ( = –15/50 = –0,3). Логика формирования такова.

При x ₁ = 1 значения составляют:

y ₁= 1; y ₂= 9; y ₃= 600; y ₄= –15; x ₄= 0; F = –300.

В расчете на x ₄ = –0,3 изменение коэффициентов (, ) составит:

0 × (–0,3); 20 × (–0,3) = –6; 1500 × (–0,3) = –450; х ₄ = у ₄; а_rk = – 0,3;

–1000 × (–0,3) = 300.

Новые значения вектор-столбца в табл. 17 составят:

1 – 0 = 1; 9 – (–6) = 15; 600 – (–450) = 1050; 0 – 0,3 = –0,3;

–300 – (+300) = –600.

Новые коэффициенты, не стоящие в столбце и строке разрешающего элемента, включают расход (при знаке «+») или поступление (при знаке «–») ресурсов на одну небазисную переменную, а также на величину приращения ранее введенной в план переменной (пример с коэффициентами вектор-столбца x ₁). В табл. 17 эти коэффициенты включают расход или поступление ресурсов от введения в план х ₁в размере 1, а также расход и поступление ресурсов в расчете на 0,3 х ₄.