Формы записи ЗЛП, их эквивалентность и способы преобразования

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

Пример 2.1 (задача о банке). Пусть собственные средства банка в сумме с депозитами состав­ляют 100 млн долл. Часть этих средств, но не менее 35 млн долл. должна быть размещена в кредитах. Кредиты являются неликвид­ными активами банка, так как в случае непредвиденной потреб­ности в наличности обратить кредиты в деньги без существенных потерь невозможно. Другое дело ценные бумаги, особенно государственные. Их можно в любой момент продать, получив некоторую прибыль или, во всяком случае, без большого убытка. Поэтому существует пра­вило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы – ценные бумаги, чтобы компенсировать неликвидность кредитов. В нашем приме­ре ликвидное ограничение таково: ценные бумаги должны состав­лять не менее 30% средств, размещенных в кредитах и ценных бумагах.

Обозначим через – средства (млн долл.), размещенные в кредитах, – средства, вложенные в ценные бумаги. Согласно условию задачи имеем следующую систему линейных ограничений:

В этой системе ограничений неравенство (1) означает балансовое ограничение, неравенство (2) означает кредитное ограничение, неравенство (3) - ликвидное ограничение. Цель банка состоит в том, чтобы получить максиальную прибыль от кредитов и ценных бумаг. В результате получаем целевую функцию (функцию прибыли банка)

, (4)

где c₁ – доходность кредитов, с₂ – доходность ценных бумаг, причем так как кредиты менее ликвидны, чем ценные бумаги, то обычно полагают c₁ > с₂.

Итак, получена задача линейного программирования с ограни­чениями (1) – (3) и целевой функцией (4), которую требуется максими­зировать.

Пример 2.2 (задача об использовании ресурсов). Предприятие имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные ресурсы, площади и т.п. Допустим, что ресурсы трех видов имеются в количестве соответственно условных единиц. Предприятие выпускает три вида товаров . Причем известно, сколько единиц каждого ресурса требуется для производства единицы каждого товара. Пусть – число единиц ресурса R_i (i= 1, 2, 3), необходимое для производства единицы товара (j =1, 2, 3). Доход, получаемый предприятием от единицы каждого вида товаров, соответственно равен . Требуется при данных ресурсах выпустить такую комби­нацию товаров, при которой доход предприятия будет макси­мальным.

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

.

Общее количество ресурса (i= 1, 2, 3), используемого при выпуске товара (i= 1, 2, 3), равно . Оно не должно превосходить

запаса (i= 1, 2, 3), то есть

.

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

и максимизирующих целевую функцию дохода .

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

Предположим для определенности, что имеются два месторождения и три потребителя . Количество угля в месторождениях равны соответственно . Запросы потребителей равны соответственно . Считаем, что суммарные запасы равны суммарным потребностям (так называемое условие сбалансированности):

.

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

				Всего отправлено
Всего доставлено

Общее количество угля, вывезенное из месторождения () должно равняться (). Отсюда имеем условие

().

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

().

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

.

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

,

Заметим, что ТЗЛП – это особая задача линейного программирования, для решения которой (для нахождения оптимального плана перевозок) применяются специальные методы. Подробно с методами решения ТЗЛП мы познакомимся в главе 2.