Задачи линейного программирования

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

1. Целевая функция представляет собой взвешенную линейную сумму от неизвестных переменных x_i вида:

,

где c_i - известные коэффициенты. Такую целевую функцию часто называют линейной формой и обозначают буквой L.

2. Ограничения, накладываемые на область возможных решений, имеют вид линейных равенств или неравенств:

,

где a_ij, b_i - известные величины, причем величины a_ij, x_i, b_i положительные.

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

Задача 1.

Фирма - булочно-кондитерский комбинат (БКК) выпускает следующие виды продукции, перечисленные в таблице 1

Таблица 1

Номер продукции j	1	2	3	4	5
Наименование продукции	булки	пирожные	ватрушки	коржики	слоенки

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

Таблица 2

Номер ресурса i	1	2	3	4	5
Наименование ресурса	мука	сахар	масло	творог	яйца
Количество ресурса	200 кГ	50кГ	50 кГ	50 кГ	500 шт.

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

Таблица 3

Продукция j Ресурсы i	1 Булка	2 Пирожное	3 Ватрушка	4 Коржик	5 Слоенка
1 Мука, кГ	0,1	0,04	0,08	0,06	0,05
2 Сахар, кГ	0,01	0,05	0,02	0,04	0,03
3 Масло, кГ	0	0,05	0,01	0,02	0,02
4 Творог, кГ	0	0	0,05	0,02	0,03
5 Яйца, шт.	0,1	0,2	0,2	0,2	0,3

В таблице 4 приведена отпускная цена на единицу каждого вида продукции.

Таблица 4

Вид продукции j	1 Булка	2 Пирожное	3 Ватрушка	4 Коржик	5 Слоенка
Отпускная цена на ед. продукции Сj , руб	0,84	3,2	1,6	1,5	2,1

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

где C_j - цена единицы j - го вида продукции,

x_j - количество произведенного j - го вида продукции.

Ограничения на ресурсы задаются системой

где a_ij - количество i - го ресурса для производства единицы j - вида продукции (табл. 3.3),

b_i - количество i - го вида ресурса (табл. 2).

Задача 2.

Пусть имеется в наличии n различных средств связи (коротковолновые и ультракоротковолновые радиостанции, средства радиорелейной, проводной и спутниковой связи). Каждый из видов связи имеет свои преимущества и недостатки. Различен для них и показатель надежности, в качестве которого пусть используется коэффициент готовности К.

Для обеспечения высокой надежности связи создается комплекс средств связи, работающий в различной обстановке (работа в условиях помех, частая смена пунктов управления и др.). Будем считать, что число различных вариантов обстановки равно m.

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

Пусть известны:

• стоимость средств связи i - го типа

• значение коэффициентов готовности средств связи i - го типа при j - м

варианте обстановки

Если в комплексе средств связи используются x₁ средств первого типа, x₂ - второго и т.д., то для j - го варианта обстановки коэффициент готовности комплекса вычисляется по формуле

(1)

Суммарные затраты на создание и эксплуатацию комплекса средств связи равны

(2)

Задача определения оптимального комплекса средств связи сводится к нахождению такого набора параметров (x₁, x₂, ..., x_n), который обращает в минимум функцию (3.2), а сами параметры при этом удовлетворяют следующей системе ограничений:

1. коэффициент готовности комплекса средств связи при любом варианте обстановки не хуже К_ГК, т.е.

2. по физическому смыслу задачи параметры х_i не могут быть отрицательными, т.е. x₁ ³ 0, x₂ ³ 0, ¼, x_n ³ 0.

Ограничения первого типа нелинейны относительно параметров x_i, однако их легко преобразовать к линейным, если прологарифмировать величину 1- К_ГК. Введя обозначения:

окончательно можем сформулировать задачу определения оптимального комплекса средств связи как задачу линейного программирования: найти такие неотрицательные значения переменных x₁, x₂, ¼, x_n, удовлетворяющих системе ограничений

(3)

которые бы обращали в минимум линейную функцию (2).

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

Имеется m складов и n пунктов потребления. На складах имеется товара в количествах a₁, a₂, ¼, a_i, ¼, a_m единиц. Пункты потребления подали заявки на b₁, b₂, ¼, b_j, ¼,b_n единиц товара.

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

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

Требуется составить такой план перевозок, чтобы все заявки были выполнены, а общие расходы были минимальными. Решение (план перевозок) состоит из m´n чисел:

x₁₁, x₁₂, ¼ , x_1n;

x₂₁, x₂₂, ¼ , x_2n;

¼¼¼¼¼¼¼

x_m1, x_m2, ¼ , x_mn;

где х_ij - количество единиц товара, перевозимого с i - го склада в j - й пункт потребления.

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

x₁₁ + x₁₂ + ¼ + x_1n £ а₁;

x₂₁ + x₂₂ + ¼ + x_2n £ а₂; (4)

. . . . . . . . . . . . . . . . . . .

x_m1+ x_m2 + ¼ + x_mn £ а_m,

т.е. при планировании перевозок емкость складов не должна быть превышена:

x₁₁ + x₁₂ + ¼ + x_m1 = b₁;

x₂₁ + x₂₂ + ¼ + x_m2 = b₂; (5)

. . . . . . . . . . . . . . . . . . .

x_1n + x_2n + ¼ + x_mn = b_n,

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

L = c₁₁x₁₁ + c₁₂x₁₂ + ¼ + c_1nx_1n + c₂₁x₂₁ + c₂₂x₂₂ + ¼ +c_2nx_2n + ¼ + c_m1x_m1 + c_m2x_m2 + ¼ + c_mnx_mn . (6)

Необходимо так выбрать план перевозок , чтобы стоимость всех перевозок обратить в минимум. Таким образом снова возникает типичная задача линейного программирования: выбрать неотрицательные значения переменных х_ij так, чтобы при выполнении условия (4), (5) линейная функция этих переменных (6) достигала минимума. Некоторая особенность рассматриваемой задачи заключается в том, что не все ограничения являются линейными неравенствами, а именно, условия (5) записаны в виде линейных равенств.

Целый ряд задач из разных областей практики может быть сформулирован как задачи линейного программирования. Все они характеризуются некоторыми общими чертами. В каждой из них элементы решения представляют собой ряд неотрицательных переменных х₁, х₂, ¼, х_n . Требуется так выбрать значения этих переменных, чтобы:

1. выполнялись некоторые ограничения, имеющие вид линейных неравенств или неравенств относительно переменных х₁, х₂, ¼, х_n ;

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

Математический аппарат линейного программирования предназначен специально для решения таких задач. Дело в том, что классический метод отыскания экстремума: продифференцировать L по аргументам х₁, х₂, ¼, х_n , приравнять производную нулю и решить полученную систему уравнений, для рассматриваемого класса задач неприемлем. Так как функция L линейна, то производные от нее по всем аргументам постоянны и нигде в нуль не обращаются. Экстремум функции L, если он существует, достигает всегда на границе области значений х₁, х₂, ¼, х_n, т.е. там, где начинают действовать ограничения.

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