5. Задача о производстве сложного оборудования.

Планируется производство сложного оборудования, каждый комплект которого состоит из элементов:

Заказы на производство этих элементов могут быть размещены на разных предприятиях:

В течение заданного времени Т на предприятии можно изготовить элементов типа .

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

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

Обозначим долю времени Т, которую предприятие будет уделять производству элемента (если этот элемент на данном предприятии вообще не производится,

При планировании мы должны соблюдать следующие ограничительные условия: количество времени, которое каждое предприятие затрачивает на производство всех элементов, не должно превышать общего запаса времени Т (а «доля» — единицы):

или

Определим количество полных комплектов оборудования, которое за время Т поставят все предприятия вместе.

Общее количество элементов которое произведут все предприятия вместе, будет равно

или

Таким образом, при заданном плане распределения заказов, т. е. при заданных будет произведено:

экземпляров элемента

Сколько же полных комплектов оборудования можно собрать из этих элементов? Очевидно столько, каково минимальное из всех чисел Действительно, если, например, элементов типа Э, произведено 100 шт., а элементов типа — всего 10 шт., то мы никак не сможем собрать из этих элементов более 10 полных комплектов.

Обозначим Z — количество полных комплектов оборудования, которое можно собрать при данном плане размещения заказов . Имеем:

где знаком обозначается минимальное из чисел, стоящих под этим знаком, для всех возможных

С учетом (1.18), условие (1.19) можно переписать в виде

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

Найти такие неотрицательные значения переменных чтобы выполнялись неравенства (1.17) и при этом обращалась в максимум функция этих переменных

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

Так как величина Z является минимальной из всех величин то можно написать ряд неравенств

Величину Z можно рассмотреть как новую неотрицательную переменную и решить следующую задачу.

Найти такие неотрицательные значения переменных чтобы они удовлетворяли линейным неравенствам (1.17) и (1.21) и при этом величина Z обращалась в максимум.

Так как величина Z есть линейная функция новых переменных

то задача сведена к обычной задаче линейного программирования, путем введения «лишней» переменной Z, которая в первоначальной постановке задачи не фигурировала.

Задачи такого типа, где требуется обратить в максимум минимальное значение какой-то величины (или, наоборот, в минимум — максимальное), довольно часто встречаются на практике и называются «задачами на минимакс». Стакими задачами мы еще встретимся в гл. 10.

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

Требуется так выбрать значения этих переменных, чтобы

1) выполнялись некоторые ограничения, имеющие вид линейных неравенств или равенств относительно переменных

2) некоторая линейная функция L тех же переменных обращалась в максимум (минимум).

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

Может возникнуть вопрос: а нужен ли такой специальный аппарат? Нельзя ли, как это принято в математике, просто продифференцировать L по аргументам приравнять производные нулю и решить полученную систему уравнений?

Нет, оказывается, сделать этого нельзя! Так как функция L линейна, производные от нее по всем аргументам постоянны и нигде в нуль не обращаются. Максимум (или минимум) функции L, если он существует, достигается всегда где-то на границе области возможных значений т. е. там, где начинают действовать ограничения.

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