· умножение уравнения E1(X) = 0 на константу K1 и замена уравнения E1(X) = 0 уравнением K1*E1(X) = 0;
· сложение уравнений E1(X) = 0 и E2(X) = 0 c последующей заменой уравнения E2(X) = 0 уравнением E1(X) + E2(X) = 0.
Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице:
Ai,p = 0, если i не равно q
и
Ai,p = 1, если i = q.
Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение.
Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений. Однако, трудные для симплекс метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами.
На звероферме могут выращиваться норки, выдры и нутрии. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны получать зверьки в среднем приведено в таблице:
| Количество единиц корма, которое ежедневно должны получать | ||||
| Вид корма | Норка | Выдра | Нутрия | Общее количество корма |
| I | 4 | 2 | 5 | 190 |
| II | 5 | 3 | 4 | 320 |
| III | 7 | 9 | 5 | 454 |
| Прибыль от реализации одной шкурки, руб. | 150 | 320 | 350 | |
В таблице указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки зверька.
1) Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).
2) Полученное математическое описание приводят к канонической форме.
3) Каноническую форму приводят к матричному виду.
4) Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m – число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.
5) Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Если удалены все искусственные столбцы, то получено первое допустимое решение. Если искусственные элементы не удается вывести из базиса, то система не имеет решений.
6) Строят последовательность матриц. Нужно определить ведущий столбец, ведущую строку и ведущий элемент. Элемент, соответствующий ведущей строке, удаляется из базиса, а на его место ставят элемент, соответствующий ведущему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец.
Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых коэффициентов при всех ограничениях.
Ответ записывается следующим образом:
- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.
- Для каждого нулевого коэффициента в векторе решения ставится в соответствие значение свободного члена из строки, содержащей единицу в столбце данной переменной.
- Фиктивные переменные в ответе не учитываются.
Ведущим может быть назначен любой столбец, удовлетворяющий одному из условий:
1) Первый столбец, содержащий положительный элемент в векторе решений.
2) Столбец, содержащий наибольший положительный элемент в строке решения.
3) Если столбец удовлетворяет условию max(Cj min bj/aij) при решении на max, и min(Cj min bj/aij)при решении задач на min.
Cj – коэффициент целевой функции в столбце j, aij – коэффициент в столбце j и строке i.
Определим максимальное значение целевой функции F(X) = 3500 x1 +3200 x2 +1500 x3 при следующих условиях ограничений.
4 x1 + 2 x2 + 5 x3 <=190
5 x1 + 3 x2 + 4 x3 <=320
7 x1 + 9 x2 + 5 x3 <=454
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
4x1 + 2x2 + 5x3 + 1x4 + 0x5 + 0x6 = 190
5x1 + 3x2 + 4x3 + 0x4 + 1x5 + 0x6 = 320
7x1 + 9x2 + 5x3 + 0x4 + 0x5 + 1x6 = 454
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x4 , x5 , x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,190,320,454)
Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы.
Переходим к основному алгоритму симплекс-метода.
| X1 | X2 | X3 | X4 | X5 | X6 | св. чл. |
| 4 | 2 | 5 | 1 | 0 | 0 | 190 |
| 5 | 3 | 4 | 0 | 1 | 0 | 320 |
| 7 | 9 | 5 | 0 | 0 | 1 | 454 |
| -3500 | -3200 | -1500 | 0 | 0 | 0 | 0 |
Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x1
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| X1 | X2 | X3 | X4 | X5 | X6 | св. чл. |
| 1 | 1/2 | 5/4 | 1/4 | 0 | 0 | 190/4 |
| 5 | 3 | 4 | 0 | 1 | 0 | 320 |
| 7 | 9 | 5 | 0 | 0 | 1 | 454 |
| 3500 | 3200 | 1500 | 0 | 0 | 0 |
| X1 | X2 | X3 | X4 | X5 | X6 | св. чл. |
| 1 | 1/2 | 5/4 | 1/4 | 0 | 0 | 190/4 |
| 0 | 1/2 | -9/4 | -5/4 | 1 | 0 | 165/2 |
| 0 | 11/2 | -15/4 | -7/4 | 0 | 1 | 243/2 |
| 0 | -1450 | 2875 | 875 | 0 | 0 |
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей
Разрешающий элемент равен 5.5 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной xв план 2 войдет переменная x2
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=5.5
На месте разрешающего элемента в плане 2 получаем 1.