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

Задачи целочисленного программирования решаются в Excel теми же средствами, что и общие задачи линейного программирования. В отличие от задач линейного программирования, при решении задач целочисленного программирования необходимо добавить указание на то, что разыскиваемые оптимальные значения переменных могут принимать только целые значения. Для этого в окне "Добавление ограничения" нужно выбрать в списке, расположенном посередине, значение "цел", как показано в следующем примере.

Пример 2.3. На мебельной фабрике изготавливают столы, стулья и табуреты. На производство одного изделия требуется 1,5, 1 и 0,62 м³ древесины. При этом затраты рабочего времени при изготовлении стола составляют 5 машино-часов, стула − 1,5 машино-часа и табурета − 0,7 машино-часа. Всего для производства мебели фабрика может ежедневно использовать 12 м³ древесины. Оборудование может быть занято в течение 26 машино-часов. Прибыль от реализации стола, стула и табуретки равна 200, 30 и 15 руб. соответственно. Фабрика должна ежедневно производить не менее двух столов. На производство другой продукции ограничений нет. Требуется определить, какую продукцию и в каком количестве следует ежедневно изготавливать фабрике, чтобы прибыль от ее реализации была максимальной.

Решение.

Составим вспомогательную таблицу:

Определим переменные модели:

ежедневное производство столов (шт.);

 ежедневное производство стульев (шт.);

ежедневное производство табуретов (шт.).

Используя эти переменные, далее строим целевую функцию:

Запишем ограничения:

Решение в Excel:

Рис. 2.4. Решение задачи целочисленного программирования

Симплекс-метод решения ЗЛП

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

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

Стандартная форма задачи ЛП необходима, потому что она позволяет получить базисное решение (используя систему уравнений, порожденную ограничениями). Это (алгебраическое) базисное решение полностью определяет все (геометрические) крайние точки пространства решений. Симплекс-метод позволяет эффективно найти оптимальное решение среди всех базисных.

Стандартная форма ЗЛП

Задача, в которой требуется найти экстремум функции

при ограничениях

называется задачей линейного программирования, заданной в канонической (стандартной) форме.

Стандартная форма записи задачи ЛП предполагает выполнение следующих требований.

1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2. Все переменные неотрицательные.

3. Целевую функцию следует или максимизировать, или минимизировать.

Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств £ или ³) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных (балансных) переменных – остаточных или избыточных, которые связаны с неравенствами типа «£» или «³» соответственно.

Для неравенств типа «£» в левую часть неравенства вводится неотрицательная переменная. Например, в модели компании Mikks, ограничение на количество сырья С1 задается в идее неравенства .

Вводя новую неотрицательную переменную , которая показывает остаток (неиспользованное количество) сырья С1, это ограничение преобразуется в равенство

Неравенства типа «≥» в задачах ЛП обычно устанавливают нижнюю границу чего-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели «диеты» неравенство показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству , .

Положительное значение избыточной переменной  показывает превышение суточного производства добавки над минимальным значением 800 фунтов.

Пример 2.4.

Преобразуем следующую задачу ЛП в стандартную форму:

при выполнении следующих условий:

Для преобразования задачи в стандартную форму выполним следующие действия.

1. Вычтем из левой части первого неравенства дополнительную (избыточную) переменную  и затем умножим все неравенство на -1, для того чтобы правая часть неравенства стала положительной.

2. Добавим дополнительную (остаточную) переменную  к левой части второго неравенства.

3. Так как третье ограничение изначально записано в виде равенства, поэтому оставляем его без изменения.

Получаем следующую стандартную задачу линейного программирования.

при выполнении следующих условий:

Основы симплекс-метода

Рассмотрим общую ЗЛП с  ограничениями и  переменными, записанную в стандартной (канонической) форме

,

                                            (2.1)

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

Мы уже говорили, что оптимальное решение представляет собой одну из вершин многогранника допустимой области. Другими словами, оптимальное решение - это одно из базисных решений.

Получение одного из базисных решений основано на известном классическом методе решения систем линейных уравнений – методе Гаусса-Жордана.

Основная идея этого метода состоит в сведении системы  уравнений с  неизвестными к каноническому или ступенчатому виду при помощи элементарных операций над строками:

1) умножение любого уравнения системы на положительное или отрицательное число;

2) прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

При использовании первых  переменных такая система имеет следующий вид:

               (2.2)

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

Остальные  переменные называются небазисными переменными.

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

Определение. Базисным решением системы (2.2) называется решение, полученное при нулевых значениях небазисных переменных.

Например, в системе (2.2) одно из базисных решений задается как

                             (2.3)

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

Т.к. различные базисные решения системы (2.2) соответствуют различным вариантам выбора  из общего числа  переменных , то число допустимых базисных решений (угловых точек) не превышает .

Поэтому ЗЛП можно решать посредством перебора конечного числа угловых точек допустимого множества , сравнивая значения ЦФ в этих точках. Это наихудший вариант решения ЗЛП, т.к. требует огромного объема вычислений.

Пример: если  (задача небольшой размерности), то количество переборов составит  (кол-во вариантов).

Обычно .

Идея симплекс-метода (СМ) состоит в направленном переборе угловых точек допустимого множества  с последовательным уменьшением ЦФ . СМ разработал Дж. Данциг (американский ученый) в 1947 г. Этот метод называют также методом последовательного улучшения решения (плана). Гарантии результативности СМ обеспечиваются следующей теоремой.

Теорема (о конечности алгоритма симплекс-метода). Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Это решение может быть получено через конечное число шагов симплекс-методом, причем, начать можно с любого исходного базиса.