Корректировки решения задач симплекс-методом

1 2 3

Задача 11.

Фермер выращивает картофель, капусту и морковь. Ресурсы фермерского хозяйства:

пашня – 85 га;

трудовые ресурсы – 1140 чел. дней;

минеральные удобрения – 2600 кг действующего вещества (кг д.в.).

Расход ресурсов на единицу площади (1 га) и эффективность выращивания культур представлены в таблице.

Таблица 61 – Расход ресурсов на 1 га и прибыль с единицы площади

Показатели	Культуры
картофель	капуста	морковь
Расход на 1 га: пашни, га
труда, чел. дней
удобрений, кг д.в.
Прибыль на 1 га, д.ед.

Площадь картофеля может находиться в пределах 40 – 70 га. В свою очередь, площадь капусты не может превышать 50 га, а моркови – 25 га.

Рассчитать оптимальную структуру посевных площадей, которая позволит получить максимум прибыли.

Введем неизвестные:

X₁– площадь картофеля, га

X₂– площадь капусты, га

X₃– площадь моркови, га.

Тогда экономико-математическая модель задачи включает 7 ограничений.

1X₁+ 1X₂+ 1X₃≤ 85

10X₁+ 15X₂+ 20X₃≤ 1140

30X₁+ 25X₂+ 15X₃≤ 2600

1X₁≥ 40

1X₁≤ 70

1X₂≤ 50

1X₃≤ 25

Целевая функция – максимум прибыли со всей площади:

F_max = 12X₁+ 10X₂+ 5X₃

Исходная симплексная таблица представлена ниже.

Таблица 62 – Исходная симплексная таблица задачи 11

БП	СЧ	НБП
X₁	X₂	X₃
Y₁
Y₂
Y₃
Y₄	-40	-1
Y₅
Y₆
Y₇
F_max		-12	-10	-5

В результате нескольких переходов получен оптимальный план.

Таблица 63 – Оптимальный план задачи 11

БП	СЧ	НБП
Y₅	Y₁	X₃
X₂		-1
Y₂			-15
Y₃		-5	-25	-10
X₁
Y₅
Y₆			-1	-1
Y₇
F_max

Согласно оптимального плана фермеру целесообразно занять картофелем 70 га, а под капусту отвести 15 га. Это даст возможность получить 990 денежных единиц прибыли. Земельные ресурсы в этом случае будут использованы полностью. Напротив, трудовые ресурсы и минеральные удобрения дефицитными не являются. Остаток трудовых ресурсов составит 215 чел. дней, а минеральных удобрений – 125 кг.

Из оптимального плана видно, что фермеру нецелесообразно выращивать морковь. Однако предположим, что площадь данной культуры должна составить 10 га, т.е. необходимо выполнить корректировку оптимального решения по основной небазисной переменной (это первый вид корректировки).

Первоначально следует определить максимально возможную величину корректировки. С этой целью необходимо рассчитать все положительные отношения коэффициентов столбца СЧ на соответствующие коэффициенты столбца X₃ (X₃ – это площадь моркови). Из полученных отношений необходимо выбрать минимальное. Таким образом,

Поскольку, максимально возможная величина корректировки превышает желаемую величину (⌂X₃ = 10), то оптимальный план может быть изменен в нужном направлении с помощью несложных вычислений. Общая формула корректировки имеет вид:

