Задачи, у которых хотя бы одно из условий задано неравенством типа (≥) или (=), решаются симплексным методом с искусственным базисом. Для рассмотрения алгоритма решения задач симплексным методом с искусственным базисом в ранее рассмотренную задачу введем дополнительные условия по гарантированному объему производства отдельных зерновых культур и сформулируем постановку задачи следующим образом.
Условие задачи:
В результате присоединения земель соседних хозяйств площадь пашни агрохолдинга увеличилась на 4000 га (В1). На этой площади планируется возделывать зерновые культуры, сахарную свеклу, подсолнечник. Под возделывание данных культур хозяйство располагает запасом дизельного топлива в количестве 280 000 кг (В2) и средствами для приобретения минеральных удобрений в количестве 450 000 кг действующего вещества (В3).
Данные об урожайности сельскохозяйственных культур, нормативах затрат производственных ресурсов и оценке продукции приведены в таблице 1. Требуется определить оптимальное сочетание посевных площадей зерновых культур, сахарной свеклы и подсолнечника с тем, чтобы получить максимум прибыли при выполнении запланированных объемов производства зерновых культур и сахарной свеклы, если известно, что производство зерна должно составлять 126 000 ц (P1), а сахарной свеклы – не менее 125 000 ц (P2).
За неизвестные примем площади посева различных культур в гектарах:
X1 - площадь посева зерновых,
Х2 - площадь посева сахарной свеклы,
Х3 - площадь посева подсолнечника.
Ограничения по использованию ресурсов записываются в виде неравенств и отражают условия по использованию пашни, труда, минеральных удобрений:
По использованию пашни:
Х1
+
Х2
+
Х3
≤
4 000
По использованию дизельного топлива:
50Х1
+
124Х2
+
68Х3
≤
280 000
По использованию минеральных удобрений:
90Х1
+
320Х2
+
90Х3
≤
450 000
По производству зерна:
40Х1
=
126 000
По производству сахарной свеклы:
300Х2
≥
125 000
Критерий оптимальности данной задачи – максимизация суммы прибыли. В этом случае целевая функция будет иметь следующий вид:
Zmax=
5,2Х1
+
10,2Х2
+
6,2Х3
Приведем запись ограничений к каноническому виду, для чего в систему условий введем дополнительные неизвестные. Тогда условия и цель задачи будут представлены в виде системы уравнений:
Дополнительные неизвестные Х4, Х5, Х6, как и в ранее рассмотренной задаче, с экономической точки зрения означают возможное недоиспользование пашни, дизельного топлива и минеральных удобрений, а X7 означает возможное перевыполнение планового задания по производству сахарной свеклы.
В полученной системе первые три заданных уравнения можно разрешить относительно дополнительных неизвестных Х4, Х5, Х6. В пятом уравнении дополнительная неизвестная х7записана со знаком минус и не может быть принята за базисную неизвестную, так как отрицательное значение базисных величин не допускается в экономических задачах, а четвертое уравнение вообще не содержит дополнительной неизвестной. Поэтому в ограничения, которые заданы неравенством (≥) или (=), вводят искусственные неизвестные Y, которые экономического содержания не имеют и вводятся в задачу для образования допустимого решения. Искусственные неизвестные в целевую функцию записываются с оценкой «М». М-оценка единицы измерения не имеет и является величиной, во много раз превышающей оценки основных неизвестных. При решении задач на максимум М-оценка вводится в целевую функцию с отрицательным знаком, а на минимум ‑ с положительным. Такая запись делает невыгодным наличие искусственных неизвестных в опорном плане и способствует их выводу из базиса. С введением искусственных неизвестных задача примет вид:
Решение задачи осуществляется в симплексных таблицах, которые отличаются от симплексных таблиц при решении задач с естественным базисом тем, что содержат две индексные строки m+1 и m+2.
За базисные неизвестные в первом опорном плане будут приняты Х4, Х5, Х6, Y1, Y2. Порядок заполнения первой симплексной таблицы такой же, как и при решении задачи с естественным базисом. В корпус матрицы записываются технико-экономические коэффициенты при переменных, а в контрольный столбец – алгебраическая сумма чисел по строке.
В индексную строку m+1 первого опорного плана по графе Bi записывается значение целевой функции, а по остальным – оценки основных неизвестных, всегда с противоположным знаком. В m+2 строку записывается алгебраическая сумма произведений М-оценки на коэффициенты соответствующего столбца (таблица 7).
В соответствии с математическим критерием оптимальности при решении задачи с искусственным базисом план будет оптимальным тогда, когда все искусственные неизвестные будут выведены из базиса, числа m+2 строки превратятся в нули, а в m+1 строке при решении задачи на максимум все числа будут неотрицательными, а при решении на минимум – неположительными. Иногда при решении задач на максимум все числа m+2 строки принимают неотрицательные, а при решении на минимум – неположительные значения. В этом случае задача не имеет решения.
Таблица 7. Сплошная симплексная таблица
i
Xj
Сj
Bi
5,2
10,2
6,2
Х1
Х2
Х3
Х4
Х5
Х6
Х7
Х4
4 000,0
1,0
1,0
1,0
1,0
0,0
0,0
0,0
4 000,0
Х5
280 000,0
50,0
124,0
68,0
0,0
1,0
0,0
0,0
2 258,1
Х6
450 000,0
90,0
320,0
90,0
0,0
0,0
1,0
0,0
1 406,3
Y1
M
126 000,0
40,0
0,0
0,0
0,0
0,0
0,0
0,0
Y2
M
125 000,0
0,0
300,0
0,0
0,0
0,0
0,0
-1,0
416,7
m+1
Zj-Cj
0,0
-5,2
-10,2
-6,2
0,0
0,0
0,0
0,0
m+2
-251 000M
-40M
-300M
0,0
0,0
0,0
0,0
M
Х4
3 583,3
1,0
0,0
1,0
1,0
0,0
0,0
0,0
3 583,3
Х5
228 333,3
50,0
0,0
68,0
0,0
1,0
0,0
0,4
4 566,7
Х6
316 666,7
90,0
0,0
90,0
0,0
0,0
1,0
1,1
3 518,5
Y1
M
126 000,0
40,0
0,0
0,0
0,0
0,0
0,0
0,0
3 150,0
Х2
10,2
416,7
0,0
1,0
0,0
0,0
0,0
0,0
0,0
m+1
Zj-Cj
4 250,0
-5,2
0,0
-6,2
0,0
0,0
0,0
-0,03
m+2
-126 000M
-40M
0,0
0,0
0,0
0,0
0,0
0,0
Х4
433,3
0,0
0,0
1,0
1,0
0,0
0,0
0,0
433,3
Х5
70 833,3
0,0
0,0
68,0
0,0
1,0
0,0
0,4
1 041,7
Х6
33 166,7
0,0
0,0
90,0
0,0
0,0
1,0
1,1
368,5
Х1
5,2
3 150,0
1,0
0,0
0,0
0,0
0,0
0,0
0,0
Х2
10,2
416,7
0,0
1,0
0,0
0,0
0,0
0,0
0,0
m+1
Zj-Cj
20 630,0
0,0
0,0
-6,2
0,0
0,0
0,0
-0,03
m+2
0,0
0,0
0,0
0,0
0,0
0,0
0,0
0,0
Х4
64,8
0,0
0,0
0,0
1,0
0,0
0,0
0,0
Х5
45 774,1
0,0
0,0
0,0
0,0
1,0
-0,8
-0,4
Х3
6,2
368,5
0,0
0,0
1,0
0,0
0,0
0,0
0,0
Х1
5,2
3 150,0
1,0
0,0
0,0
0,0
0,0
0,0
0,0
Х2
10,2
416,7
0,0
1,0
0,0
0,0
0,0
0,0
0,0
m+1
Zj-Cj
22 914,8
0,0
0,0
0,0
0,0
0,0
0,1
0,04
Улучшение опорного плана при решении задач с искусственным базисом осуществляется, как и при решении с естественным, путем последовательной замены одних базисных неизвестных на другие. Выбор направляющего столбца осуществляется по m+2 строке до тех пор, пока все числа этой строки не превратятся в нулевые. После выведения всех искусственных переменных из базиса и получения нулевых значений чисел m+2 строки выбор направляющего столбца осуществляется по числам m+1 строки, как и при решении задач с естественным базисом.
Решение данной задачи приведено в сплошной симплексной таблице (таблица 7). В первом опорном плане наибольшее по модулю отрицательное число в m+2 строке принадлежит X2, следовательно, этот столбец будет разрешающим, а разрешающая строка ‑ пятая, так как в этой строке получено наименьшее симплексное отношение.
Перерасчет всех коэффициентов нового опорного плана осуществляется по ранее рассмотренным правилам. Новая строка получается от деления всех чисел бывшей разрешающей строки на разрешающий элемент, а числа остальных строк рассчитываются по правилу прямоугольника.
В третьем опорном плане все искусственные неизвестные выведены из базиса, m+2 строка обратилась в нулевую строку, но план не является оптимальным, так как в m+1 строке имеются отрицательные числа. Поэтому разрешающий столбец находим по коэффициентам m+1 строки, как и при решении задач с естественным базисом.
Оптимальное решение получено в четвертом опорном плане, так как данная задача решается на максимум значения целевой функции, все искусственные неизвестные выведены из базиса, числа индексной строки m+2 равны нулю, а в m+1 строке все числа не отрицательные.
В соответствии с оптимальным планом под посев зерновых следует отвести 3 150 га пашни (х1=3150), под посев сахарной свеклы – 416,7 га (х2=416,7) и под посев подсолнечника – 368,5 га (х3=368,5). По оптимальному плану полностью используются только минеральные удобрения (х6=0). Недоиспользование пашни составляет 64,8 га (х4=64,8), а дизельного топлива – 45 774,1 кг (х5=45774,1). Производство сахарной свеклы и зерна соответствует плановым объемам. Сумма прибыли составит 22 914,8 тыс. рублей (Zmax=22 914,8). Любое другое сочетание посевных площадей при данных условиях неизбежно повлечет уменьшение суммы прибыли.
