Последняя симплексная таблица, содержащая оптимальное решение задачи, может быть использована для получения новых вариантов оптимального её решения без повторных расчетов по рассмотренному выше алгоритму симплексного метода. Корректировка оптимального решения задачи и получения на этой основе новых вариантов оптимального плана может быть достигнута путем внесения в него следующих изменений:
1) увеличением переменной, вошедшей в базис;
2) введением в базис дополнительной переменной, не вошедшей в него ранее;
3) введением в базис основной переменной, не вошедшей в базис ранее.
Выбор того или иного варианта корректировки оптимального плана, из числа вышеуказанных, обусловлен спецификой содержания данного плана. Поэтому применительно к конкретным задачам должны выбираться соответствующие характеру полученных оптимальных решений возможные варианты их корректировки.
Случай 1. Предусматривается увеличение значений основной переменной, вошедшей в базис.
Методику корректировки оптимального плана применительно к данному случаю рассмотрим на примере последней симплексной таблицы 3.14 задачи по определению оптимальных объемов трансформации естественных сенокосов в пашню и орошаемые культурные пастбища (ОКП) с целью получения максимального выхода валовой продукции (Zmax).
В случае увеличения основной переменной, вошедшей в базис, предусматривается следующий порядок действий при корректировке оптимального плана:
- в форму таблицы 3.15 (в столбцы 2,3) выписываются переменные, вошедшие в базис оптимального плана (Х3, Х4, Х5, Х6, Х2 из таблицы 3.14), со своими численными значениями (вi);
Таблица 3.14
Оптимальный план задачи по трансформации угодий
(последняя симплексная таблица)
| № п/п | Базис | Сi | вi | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | Х7 | Сумма |
| Х3 | -1 | -1 | |||||||||
| Х4 | 88,5 | 0,41 | -0,91 | ||||||||
| Х5 | -3,8 | ||||||||||
| Х6 | -0,81 | ||||||||||
| Х2 | 0,5 | ||||||||||
| m+1 |
- направление изменения (уменьшение или увеличения) переменных, вошедших в базис оптимального решения задачи, зависит от знаков коэффициентов структурных сдвигов, стоящих в столбце дополнительной переменной, выбранном для корректировки плана. Если в столбце есть отрицательные коэффициенты, то значения переменных, стоящих в базисе по их строкам, будут увеличиваться в процессе корректировки, а значения переменных, стоящих по строкам с положительными коэффициентами, будут уменьшаться. В нашем примере для корректировки оптимального плана выбран столбец дополнительной переменной Х6 (таблица 3.14, столбец 10);
- переменную, через коэффициенты столбца которой предусматривается корректировка оптимального плана, заносят в базис (таблицы 3.15 в столбец 2) с нулевым значением в столбце коэффициенты структурных сдвигов столбца данной переменной из оптимального плана (таблица 3.14, столбец 10) переписываются в графу 4 таблицы 3.15. На пересечении строки и столбца данной переменной (Х6) ставится -1;
- определяют наименьшее положительное частное от деления численных значений базисных переменных (столбец 3 таблицы 3.15) на соответствующие по строкам положительные коэффициенты структурных сдвигов столбца дополнительной переменной (Х6) выбранного для корректировки оптимального плана (столбец 4 таблицы 3.15). Результаты вычислений записывают в столбец 5.
В нашем примере таким наименьшим положительным числом является 215,8 (88,5׃0,41=215,8). В таблице 3.15 (столбец 5) оно выделено квадратом;
- определяют произведение выбранного наименьшего положительного отношения (215,8) на коэффициенты структурных сдвигов со своими знаками. Результаты записываются в графу 6 (таблицы 3.15);
- определяют откорректированные значения базисных переменных путем вычитания из прежних их значений (столбец 3) указанного произведения (столбец 6). Значения переменных при данных расчетах уменьшаются на величину, равную произведению минимального положительного отношения (215,8), на положительные коэффициенты структурных сдвигов и, соответственно, увеличиваются при умножении данного отношения на отрицательные коэффициенты.
Результаты расчетов записываются в графу 7 (таблица 3.15);
- выполняют анализ изменений в составе оптимального плана в результате его корректировки.
Таблица 3.15
Корректировка оптимального плана путем увеличения основной переменной Х1, вошедшей в базис (по столбцу дополнительной переменной Х6)
| i | Переменные, вошедшие в базисное решение | Значения базисных переменных | Коэффициенты переменной Х6 в последней симплексной таблице | Отношение (гр. 3׃гр. 4) | Произведение коэффициентов при Х6 на min отношение в гр. 5 | Расчетный вариант оптимального плана |
| Х3 | 1189,0 | -1 | - | -215,8 | 1189,0-(-158)=1404,8 | |
| Х4 | 88,5 | 0,41 | 215,8 | 88,5 | 88,5-88,5=0 | |
| Х5 | 1970,0 | -3,8 | - | -820,0 | 1970-(-820,0)=2790 | |
| Х1 | 771,0 | -0,81 | - | -174,8 | 771,0-(-174,8)=945,8 | |
| Х2 | 250,0 | 0,5 | 500,0 | 107,9 | 250,0-107,9=142,1 | |
| Х6 | -1 | - | -215,8 | 0-(-215,8)=215,8 | ||
| m+1 | 250,0 | - | 243520-53950=189570 |
Выполненные в таблице 3.15 расчеты показывают, что получен новый откорректированный вариант оптимального плана. В результате корректировки оптимального плана площадь естественных сенокосов, трансформируемых в пашню (Х1), увеличилась на 174,8 га, а в орошаемые культурные пастбища (Х2) сократилась на 107,9 га. Нетрансформированная площадь естественных сенокосов в целом (Х3) и пригодных для трансформации в ОКП (Х6) увеличилась на 215,8 га. Недоиспользованные капитальные вложения на трансформацию (Х4) равны нулю, а недоиспользованные трудовые ресурсы (Х5) увеличились на 820 чел./дней. Данные изменения обусловили сокращение стоимости валовой продукции (Zmax) на 53950 тыс. руб.
Случай 2. Предусматривается введение в базис дополнительной переменной, невошедшей в него ранее.
Порядок выполнения расчетов по корректировке оптимального плана применительно к данному случаю мало отличается от предыдущего.
Отличительной особенностью расчетов в рассматриваемом случае является то, что в столбце 5 определяют наименьшее отрицательное частное от решения численных значений базисных переменных (столбец 3) на отрицательные коэффициенты структурных сдвигов столбца дополнительной переменной (в нашем примере та же Х6). Величина частного от деления определяет допустимое значение, которое может принять вводимая дополнительная переменная.
Во втором случае корректировка оптимального плана выполнена на том же примере с целью уяснения отличий в методике расчетов от рассмотренного первого случая.
Расчеты сведены в таблицу 3.16.
В результате корректировки оптимального плана площадь естественных сенокосов, трансформируемых в пашню (Х1), сократилась на 419,9 га, а в ОКП (Х2) увеличилась на 259,2 га. Нетрансформированная площадь естественных сенокосов (Х3) сократилась на 518,4 га. Недоиспользованные капитальные вложения (Х4) увеличились на 212,5 тыс. руб., а трудовые ресурсы (Х5) использованы полностью.
Стоимость валовой продукции увеличится на 129600 тыс. руб.
Таблица 3.16
Корректировка оптимального плана путем введения в базис
дополнительной переменной (Х6), не вошедшей в него ранее
Случай 3. Предусматривается введение в базис основной переменной, не вошедшей в него ранее.
Отличительной особенностью данного случая является то, что вводится основная переменная, не вошедшая ранее в базис, и для корректировки оптимального плана используется коэффициенты замещения её столбца. Допустимое значение основной переменной, вводимой в базис, определяется по наименьшему соотношению значений базисной переменной и соответствующего положительного коэффициента структурных сдвигов.
Порядок расчетов по корректировке оптимального плана в данном случае практически не отличается от рассмотренного в первом случае.
В качестве примера в таблице 3.17 выполнена корректировка оптимального плана, полученного при решении задачи симплексным методом.
Таблица 3.17
Корректировка оптимального плана путем введения в базис
основной переменной (Х3), не вошедшей в него ранее
| i | Переменные, вошедшие в базисное решение | Значения базисных переменных | Коэффициенты переменной Х6 в последней симплексной таблице | Отношение (гр. 3׃гр. 4) | Произведение коэффициентов при Х6 на min отношение в гр. 5 | Расчетный вариант оптимального плана |
| Х4 | 51,99 | 0,799 | 65,06 | 5,33 | 51,99-5,33=46,66 | |
| Х1 | 15,99 | 2,398 | 6,67 | 15,99 | 15,99-15,99=0 | |
| Х6 | 18,01 | -1,799 | - | -12,0 | 18,01-(-12,0)=30,0 | |
| Х3 | -1 | - | -6,67 | 0-(-6,67)=6,67 | ||
| m+1 | 319,91 | 17,98 | - | 119,93 | 319,91-119,93=199,98 |
Анализ изменений в результате корректировки оптимального плана в данном случае выполняется аналогично рассмотренному выше.
Задания для самостоятельной работы студентов по решению задач симплексным методом с искусственным базисом представлены в приложении 4.