Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных переменных n - m > 3, а затруднительна уже при n - m = 3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.

Идея симплекс-метода относительно проста.

Пусть в задаче линейного программирования имеется п переменных и т независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР.), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то к переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных а

остальные m выражены через них:

(2.22)

Предположим, что все свободные переменные равны нулю.

При этом мы получим:

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные членынеотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию Z через свободные переменные

(2.23)

Очевидно, что приПроверим, может ли быть улучшено решение, т.е. получено уменьшение функции Z c увеличением каких-нибудь из переменных (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициентыв (2.23) положительны, то увеличение каких-либо из переменныхне может уменьшить Z; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентовесть отрицательные, то, увеличивая некоторые из переменных (те, коэффициенты при которых отрицательны), мы можем улучшить решение.

Пусть, например, коэффициентв (2.23) отрицателен. Значит, есть смысл увеличить, т.е. перейти от данного опорного решения к другому, где переменнаяне равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьследует с осторожностью, так чтобы не стали отрицательными другие переменныевыраженные через свободные переменные, в частности черезформулами (2.22).

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

Допустим, что это не так и что среди уравнений (2.22) есть такие, в которых коэффициент приотрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличение опасно - оно может сделать их отрицательными.

Возьмем одну из таких переменныхи посмотрим, до какой степени можно увеличить, пока переменнаяне станет отрицательной. Выпишемуравнение из системы (2.22):

Здесь свободный член, а коэффициентотрицателен.

Легко понять, что если мы оставим, томожно увеличивать только до значения, равногоа при дальнейшем увеличениипеременнаястанет отрицательной.

Выберем ту из переменныхкоторая раньше всех обратится в нуль при увеличениит.е. ту, для которой величинанаименьшая. Пусть это будетТогда имеет смысл разрешить систему уравнений (2.22) относительно других базисных переменных, исключая из числа свободных переменныхи переводя вместо нее в группу свободных переменныхДействительно, мы хотим перейти от опорного решения, задаваемого равенствамик опорному решению, в котором ужеа Первое опорное решение мы получили, положив равными нулю все прежние свободные переменныевторое мы получим, если обратим в нуль все новые свободные переменные

Базисными переменными при этом будут

Предположим, что уравнения типа (2.22) для нового набора базисных и свободных переменных составлены. Тогда можно выразить через новые свободные переменные и линейную функцию Z Если все коэффициенты при переменных в этой формуле положительны, то мы нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю.

Если среди коэффициентов при переменных есть отрицательные, то процедура улучшения решения продолжается: система вновь разрешается относительно других базисных переменных, и так далее, пока не будет найдено оптимальное решение, обращающее функцию Z в минимум.

Пример 2.7 Пусть имеется задача линейного программирования с ограничениями-неравенствами:

(2.24)

Требуется минимизировать линейную функцию

Приводя неравенства к стандартному видуи вводя добавочные переменныепереходим к условиям-равенствам:

(2.25)

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пусть в качестве свободных переменных выступают Положим их равными нулю и получим опорное решение:

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приотрицателен. Значит, увеличиваяможно уменьшить Z.

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

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

Выбирается переменная у, и вводится в число свободных вместоЧтобы разрешить систему (2.25) относительно поступим следующим образом. Разрешим первое уравнение (2.25) относительно новой базисной переменной

Это выражение подставляется вместово второе уравнение:

(2.26)

Что касается третьего уравнения, то оно, как не содержащее не изменится. Система (2.25) приведена к виду со свободными переменнымии базисными

Выразим функцию Z через новые свободные переменные:

(2.27)

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0.

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

Поменяем местами переменные - первую исключим из числа свободных, а вторую - включим. Для этого разрешим второе уравнение (2.26) относительнои подставимв первое уравнение. Получим следующий вид системы (2.25):

(2.28)

Выразим Z через новые свободные переменные:

(2.29)

Полагая , получим Z = - 10.

Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении (2.29) неотрицательны. Итак, оптимальное решение ОЗ найдено:

При таких значениях переменных линейная функция Z принимает минимальное значение:

Заметим, что в рассмотренном примере нам не пришлось искать опорное решение: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (2.25) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, повторно решая уравнения до тех пор, пока свободные члены не станут неотрицательными [7].

2.2.3 Описание входных и выходных данных

Входными данными для разработанной программы вид материально-денежных ресурсов, норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота, технологические коэффициенты в числовом виде, объем ресурсов в числовом виде и доход от продажи товаров на 1 тыс. руб. товарооборота. Выходными данными является ассортиментный план выпуска продукции, общая оптимальная доходность от реализации всей продукции и остатки нереализованных ресурсов.

2.2.4 Описание алгоритма

Описание алгоритма состоит из нескольких шагов:

формирования таблицы исходных данных и заполнение ее числовыми значениями;

формирование таблицы выходных данных, с установкой нужных формул в ячейках;

вызовы стандартной функции из меню Сервис > Solver, с заполнением таблицы и запуском на выполнение.

2.2.5 Состав технических и программных средств