В результате присоединения земель соседних хозяйств площадь пашни агрохолдинга увеличилась на 4000 га (В1). На этой площади планируется возделывать зерновые культуры, сахарную свеклу, подсолнечник. Площадь посева технических культур по агротехническим требованиям не должна превышать 25% площади пашни, т.е. 1000 га (В2). Под возделывание данных культур хозяйство располагает запасом дизельного топлива в количестве 280 000 кг (В3) и средствами для приобретения минеральных удобрений в количестве 450 000 кг действующего вещества (В4).
Данные об урожайности сельскохозяйственных культур, о планируемых затратах производственных ресурсов в натуральном и стоимостном выражении, ценах реализации продукции и планируемом объеме прибыли в расчете на 1 га посева отдельных сельскохозяйственных культур приведены в таблице 1.
Таблица 1. Исходные данные для задачи
Показатели
Сельскохозяйственные культуры
зерновые культуры
сахарная свекла
подсолнечник
Урожайность, ц/га
40 (а1)
300 (а4)
20 (а7)
Затраты дизельного топлива, кг на 1 га
50 (а2)
124 (а5)
68 (а8)
Затраты удобрений, кг д.в-ва на 1 га
90 (а3)
320 (а6)
90 (а9)
Цена реализации 1 ц продукции, руб.
480 (k1)
120 (k2)
800 (k3)
Себестоимость 1 ц продукции, руб.
350 (d1)
86 (d2)
490 (d3)
Прибыль с 1 га, тыс. руб.
5,2
(а1·(k1‑d1)/1000)
10,2
(а2·(k2‑d2)/1000)
6,2
(а3·(k3‑d3)/1000)
Требуется определить такое сочетание посевных площадей зерновых культур, сахарной свеклы и подсолнечника, которое позволило бы при существующих ограничениях в ресурсах получить максимальную сумму прибыли.
За неизвестные примем площади посева указанных в постановке задачи сельскохозяйственных культур (в гектарах):
X1 - площадь посева зерновых,
Х2 - площадь посева сахарной свеклы,
Х3 - площадь посева подсолнечника.
Ограничения по использованию ресурсов записываются в виде неравенств и отражают условия по использованию пашни, дизельного топлива, минеральных удобрений:
По использованию пашни:
Х1
+
Х2
+
Х3
≤
4 000
По площади посева технических культур:
Х2
+
Х3
≤
1 000
По использованию дизельного топлива:
50Х1
+
124Х2
+
68Х3
≤
280 000
По использованию минеральных удобрений:
90Х1
+
320Х2
+
90Х3
≤
450 000
Критерий оптимальности данной задачи – максимизация суммы прибыли. В этом случае целевая функция будет иметь следующий вид
Zmax=
5,2Х1
+
10,2Х2
+
6,2Х3
Поскольку все условия задачи выражены неравенством типа ≤, то задача может быть решена симплексным методом с естественным базисом.
Последовательность решения задачи линейного программирования симплексным методом с естественным базисом рассмотрим на примере поставленной выше задачи.
Чтобы решить задачу, необходимо систему неравенств преобразовать в систему уравнений, т.е. привести к каноническому виду. С этой целью в каждое неравенство вводится по одной дополнительной неизвестной.
Дополнительные неизвестные в данной задаче означают:
Х4 - возможное недоиспользование пашни;
Х5 - возможное недоиспользование пашни, выделяемой под технические культуры;
В результате преобразования получим систему четырех уравнений с семью неизвестными:
Дополнительные неизвестные в целевую функцию записываются с нулевой оценкой, так как недоиспользованные ресурсы не позволяют получить прибыль
Система уравнений, в которой количество неизвестных больше количества уравнений, имеет бесконечное множество решений. Если принять, что основные неизвестные Х1=0, Х2=0, Х3=0, тогда Х4=4000, Х5=1000, Х6=280000, Х7=450000. Такое решение задачи называется первым допустимым (базисным) решением или опорным планом. С экономической точки зрения первый опорный план является исходным положением для планирования, так как все производственные ресурсы не используются, объем производства равен нулю.
Решение задачи проводится в специальных симплексных таблицах следующего вида:
Таблица 2. Макет симплексной таблицы
№ строки (i)
Базисные
переменные (Xj)
Оценки базисных
переменных (Cj)
Значения базисных
переменных (Bi)
Целевая строка
Контрольный столбец
Симплексные отношения
С1
С2
…
…
…
…
Cn
Строка неизвестных
Х1
Х2
…
…
…
…
Хn
…
…
…
m
m+1
Zj-Cj
Индексная строка
В столбец «№ строки (i)» данной таблицы записываются номера уравнений (ограничений); в столбец «Базисные переменные (Xj)» заносятся неизвестные, относительно которых разрешается система уравнений, а в столбец «Оценки базисных переменных (Cj)» - оценки целевой функции базисных неизвестных.
В столбец «Значения базисных переменных (Bi)» (столбец свободных членов) первого опорного плана (первой симплексной таблицы) заносятся значения базисных неизвестных (объем ресурсов). Целевая строка представлена коэффициентами целевой функции, а строка неизвестных – перечнем основных и дополнительных неизвестных (переменных).
В строки основной матрицы первого опорного плана заносятся технико-экономические коэффициенты при основных переменных. Коэффициенты базисных переменных в корпусе матрицы образуют единичную матрицу.
Строка m+1 называется индексной, или целевой. Если задача решается на максимум значения целевой функции, коэффициенты целевой функции заносятся в первую симплексную таблицу с обратным знаком, при решении на минимум их знаки не меняются. По числам индексной строки (коэффициентам целевой функции) определяют, в каком направлении следует улучшать план. В столбце свободных членов по этой строке записывается сумма произведений значений базисных переменных на соответствующие им оценки.
Контрольный столбец используется для контроля за правильностью расчета чисел по строке. В контрольный столбец первого опорного плана записывается алгебраическая сумма чисел по строкам, начиная со столбца свободных членов.
Столбец симплексных отношений предназначен для определения направления улучшения плана при переходе от одной таблицы к другой.
Первая симплексная таблица данной задачи представлена в таблице 3.
Таблица 3. Первая симплексная таблица
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 004,0
4 000,0
Х5
1 000,0
0,0
1,0
1,0
0,0
1,0
0,0
0,0
1 003,0
1 000,0
Х6
280 000,0
50,0
124,0
68,0
0,0
0,0
1,0
0,0
280 243,0
2 258,1
Х7
450 000,0
90,0
320,0
90,0
0,0
0,0
0,0
1,0
450 501,0
1 406,3
m+1
Zj-Cj
0,0
-5,2
-10,2
-6,2
0,0
0,0
0,0
0,0
-21,6
Базисные неизвестные характеризуют недоиспользование пашни (Х4), недоиспользование пашни под посев технических культур (Х5), дизельного топлива (Х6) и минеральных удобрений (Х7) и их значение находится в соответствующих строках столбца Bi. Коэффициенты при основных переменных Х1, Х , Х означают нормативы расхода производственных ресурсов на 1 га посева cсельскохозяйственных культур, а коэффициенты дополнительных переменных Х , Х , Х , Х образуют единичную матрицу.
После построения первого опорного плана он испытывается на оптимальность. В соответствии с математическим критерием оптимальности план будет оптимальным, если при решении задачи на максимум все числа индексной строки будут неотрицательными, а при решении задачи на минимум – неположительными.
Первый опорный план нашей задачи не является оптимальным, так как в строке m+1 имеются отрицательные числа при Х1, Х , Х , что указывает на возможность улучшения плана. Улучшение плана достигается путем замены одних базисных переменных на другие. За одну итерацию (перерасчет) можно сделать только одну замену, т. е. одну переменную вывести из базиса, а другую ввести в базис. С этой целью просматривают индексную строку и при решении задачи на максимум выбирают наибольшее по модулю число среди отрицательных, а при решении на минимум – среди положительных чисел. Эти числа указывают, какую переменную следует ввести в базис. Столбцы вводимых в базис переменных называются разрешающими (направляющими, ключевыми, генеральными). С экономической точки зрения разрешающий столбец указывает на наиболее эффективный вид производственной деятельности. В данном опорном плане разрешающим столбцом является столбец, содержащий переменную Х2, следовательно, для улучшения плана необходимо ввести в базис именно переменную Х2 (площадь посева сахарной свеклы).
Чтобы решить, какую переменную необходимо вывести из базиса, необходимо все числа столбца свободных членов построчно разделить на положительные значения разрешающего столбца, а результаты записать в столбец симплексных отношений. Наименьшее положительное симплексное отношение указывает, какую переменную необходимо вывести из базиса. Строка, в которой находится наименьшее положительное симплексное отношение, называется разрешающей (направляющей, ключевой). Разрешающая строка характеризует узкое место производства, т. е. описывает фактор, сдерживающий развитие наиболее эффективного вида производственной деятельности. Деление свободных членов на положительные элементы разрешающего столбца обеспечивает также выполнение условия неотрицательности переменных решаемой задачи.
Деление наличия производственных ресурсов на норматив их расхода по X2 показывает, что за счет пашни под сахарную свеклу можно было бы отвести 4000 га посевных площадей; наличие дизельного топлива позволит возделывать сахарную свеклу на площади 2 258,1 га, минеральных удобрений – на площади 1 406,3 га, а требование об ограничении площади посева технических культур позволяет возделывать сахарную свеклу лишь на 1 000 га. Следовательно, в данной задаче фактором, сдерживающим развития наиболее эффективной культуры (сахарной свеклы), являются агротехнические требования. В этом случае вторая строка является разрешающей, а из базиса для улучшения плана необходимо вывести X5. Число, стоящее на пересечении разрешающего столбца и разрешающей строки, называется разрешающим (направляющим, ключевым, генеральным) элементом.
Иногда при нахождении разрешающей строки можно столкнуться с таким положением, когда несколько минимальных симплексных отношений имеют одинаковое значение. Выбор разрешающей строки по любому из этих симплексных отношений ведет к нулевому значению базисной переменной в следующей симплексной таблице, т.е. к вырождению. Вырожденные задачи не имеют решения, так как образуется зацикливание. При зацикливании происходит бесчисленное повторение ввода в базис и вывода из него одних и тех же переменных. Устранить вырождение можно путем замены нулевого значения базисной переменной на очень малую величину, которая не окажет существенного значения на конечный результат решения задачи.
После выбора разрешающего столбца и разрешающей строки приступают к построению новой симплексной таблицы. Заполнение таблицы начинают с замены базисных переменных.
В данном примере для улучшения плана из базиса выводится X5, а вводится X2 с оценкой, равной 10,2. Переменные X4, X6, и X7 остаются в базисе.
Таблица 4. Вторая симплексная таблица
i
Xj
Сj
Bi
5,2
10,2
6,2
Х1
Х2
Х3
Х4
Х5
Х6
Х7
Х4
3 000,0
1,0
0,0
0,0
1,0
-1,0
0,0
0,0
3 001,0
3 000,0
Х2
10,2
1 000,0
0,0
1,0
1,0
0,0
1,0
0,0
0,0
1 003,0
Х6
156 000,0
50,0
0,0
-56,0
0,0
-124,0
1,0
0,0
155 871,0
3 120,0
Х7
130 000,0
90,0
0,0
-230,0
0,0
-320,0
0,0
1,0
129 541,0
1 444,4
m+1
Zj-Cj
10 200,0
-5,2
0,0
4,0
0,0
10,2
0,0
0,0
10 209,0
Все числа каждой последующей таблицы рассчитываются на основе элементов предыдущей. Расчет чисел новой симплексной таблицы начинают с начальной строки, т.е. с той строки, которая в предыдущей таблице называлась разрешающей. Эти элементы рассчитываются путем последовательного деления чисел бывшей разрешающей строки на разрешающий элемент: a'ij = aij/akr.
Числа бывшего разрешающего столбца можно не рассчитывать, так как коэффициент на месте бывшего генерального элемента всегда будет равен 1, а все остальные коэффициенты равны 0.
Числа остальных строк рассчитываются по правилу прямоугольника. Правило прямоугольника можно выразить следующей формулой:
,
где i - номер расчетной строки;
j - номер расчетного столбца;
k - номер разрешающей строки;
r - номер разрешающего столбца;
a¢ij- новое значение расчетного числа;
aij-старое значение числа в предыдущей таблице;
akj-число, стоящее в разрешающей строке по j-му столбцу в предыдущей таблице;
akr-разрешающий (генеральный) элемент;
air- число, стоящее в разрешающем столбце по i-й строке в предыдущей таблице.
Подставляя числа в рассмотренную формулу, рассчитаем новое значение чисел по столбцу Bi:
,
,
,
.
Рассчитаем коэффициенты при X1 во второй симплексной таблице:
,
,
,
.
Аналогично рассчитываются коэффициенты по остальным столбцам.
Расчет чисел контрольного столбца подчиняется общим правилам расчета коэффициентов симплексных таблиц. Если число контрольного столбца совпадает с алгебраической суммой чисел по строке, следовательно, числа данной строки рассчитаны правильно, если же не совпадает, то необходимо искать ошибку расчета чисел по строке.
Полученный во второй симплексной таблице опорный план не является оптимальным, так как в индексной строке имеются отрицательные числа, следовательно, его необходимо улучшать дальше. Процедура улучшения плана осуществляется по ранее рассмотренной схеме до тех пор, пока не получат оптимальный план.
Таблица 5. Третья симплексная таблица
i
Xj
Сj
Bi
5,2
10,2
6,2
Х1
Х2
Х3
Х4
Х5
Х6
Х7
Х4
1555,6
0,0
2,6
1,0
2,6
0,0
0,0
1 561,7
608,7
Х2
10,2
1000,0
1,0
1,0
0,0
1,0
0,0
0,0
1 003,0
1 000,0
Х6
83777,8
0,0
71,8
0,0
53,8
1,0
-0,6
83 903,8
1 167,2
Х1
4,8
1444,4
1,0
0,0
-2,6
0,0
-3,6
0,0
0,0
1 439,3
m+1
Zj-Cj
17711,1
0,0
-9,3
0,0
-8,3
0,0
0,1
17 693,6
Расчет чисел третьей симплексной таблицы показывает, что полученный опорный план не является оптимальным, так как в индексной строке присутствуют отрицательные значения. Рассчитывается следующий опорный план. Из базиса выводится X4, а вводится X3.
Таблица 6. Четвертая симплексная таблица
i
Xj
Сj
Bi
5,2
10,2
6,2
Х1
Х2
Х3
Х4
Х5
Х6
Х7
Х3
6,2
608,7
0,0
0,0
1,0
0,4
1,0
0,0
0,0
611,1
Х2
10,2
391,3
0,0
1,0
0,0
-0,4
0,0
0,0
0,0
391,9
Х6
5,2
40 087,0
0,0
0,0
0,0
-28,1
-18,0
1,0
-0,2
40 041,6
Х1
3 000,0
1,0
0,0
0,0
1,0
-1,0
0,0
0,0
3 001,0
m+1
Zj-Cj
23 365,2
0,0
0,0
0,0
3,6
1,0
0,0
0,0
23 369,9
Четвертый опорный план является оптимальным, так как все коэффициенты индексной строки неотрицательны.
Максимальная прибыль по оптимальному плану составляет 23 365,2 тыс. руб. и будет получена при условии, если под посев зерновых культур будет отведено 3000 га (X1=3000), под сахарную свеклу – 391,3 га (X2=391,3), под подсолнечник – 608,7 га (X3=608,7). Минеральные удобрения и площадь пашни используются полностью (X4=0, X7=0), недоиспользование дизельного топлива составляет 40 087 кг (X6=40 087). Площадь посева технических культур определилась верхней допустимой границей (недоиспользование ‑ X5=0) и составляет 1000 га (X2+X3=1000).
, Х 
означают нормативы расхода производственных ресурсов на 1 га посева cсельскохозяйственных культур, а коэффициенты дополнительных переменных Х 
, Х 
, Х 
, Х 
образуют единичную матрицу.
,
,
,
,
.
,
,
,
.