Линейное программирование

      Пример 16.

      Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице 13.

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

      Таблица 13

      Решение. Предположим, что производится x₁ изделий А, изделий В и изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции

(48)

      при следующих условиях

(49)

(50)

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

(51)

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

(52)

(53)

      Как видно, задачи (48) – (50) и (51) – (53) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный  план производства изделий A, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (48) – (50) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице 14.

      Из  этой таблицы видно, что оптимальным  планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы 14 также видно, что оптимальным решением двойственной задачи является

      Таблица 14

      Переменные  и обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции.

      Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые  полностью используются при оптимальном  плане производства изделий. Поэтому  двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции  прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75=1345,75 руб. При этом числа, стоящие в столбце вектора таблицы 14, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг.

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

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

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

      Первое  ограничение двойственной задачи выполняется  как строгое неравенство. Это  означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи.

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

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

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

      Пример 20.

      В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1000 руб., а II вида – 3000 руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Зная что для установки одного комплекта оборудования I вида требуется 2 м² площади, а оборудования II вида – 1 м² площади определить такой набор дополнительного оборудования, которых дает возможность максимально увеличить выпуск продукции

      Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет x₁ комплектов оборудования I вида и комплектов оборудования II вида. Тогда переменные x₁ и должны удовлетворять следующим неравенствам:

(70)

      Если  предприятие приобретет указанное  количество оборудования, то общее увеличение выпуска продукции составит

(71)

      По  своему экономическому содержанию переменные x₁ и могу принимать лишь целые неотрицательные значения, т. е.

(72)

x₁, – целые. (73)

      Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (71) при вы полнении условий (70), (72) и (73). Так как неизвестные могут принимать только целые значения, то задача (70) – (73) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого прежде всего построим многоугольник решений задачи, состоящей в определении максимального значения линейной функции (71) при выполнении условий (70) и (72) (рис. 11). Координаты всех точек построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (70) и условию неотрицательности переменных (72). Вместе с тем условию (73), т. е. условию целочисленности переменных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (71) на многоугольнике OKEMNF, то координаты этой точки и определят оптимальный план задачи.

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

      В данном случае искомой является точка  E(1; 3), в которой целевая функция принимает максимальное значение Следовательно, координаты точки Е определяют оптимальный план задачи (70) – (73). В соответствии с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуск продукции, равное 14 ед. в смену.

      Пример 21.

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

      Решение. Введем переменную x_ij, значение которой равно 1, если при выполнении i–й работы используется j–й механизм, и равно 0 в противном случае. Тогда условия использования каждого механизма только на одной работе выражаются равенствами

(74)

а условия выполнения работы только одним  механизмом – равенствами

(75)

(76)

      Таким образом, задача состоит в определении  таких значений неизвестных  , удовлетворяющих системам уравнений (74) и (75) и условию (76), при которых достигается максимальное значение функции

(77)

      Сформулированная  задача является задачей целочисленного программирования.

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

(78)

при условиях

(79)

(80)

– целые  (81)

      Если  найти решение задачи (78) – (81) симплексным  методом, то оно может оказаться  как целочисленным, так и нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения  оптимального плана задачи (78) – (81) требуются специальные методы. В  настоящее время существует несколько  таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит описанный выше симплексный метод.