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

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

— показатель эффективности W представляет собой линейную функцию от элементов решения;

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

Такие задачи принято называть задачами линейного программирования.

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

Задача о пищевом рационе.

Имеется четыре вида продуктов питания:

Известна стоимость единицы каждого продукта:

Из этих продуктов необходимо составить пищевой рацион, который должен содержать:

Единица продукта содержит единиц белков, единиц углеводов, единиц жиров и т. д. Содержание элементов в единице каждого продукта задано таблицей (табл. 1.1).

Требуется так составить пищевой рацион, чтобы обеспечить заданные условия (1.1) при минимальной стоимости рациона.

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

количества продуктов входящих в рацион.

Таблица 1.1

Очевидно, общая стоимость рациона будет

или короче

(1.2)

Запишем математически условия (1.1). В одной единице продукта содержится единиц белка, значит, в единицах — единицах продукта содержится единиц белка и т. д. Общее количество белков, содержащееся в рационе, не должно быть меньше отсюда получаем первое условие-неравенство:

Записывая аналогичные условия для углеводов и жиров, получим, включая (1.3), три условия-неравенства:

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

Возникает следующая задача:

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

обращалась бы в минимум.

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

Задача о загрузке станков.

Ткацкая фабрика располагает М, станками типа 1 и станками типа 2. Станки могут производить четыре вида тканей:

Каждый тип станка может производить любой из видов тканей, но в неодинаковом количестве. Станок типа 1 производит в месяц метров ткани метров ткани метров ткани метров ткани Соответствующие числа для станка типа 2 будут Таким образом, производительности станков при производстве каждого вида ткани заданы табл. 1.2.

Таблица 1.2

Каждый метр ткани приносит фабрике доход ткани — доход ткани — доход и ткани — доход Фабрике предписан план, согласно которому она обязана произвести за месяц:

не менее метров ткани не менее метров ткани не менее метров ткани и не менее 64 метров ткани т. е. плановое задание выражается числами

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

Запишем условия задачи математически. Обозначим — число станков типа 1, занятых производством ткани — число станков типа 1, занятых производством ткани и вообще число станков типа I, занятых производством ткани Т. Первый индекс соответствует типу станка, второй — виду ткани.

Таким образом возникают восемь переменных — элементов решения:

которые мы должны выбрать так, чтобы месячная прибыль была максимальна. Запишем формулу для вычисления этой прибыли. Каждый метр ткани приносит прибыль метров ткани принесут прибыль всего ткань принесет прибыли и т. д. Общая прибыль будет равна:

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

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

2) Задания по ассортименту должны быть выполнены (или перевыполнены). С учетом данных табл. 1.2 эти условия запишутся в виде неравенств:

Таким образом, сформулирована задача:

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

Задача о распределении ресурсов.

Имеются какие-то ресурсы (сырье, рабочая сила, оборудование):

в количествах соответственно

единиц. С помощью Этих ресурсов могут производиться товары:

Для производства одной единицы товара необходимо единиц ресурса. Каждая единица ресурса стоит рублей. Каждая единица товара может быть реализована по цене

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

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

количества товаров которые мы запланируем к производству. Условия спроса налагают на эти величины ограничения:

Ресурсов должно хватить, отсюда возникают ограничения:

Эти же условия можно короче записать в виде:

Выразим прибыль L в зависимости от элементов решения

Себестоимость единицы товара равна

или, короче,

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

Чистая прибыль получаемая от реализации одной единицы товара равна разнице между ее продажной ценой и себестоимостью

По этой формуле получаем чистые прибыли на единицу для всех товаров:

Общая чистая прибыль от реализации всех товаров будет

или, короче,

Задача сводится к следующему:

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

Задача о перевозках.

Имеются складов:

и пунктов потребления:

(см. рис. 2.1).

Рис. 2.1

Речь идет о составлении плана перевозок со складов в пункты некоторого товара. На складах имеются запасы товара в количествах

единиц. Пункты потребления подали заявки соответственно на

единиц товара. Заявки выполнимы, т. е. сумма всех заявок не превосходит суммы всех имеющихся запасов:

Склады связаны с пунктами потребления какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки одной единицы товара со склада С; в пункт равна

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

Обозначим — количество единиц товара, направляемое со склада в пункт (если с этого склада в этот пункт товары не направляются,).

Решение (план перевозок) состоит из чисел

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

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

или, короче,

2. Заявки, поданные пунктами потребления, должны быть выполнены:

или, короче,

Общая стоимость перевозок L будет равна

или, гораздо короче,

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

Снова возникает задача, аналогичная рассмотренным ранее: выбрать неотрицательны значения переменных так, чтобы при выполнении условий (1.14), (1.15) линейная функция этих переменных (1.16) достигала минимума.

Некоторая особенность этой задачи, по сравнению с ранее рассмотренными, состоит в том, что не все ограничения, наложенные на переменные, являются линейными неравенствами; а именно, условия (1.15) записаны в виде линейных равенств.

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

Заметим, что при некоторой постановке задачи о перевозках все условия-ограничения задачи становятся равенствами. А именно, если сумма всех заявок равна сумме всех запасов

то неизбежно с каждого склада будет вывезено все, что на нем имеется, и неравенства (1.14), так же как (1.15), превратятся в равенства.

Такая задача о перевозках называется транспортной задачей, и ею мы будем специально заниматься в дальнейшем (см. § 9—14 данной главы).

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

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

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

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

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

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

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

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

или

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

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

или

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

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

Сколько же полных комплектов оборудования можно собрать из этих элементов? Очевидно столько, каково минимальное из всех чисел Действительно, если, например, элементов типа Э, произведено 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 обращается в максимум или в минимум.