включающие симплексный алгоритм, выполняют подобные действия автоматически.
Переопределим нашу целевую функцию и ограничения следующим образом:
максимизировать 4
Z= +. 0,03V„ + 0,07 Wb .
0,1 И/ +0,3 «0,2 (9.20)
Первый шаг - преобразование неравенств в равенства с помощью дополнительных переменных, известных как свободные переменные. Так как эта задача содержит два неравенства, то нужно применить две свободные переменные. Поэтому, 0,11 + 0,310,2 преобразуется в выражение 0,1 Jf + 0,3 + s\ = 0,2, где $\ - свободная переменная. Она отражает уровень, до которого сумма 0,11 + 0,3 Wb находится ниже 0,2. Аналогично, Wa + WysX становится Wa + Wb + s2 - 1.
Таким образом, ограничения в виде неравенств преобразуются в ограничения в виде равенств следующим образом:
1. 0,1 Wa + 0,30,2 становится 0,1 Wa + 0,3 + s{ = 0,2
2. Wa + Wb<,l становится Wa + Wb + s2 = 1
Цель состоит в максимизации 0,03 Wa + 0.07 Wb.
Заметьте, что мы опустили ограничения неотрицательности, так как предполагается, что для симплексного метода переменные могут иметь только неотрицательные значения.
Одна из возможных, хотя и не оптимальная точка, определена как Wa = 0 и Wb = 0, т.е. как начало координат, потому что если ничего не инвестировалось в А и В и мы задаем s\ = 0,2 и s2 - 1, удовлетворяются оба ограничения в виде равенств. Назовем это предварительным возможным решением. Функция симплексного метода заключается в том, чтобы искать оптимальное решение посредством повторяемого движения от одного возможного решения к другому, лучшему возможному решению.
Следует отметить, что часто нелегко определить первоначальное возможное решение. Если все ограничения в виде неравенств имеют форму "<", первоначальным возможным реше-
нием служит начало координат. При наличии ограничения ">", это не будет верным. К счастью, путем искаженного обращения процедур, что нравится математикам, метод может быть направлен на самого себя, чтобы произвести свое собственное первоначальное возможное решение.
Таким образом, текущий вид задачи состоит в следующем:
максимизировать
Z = 0,03 Wa + 0,07 Wb
0,lWe + 0,3W4 + j, = 0,2 (9.21)
Wa+Wb + s2= 1.
При Wa = 0, Wb = 0, s\ = 0,2 и s2 = 1 решение равно Z = 0. Это первоначальное возможное решение. Далее метод продвигается через последовательность улучшающихся возможных решений до тех пор, пока не будет найдено лучшее. Для облегчения поиска лучшего решения представим исходную ситуацию в табличной форме
| | | | «2 | |
ограничение 1 | | | | | |
ограничение 2 | | | | | |
целевая функция | -0,03 | -0,07 | | | |
+-индикаторы-►
Нижняя строка представляет собой целевую функцию Мы установили цель в форме Z - 0,03 -0,07 Wb + 0s\ + 0- - 0. Первая и вторая строки показывают два ограничения, связанных с этой задачей. ПС представляет правую сторону неравенств.
Теперь мы должны дать определение базисных и небазисных переменных. Базисные переменные - это те, в столбцах которых содержатся только нули кроме одной единицы. Значит, в данном предварительном решении s\ и s2 являются базовыми переменными. Текущая величина этих переменных может быть найдена, -если посмотреть на правый столбец напротив элемента "один" в соответствующих столбцах. Отсюда текущая величина s\ составляет 0,2, а текущее значение 52-1.
Остальные переменные известны как небазисные переменные. В этом процессе небазисные переменные имеют текущее значение ноль.
При каждой итерации (шаге) процесса поиска одна базисная переменная преобразуется в небазисную переменную. В то же время какая-либо небазисная переменная преобразуется в базисную переменную (что называется вхождением в решение).
В каждом шаге процедуры поиска лучшего решения мы должны убедиться в том, что каждое ограничение содержит только одну базисную переменную. Алгоритм также требует, чтобы целевая функция была выражена с помощью небазисных переменных. Наше предварительное возможное решение удовлетворяет этим условиям.
Улучшение решения
Первым шагом в этом процессе служит определение одного элемента в целевой строке, который имеет знак минус. Мы выберем -0,03 (возможен выбор между -0,03 и -0,07). Столбец чисел, где находится -0,03, известен как основной.
Вспомним, что в первоначальной форме целевая функция имеет вид Z = 0,03 Wa + 0,07 Wb. В таблице Z выражена через текущие небазисные переменные, т.е. в таблице это соотносится с Z-0,03 Жд-0,07 Wb = 0. Так как в предварительном решении эти небазисные переменные имели нулевые значения и их коэффициенты в таблице отрицательны, мы видим, что Z возрастет, если увеличится Wa или Wb, т.е. если мы сделаем какую-то из них базисной. Имея возможность выбора, мы решили выбрать увеличение Wa.
Второй шаг заключается в следующем: используя только строки ограничений, разделим каждый элемент с правой стороны на соответствующий элемент из основного столбца. Это называется проверкой соотношений. Найдем показатель с минимальной неотрицательной величиной. Соответствующий элемент из основного столбца определяет основную строку, а элемент, находящийся на пересечении основного столбца и основной строки, называется основой.
Проведя проверку соотношений, мы обнаружили, что единица во втором ограничении является основой. Мы должны преобразовать эту основу в единицу, деля всю основную строку на себя саму. Однако в данном случае в этом нет необходимости, потому что основа уже равна единице.
Следующий шаг - преобразование всех остальных элементов основного столбца в нули с помощью прибавления или