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


Содержание лекционного занятия:

· Задача об оптимальном использовании ресурсов.

· Транспортная задача линейного программирования

Задача об оптимальном использовании ресурсов

Для изготовления двух видов продукции используется четыре вида ресурсов: В1, В2, В3, В4. Запасы ресурсов, затра­чиваемых на изготовление единицы продукции, приведены в табл. 1.

Вид ресурса

Запас ресурса

Число единиц ресурсов, затрачиваемых на изго­товление единицы продукции

Первый вид продукции

Второй вид продукции

В1

18

1

3

В2

16

2

1

В3

5

_

1

В4

21

3

-

На производство единицы продукции 1-го и II-го вида ис­пользуется различное количество ресурсов. Так, на произ­водство единицы продукции 1-го вида используется только одна единица ресурса В1, а на производство единицы про­дукции II-го вида используется 3 единицы ресурса В1 на производство единицы продукции 1-го вида используется 2 единицы ресурса В2, а на производство единицы продукции II-го вида используется 1 единица ресурса В2, в то же время на производство продукции 1-го вида ресурс В3 вообще не используется, а на производство продукции II-го вида не ис­пользуется ресурс В4.

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

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

Составим экономико-математическую модель задачи.

Пусть x1 — число единиц продукции первого вида, запла­нированное к производству;

x2 — число единиц продукции второго вида, запла­нированное к производству.

На их изготовление предприятию потребуется:

x1 + 3х2 единиц ресурса В1;

1 + х2 единиц ресурса B2;

х2 единиц ресурса В3;

1 единиц ресурса В4.

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

x1+3х2≤18
12 ≤16 (1)
Зх1 ≤21.

По смыслу задачи:

x 1≥0, х2≥0 (2)

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

Суммарная выручка от реализации продукции первого вида составит 2х1 , а от реализации продукции второго вида — 3x2. Таким образом, суммарная выручка от реализации обоих видов продукции составит:

F = 2х1 + 3х2 → max (3)

Требуется найти такой план выпуска продукции X=(x1, x2), который удовлетворял бы ограничениям (1) и (2) и при котором целевая функция F (3) принимала бы максимальное значение.

Эту задачу легко обобщить на n видов продукции и m видов ресурсов.

Обозначим через

x j — число единиц j-го вида продукции (j=l...n), запла­нированной к производству;

bi — запас i-го ресурса (i=l.. .m);

аij — число единиц ресурса i, затрачиваемого на изго­товление единицы продукции j-ro вида (аij часто называют технологическими коэффициентами);

cj— выручка от реализации единицы продукции j-ro вида (или цена продукции j-ro вида).

Тогда экономико-математическая модель задачи об ис­пользовании ресурсов в общей постановке примет вид: найти такой план X=(x1, x2,..., хn) выпуска продукции, ко­торый удовлетворял бы системе ограничений:

a 11x1+a12 x2+…+a1n xn≤b1

a21 x1+a22 x2+…+a2n xn≤b2

a31 x1+a32 x2+…+a3n xn≤b3

……………………………

am1 x1+am2 x2+…+amn xn≤bm

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

F = (c1 x1 +c2 x2 +c3 x3 + ...cn xn) →max.

Транспортная задача линейного программирования

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

все грузы из всех пунктов отправления были вывезены;

заявки всех пунктов назначения были бы удовлетворе­ны;

суммарные затраты на перевозку были бы минималь­ны.

Рассмотрим конкретный пример. Пусть имеется:

три пункта отправления: города под названием А1, А2, A3 , в которых сосредоточены запасы какого-либо товара (например машин) соответственно в количестве a1 =10, а2=20, а3=30;

три пункта назначения: города под названием В1, В2, В3, в которых сосредоточены потребители товара, же­лающие получить его в количестве в1 =10, в2=10, в3=40;

установлено, что сумма заявок всех городов — потре­бителей товара равна суммарному количеству товара, имеющегося в городах — поставщиках этого товара, т.е.:

а1 + а2 + а3 = в1 + в2 + в3 = 60

известна стоимость перевозки одной единицы товара (одной машины) из пункта отправления Аi в пункт на­значения Bj, т.е. задана матрица стоимостей перевозок:

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

Перейдем к математической формулировке этой задачи. Обозначим через хij - количество товара, который перево­зится из пункта отправления Ai в пункт назначения Bj (l£i£3, l£j£3).

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

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

Второе содержательное ограничение в данной задаче— все товары, содержащийся в каждом из пунктов от­правления, должны быть вывезены, возможно, в раз­личные пункты отправления. Математически это озна­чает, что должны выполняться следующие равенства:

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

Четвертое ограничение предполагает, что перевозимые товары не могут принимать отрицательные значения, т.е. xij ≥0.

Цель задачи — в минимизации перевозок. Математичес­ки это означает, что целевая функция

F = с11 х11 + с12 х12 +... + с33 х33 → min.

Таким образом, математически задача состоит в нахож­дении такого плана перевозок Х=(х11 ,x12 ,...,хmn), который удовлетворял бы системе ограничений и составлял бы ми­нимум целевой функции.

Отличительные особенности экономико-математической модели транспортной задачи:

система ограничений представляет собой систему уравнений;

в системе ограничений коэффициенты при переменных принимают только два возможных значения: либо 0, ли­бо 1;

каждая переменная входит в систему ограничений два раза.

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

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

Вопросы для самоконтроля:

1.Линейная задача оптимального управления и принцип максимума (минимума).

2. План решения задач оптимального управления.

Рекомендуемая литература:

1.Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высш. шк., 1986.

2.Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. М.: Наука, 1984.