X_j^k (Y_i^k)- значения базисных основных (дополнительных переменных после корректировки;

X_j (Y_i) - значения тех же переменных до корректировки;

a_ij - коэффициенты столбца, который используется для корректировки;

⌂X_j (⌂Y_j)- величина корректировки по основной (дополнительной переменной).

Используя вышеприведенную формулу, получим новое решение:

X₂^k=15 - 1∙10 = 5

Y₂^k=215 - 5∙10 = 165

Y₃^k=125 – (-10)∙10 = 225

X₁^k=70 - 0∙10 = 70

Y₄^k=30 – 0∙10 = 30

Y₆^k=35 – (-1)∙10 = 45

Y₇^k=25 - 1∙10 = 15

F_max^k=990 - 5∙10 = 940

А также нужно помнить, что X₃^k=10.

Пусть необходимо скорректировать оптимальный план и увеличить площадь моркови до 20 га (это превышает максимально возможную величину). Тогда, применив соответствующую формулу, получим, что X₃^k=15 - 1∙20 =- 5. Как известно, площадь не может быть отрицательной и, следовательно, такая корректировка не имеет смысла.

Корректировка оптимального решения по дополнительным небазисным переменным – второй вид корректировки.

Мы знаем, что дополнительные переменные вводятся по каждому ограничению. В частности, переменная Y₁ соответствует ограничению по использованию пашни. В оптимальном плане переменная Y₁ является небазисной. Это означает, что вся площадь пашни в количестве 85 га была использована полностью.

Предположим, что нам необходимо выполнить корректировку по дополнительной переменной Y₁.Здесь возможны 2 варианта: когда площадь пашни уменьшается и когда она увеличивается.

Рассмотрим первый вариант. Допустим, что площадь пашни в фермерском хозяйстве сокращается на 5 га, т.е. должна составить 80 га. Определим максимально возможную величину корректировки. Для этого находим все положительные отношения коэффициентов столбца СЧ на соответствующие коэффициенты столбца Y₁. В нашем случае только одно такое отношение (15:1 = 15). Следовательно, максимальная величина корректировки по столбцу Y₁ составит 15. При наличии нескольких положительных отношений необходимо выбрать минимальное. Учитывая, что требуемая величина корректировки (⌂Y₁ = 5) не превышает максимально возможную (⌂Y₁ = 15), то оптимальный план может быть скорректирован. С помощью известной формулы находим новое решение:

X₂^k=15 - 1∙5 = 10

Y₂^k=215 – (-15)∙5 = 290

Y₃^k=125 – (-25)∙5 = 250

X₁^k=70 - 0∙5 = 70

Y₄^k=30 – 0∙5 = 30

Y₆^k=35 – (-1)∙5 = 40

Y₇^k=25 - 0∙5 = 25

F_max^k=990 - 10∙5 = 940

Теперь рассмотрим обратную ситуацию: предположим, что площадь фермерского хозяйства должна увеличиться на 10 га (⌂Y₁= -10). Определим максимально возможную величину корректировки. Для этого необходимо выбрать отрицательные отношения коэффициентов столбца СЧ на соответствующие коэффициенты столбца Y₁. В результате имеем:

или {-14,33; -5; -35}.

Из полученных отношений выбираем минимальное по модулю (-5), которое и является максимально возможной величиной корректировки. Однако, необходимая величина корректировки по модулю (|-10| = 10) превышает модуль максимально возможной величины (|-5| = 5). Следовательно, в этом случае корректировка не возможна.

Предположим, что площадь пашни возрастает на 5 га. В этом случае после проведения корректировки получим новый план:

X₂^k=15 - 1∙(-5) = 20

Y₂^k=215 – (-15)∙(-5) = 140

Y₃^k=125 – (-25)∙(-5) = 0

X₁^k=70 - 0∙(-5) = 70

Y₄^k=30 – 0∙(-5) = 30

Y₆^k=35 – (-1)∙(-5) = 30

Y₇^k=25 - 0∙(-5) = 25

F_max^k=990 - 10∙(-5) = 1040.

После корректировки прибыль увеличилась, что связано с более полным использованием ресурсов.

Корректировка по базисным переменным (основным и дополнительным) – третий вид корректировки.

Согласно оптимального плана площадь картофеля составляет 70 га. Однако, допустим, что ситуация изменилась и нам необходимо уменьшить площадь данной культуры до 60 га. Прежде всего, среди небазисных переменных необходимо выбрать ту, которая позволит нам скорректировать решение. Пусть это будет переменная X₃ (она выбирается произвольно). Тогда, используя общую формулу корректировки, получим:

X₁^k= X₁ - 0·⌂ X₃ или 60 = 70 - 0·⌂X₃

Анализ показывает, что невозможно подобрать значение ⌂X₃, которое обращает данное выражение в равенство. Следовательно, переменная X₃ не может быть взята нами для корректировки. Небазисная переменная Y₁ нас также не устраивает.

Попытаемся скорректировать оптимальный план с помощью небазисной переменной Y₅. Подставив известные значения в формулу корректировки, получим:

60 = 70 - 1·⌂Y₅. Отсюда, ⌂Y₅ = 10.

В результате мы определили величину корректировки по столбцу Y₅ (⌂Y₅ = 10). И теперь нужно рассчитать максимально возможную величину корректировки по этому столбцу. Дальнейшие операции нам уже известны:

‌X₂^k=15 – (-1)∙10 = 25

Y₂^k=215 – 5∙10 = 165

Y₃^k=125 – (-5)∙10 = 175

X₁^k=70 - 1∙10 = 60 и т.д.

Таким образом, корректировка по базисным переменным сводится к корректировке по небазисным переменным. Это возможно потому, что все коэффициенты симплексной таблицы взаимоувязаны друг с другом.

Выполним еще одну корректировку. Допустим, что фермер решил полностью использовать минеральные удобрения (согласно оптимального плана остаток удобрений составляет 125 кг). Выберем для корректировки небазисную переменную Y₁ и с помощью общей формулы найдем значение ⌂Y₁:

0 = 125 – (-25)∙ ⌂Y₁. Отсюда ⌂Y₁= -5.

Отсюда следует, что для решения проблемы необходимо площадь пашни увеличить на 5 га. Остается определить максимально возможную величину корректировки по столбцу

Y₁. Для этого, по столбцу Y₁ рассчитаем отрицательные симплексные отношения:

Минимальное по модулю отношение (-5) является искомой величиной. Необходимая величина корректировки по модулю (‌‌‌‌‌‌‌‌‌‌‌-5) не превышает (в нашем случае равна) модуль максимальной величины корректировки по столбцу Y₁. Следовательно, оптимальный план может быть скорректирован: