 |
|
Симплекс метод на примере
Симплексный метод является универсальным методом решения задач линейного программирования.
Рассмотрим пример задачи линейного программирования.
Задача. Определить посевные площади зерновых, сахарной свеклы и подсолнечника в подразделении сельскохозяйственного предприятия, располагающего следующим объемом трудовых ресурсов: 2700чел.-дней, минеральными удобрениями в количестве 1200 ц.д.в. и под эти культуры отведено 580га пашни.
Требуется определить такое сочетание посевов зерновых культур, сахарной свеклы и подсолнечника, которое обеспечивало бы фермеру прибыль. Исходные данные заданы в таблице 1.
Таблица 1.
| Сельскохозяйственные культуры | Затраты на труд, чел.-дни удобрен. ц.д.в. | Прибыль с 1 га тенге | |
| Зерновые Свекла Подсолнечник | 0,9 | 1,7 1,6 | |
Решение задачи начинается с составления экономико-математической модели. Для этого необходимо условие задачи сформулированное в экономических терминах, записать в математической форме.
Введем следующие обозначения:
Х1-количество пашни, отведенной под зерновые, га;
Х2-количество пашни, отведенной под свеклу, га;
Х3-количество пашни, отведенной под подсолнечника, га.
Система ограничений записывается из условия, согласно которому затраты по каждому виду ресурсов не должны превышать имеющегося в наличии запаса этого ресурса
м Х1 + Х2+ Х3 Ј 580
н Х1 + 20Х2+ 0,9Х3 Ј 2700 (5.15)
о1,7Х1 + 4Х2+ 1,6Х3 Ј 1200
Целевая функция, которую требуется максимизировать, представляет собой сумму прибыли, получаемую от реализации продукции сельскохозяйственных культур.
Zmax=200X1+350X2+300X3 (5.16)
а также из экономического смысла задачи следует условие неотрицательности в их переменных, т.е.
Х1і0, Х2і0, Х3 і0 (5.17)
Приведем систему ограничений (5.15)-(5.17) к каноническому виду, вводя неотрицательные дополнительные переменные
м Х1 + Х2 + Х3 + Х4 = 580
н Х1 + 20Х2 + 0,9Х3 + Х5 = 2700 (5.18)
о1,7Х1 + 4Х2 + 1,6Х3 + Х6 = 1200
Дополнительные переменные Х4, Х5, Х6-экономически означают соответственно возможное недоиспользование пашни (Х4), трудовых ресурсов (Х5) и удобрений (Х6).
Недоиспользование ресурсов не приносит никакого дохода и поэтому в целевую функцию дополнительные переменные вводятся с нулевыми коэффициентами.
Zmax=200Х1+350Х2+300Х3+0Х4+0Х5+0Х6
Симплекс метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям.
Его идея состоит в следующем. Имея систему ограничений в канонической форме, находят любое базисное решение этой системы, заботясь лишь о том, чтобы найти его как можно проще.
Проверяют это решение на оптимальность. Если оно не оптимально, то осуществляется переход к другому базисному решению. Симплекс метод гарантирует, что при этом новом решении целевая функция, если не достигнет оптимума, то приблизится к нему. С новым базисным решением поступают так же, пока не находят оптимальное.
Найдем первый базисный план рассматриваемой задачи.
Надо искать решение, которое содержит 6-3=3 переменных, равных нулю. Обратим внимание, что коэффициенты при дополнительных переменных образуют единичную матрицу. Поэтому, если принять значения основных переменных, равными нулю (х1=0, х2=0, х3=0), получим первый базисный план: х4=580, х5=2700, х6=1200, F=0.
Этот план отвечает такому положению, при котором продукция не производится, ресурсы не используются и размер прибыли равен нулю. План явно является не выгодным. Для получения прибыли необходимо последовательно ввести в план основные переменные взамен дополнительных, пока не будет получено оптимальное решение.
Для удобства проведения технических расчетов модель задачи представлена в таблице в несколько преобразованном виде. Дальнейшее решение представим в виде таблицы 2.
Таблица 2
| № | базис | вi | х1 | х2 | х3 | х4 | х5 | х6 | Q |
| х4 | |||||||||
| х5 | 0.9 | ||||||||
| х6 | 1.7 | 1.6 | |||||||
| F | -200 | -350 | -300 |
В симплексной таблице вводится специальный столбец базисных переменных и свободные члены уравнений записываются слева от матрицы коэффициентов. Это создает удобства при чтении базисного плана.
Рассмотрим порядок заполнения первой симплексной таблицы.
Первая таблица получена непосредственно из канонической формы записи модели задачи. Каждая строка таблицы соответствует одному из уравнений системы. Последняя строка целевой функции соответствует записи целевой функции в форме уравнения, когда все члены с переменными перенесены в левую часть:
F - 200х1 - 350х2 - 300х3 - 0х4 - 0х5 - 0х6 =0
Последняя строка является оценочной или индексной. Во втором столбце записаны наименования базисных переменных. В третьем столбце находятся сами базисные переменные, то есть план.
Коэффициенты при основных переменных — это нормы расхода ресурсов. Коэффициенты при дополнительных переменных образуют единичную матрицу. Подчеркнем, что переменным входящим в базис, в матрице коэффициентов всегда соответствуют единичные векторы-столбцы.
Формальным признаком оптимальности плана при решении задач на максимум является отсутствие в индексной строке отрицательных величин. При решении задач на минимум, наоборот, в индексной строке не должно быть положительных коэффициентов.
В индексной строке первой симплексной таблицы имеются отрицательные коэффициенты. Следовательно, план не оптимален и его следует улучшить.
Переход к новому базисному плану называется симплексным преобразованием.
Поскольку задача решается на максимум прибыли, исходя из здравого смысла, целесообразно ввести в план посевы культуры, дающей наибольший размер прибыли. Для этого находим в индексной строке максимальное по абсолютной величине отрицательное число. Это число -350 и расположено в столбце х2. Оно означает, что введение в план посевов свеклы даст 350 тенге прибыли с 1га. Столбец, содержащий переменную х2, которую необходимо ввести в базис, называется направляющим (разрешающим, ведущим, генеральным, главным, ключевым и т.п.).
Теперь необходимо определить, в каком максимально размере могут быть предусмотрены посевы свеклы. Это зависит от объёмов ресурсов и нормативов затрат. Разделим величины столбца «план» (объёмы ресурсов) на коэффициенты направляющего столбца:
580/1=580га; 2700/20=135 га; 1200/4=300 га. (5.19)
Отношения (5.19) называются симплексным. Минимальное из них показывает, что посевы свеклы можно запланировать в размере, не превышающим 135га. Трудовые ресурсы являются «узким» местом, они лимитируют размеры посевов свекла.
Переменную х2 надо запланировать в таком объёме, чтобы одна из базисных переменных стала равной нулю (чтобы в базисе освободилось место для х2).
Если посеять 135га свеклы, то будут полностью использованы трудовые ресурсы, х5 станет равной нулю и ее следует вывести из базиса. Таким образом минимальное симплексное отношение определяет переменную, которая станет свободной. Соответствующая ей строка называется направляющей. Выделяем направляющую строку и столбец с помощью стрелок. Элемент, стоящий на их пересечении, называется направляющим. В таблице он заключен в рамку.
Теперь переходим к построению второй симплексной таблицы, то есть второго базисного плана. В начале вместо х5 в число базисных переменных вводим х2, остальные базисные переменные не меняются. При переходе к новому варианту плана в базис можно ввести только одну переменную и одну вывести.
Надо преобразовывать систему уравнений таким образом, чтобы у вводимой переменной х2 был единичный вектор-столбец. Для этого вначале рассчитаем строку вводимой переменной следующим образом. Она получается из направляющей строки первой симплексной таблицы путем деления всех ее элементов на направляющий элемент, то есть на число 20.
Остальные строки необходимо преобразовать так, чтобы в клетках направляющего столбца появились нули. То есть необходимо исключить х2 из других уравнений системы. Этого можно достичь с помощью метода Гаусса. Надо к каждой строке первой симплексной таблицы прибавить вновь полученную строку, умноженную на такое число, чтобы в клетке направляющего столбца появился нуль. Таким образом, первая таблица является расчетной базой для второй, вторая - для третьей и т.д., последующая таблица рассчитывается на основе предыдущей. Расчет и заполнение последующей таблицы всегда начинают со строки, которая соответствует разрешающей строке в предыдущей таблице, поэтому ее иногда называют начальной. Например заполняем строку х2, коэффициенты этой строки определяют путем деления каждого элемента предыдущей на разрешающий элемент.
2700:20=135; 1:20=0,05; 20:20=1; 0,9:20=0,045; 0:20=0;
1:20=0,05; 0:20=0.
По разрешающему столбцу в последующей таблице на место разрешающего элемента ставится единица, а на место других элементов - нули. Аналогично против самой себе базисной переменной – 1, а против других -0
Все остальные коэффициенты рассчитываются следующим образом:
Новое значение элемента, находящегося в i-й строке и в j -м столбце равно: старое значение элемента минус элемент матрицы, находящийся на пересечении i-й строки и разрешающего столбца и умноженное на элемент начальной строки последующей таблицы в j - м столбце.
Например, строка х4 заполняется по формуле х4-х2н, получим
580- 135=445; 1-0,05=0,95; 1-1=0; 1-0,045=0,955; 1-0=1;
0-0,05= -0,05; 0-0=0.
А строка х6 получим по формуле х6-4х2н,
1200-4х135=660; 1,7-4х0,05=1,5; 4-4=0; 1,6-4х0,045=1,42; 0-0;
0-4х0,05=-0,2; 1-4х0=1.
Строка целевой функции заполняется по формуле F+350x2; получим 0+135х350= 47250; -200+350х0,05=-182,5; -350+350х1=0; -300+350х0,045= -284,25; 0+350х0=0; 0+350х0,05=17,5; 0-0=0. Полученные коэффициенты запишем во второй таблице 3.
Таблица 3
| № | базис | вi | х1 | х2 | х3 | х4 | х5 | х6 | Q |
| х2 | 0.05 | 0.045 | 0.05 | ||||||
| х4 | 0.95 | 0.955 | -0,05 | 465,9 | |||||
| 3 | х6 | 1.5 | 1.42 | -0.2 | 464,8 | ||||
| F | -182.5 | -284.25 | 17.5 |
После составления ее проверяют план на оптимальность. Наличие отрицательных величин в индексной строке говорит о том, что решение не оптимально - его надо улучшить. Для этого повторяется вычислительная процедура, которая была разработана при переходе от первой таблицы ко второй.
Опять отыскиваются разрешающий столбец и разрешающая строка, а затем строится и рассчитывается третья симплексная таблица 4. Разрешающим столбцом является х3(-284,25) и разрешающей строкой является х6 (464,8).
Например, строка х3 вычисляется так: х6:1.42, получим
660: 1,42 =464,788; 1,5:1,42=1,06; 0:1,42=0; 1,42:1,42=1; 0:1,42=0;
-0,2:1,42=-0,14; 1:1,42=0,7.
А строка х2 получим по формуле х2-0,045х3:
135-464,78х0,045=114,08; 0,05-1,06х0,045=0,002; 1-0х0,045=1;
0,045-1х0,045=0; 0-0х0,045=0; 0,05-0,14х0,045=0,044; 0-0,7х0,045=-0,03. Вычисляем строку х4 по формуле х4-0,955х3: получим
445-0,955х464,78=1,12; 0,95-0,955х1,06=-0,06; 0-0,955х0=0; 0,955-0,955х1=0; 1-0х0,955=1; -0,05-0,955х0,14=-0,18; 0-0,955х0,7=-0,67. Строка целевой функции вычисляется по формуле F+284.25x3: 47250+464,78х284,25=179366; -182,5+1,06х284,25=118,8; 0+0х284,25=0; -284,25+1х284,25=0; 0+0х284,25=0;
17,5+284,25х0,14=57,3; 0+0,7х284,25=199.
Таблица 4
| № | базис | вi | х1 | х2 | х3 | х4 | х5 | х6 | Q |
| х3 | 464,788 | 1,06 | 0,14 | 0,7 | |||||
| х2 | 114,08 | 0,002 | 0,044 | -0,03 | |||||
| х4 | 1,12 | -0,06 | -0,18 | -0,67 | |||||
| F | 118,8 | 57,3 |
По последней таблице оптимальное решение соответствует оптимальному плану
Х1=0, Х2=114,08, Х3=464,78, Х4=1,12, Х5=0, Х6=0, Fmax=179366 тг.
Отсутствие отрицательных величин в индексной строке третьей симплексной таблицы свидетельствует о том, что данный план оптимальный. В него вошли посевы под свеклу и подсолнечник, в условиях данного хозяйства посев зерновых при заданной прибыли, получаемой с 1 га -200тг, невыгоден. Базисные переменные х4 характеризуют недоиспользование пашни на 1,12 га. Коэффициенты индексной строки по столбцу х1 имеют положительный знак. Они показывают, на сколько уменьшится сумма чистого дохода от посева одного гектара зерновых культур. Коэффициенты индексной строки по столбцам дополнительных неизвестных х5 и х6 показывают, на сколько уменьшится общая сумма чистого дохода при недоиспользовании 1 чел-дня (на 57,3 тг) и 1 ц удобрений (на 199 тг).