Общая задача линейного программирования

Дана система т линейных уравнений и неравенств с п перемен­ными

и линейная функция

F = C\X\ + c₂x₂ +...+ c„x„, (1.21)

Необходимо найти такое решение системы Х= (х\, х₂,..., Хр..., х„), где

х, > 0(/=1, 2,..., /; /< «), (1.22)

при котором линейная функция F (1.21) принимает оптимальное (т.е. максимальное или минимальное) значение.

Система (1.20) называется системой ограничений, а функция F — линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

п F ⁼ £ ^cj^xj -> max (или -> min)

7=1

при ограничениях:

и

5> _/ух, - ^b_t{i = \, 2,..., k),. И

л

Y.OtjXj =bi(i = k + l, k + 2,..., m),

.7=1

^•> 0(М, 2,..., /; 1< п).

Оптимальным решением (или оптимальным планом) задачи ли­нейного программирования называется решение Х= (х\, х₂,..., Xj, •■ ■, ^хп) системы офаничений (1.20), удовлетворяющее условию (1.22), при котором линейная функция (1.21) принимает опти­мальное (максимальное или минимальное) значение.

Термины " решение" и " план" — синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи t (ее математическом решении), а второй — о содержательной сто­роне (экономической интерпретации).

При условии, что все переменные неотрицательны (Xj> 0, у'=1, 2,..., л), система офаничений (1.20) состоит лишь из одних неравенств, — такая задача линейного профаммирования называется стандарт­ной; если система офаничений состоит из одних уравнений, то зада­ча называется канонической^. Так, в приведенных выше примерах задач линейного профаммирования задачи 1 и 2 — стандартные, задача 4 — каноническая, а задача 3 — общая.

Любая задача линейного профаммирования может быть сведе­на к канонической, стандартной или общей задаче. Рассмофим вначале вспомогательную теорему.

Теорема 1.1. Всякому решению {а\, а₂,..., а_п) неравенства

а/1*1+а/2*2⁺-⁺а//Л» £ */ (1-23)

соответствует определенное решение (оц, а₂,.-., а_п; а_я+/) уравнения

a_nxi+a_ax₂+...+a_inx„ +x_n+i = b_h (1.24)

в котором

x„_+i> 0 (1.25)

и, наоборот, каждому решению (а_ь а₂,..., а„; а_я+() уравнения (124) и неравенства (1.25) соответствует определенное решение (ct], a₂,..., ос„) неравенства (1.23).

1 В ряде работ по математическому профаммированию стандартную задачу называют симметричной, а каноническую — основной.

Глава 1

Общая пост ановка задач

Используя эту теорему (которую принимаем без доказательст­ва), представим в качестве примера стандартную задачу (1.4)— (1.6) в каноническом виде. С этой целью в каждое из т нера­венств системы ограничений (1.4) введем дополнительные неот­рицательные переменные х„+\, х_п+2,..., х„+_т и система ограниче­ний (1.4) примет вид:

а_их₁+а_пх_г+...+а_1пх„ +х_л+1 -6,,

a_2lx_i+a₂₂x₁+...+a₂„x„ +х_п+2 = Ь_ъ

(1.26)

a_m, Xi +a_mlXi+...+a_mnx

Таким образом, стандартная задача (1.4)—(1.6) в канонической форме: найти такое решение Х- {х\, х₂,..., х_п, х_п+\,..., х„_+т), удов­летворяющее системе (1.26) и условию (1.5), при котором функция (1.6) принимает максимальное значение.

Замечание. В рассматриваемой задаче все неравенства вида " s", поэтому дополнительные неотрицательные пере­менные вводились со знаком " +". В случае неравенства ви­да " > ", как, например, в задаче (1.10) — (1.12), соответст­вующие дополнительные переменные следовало бы ввести со знаком " -".

УПРАЖНЕНИЯ

В задачах 1.4—1.7 составить экономико-математические моде­ли.

1.4. Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.

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

1.5. Рацион для питания животных на ферме состоит из двух
видов кормов I и II. Один килограмм корма I стоит 80 ден. ед. и
содержит: 1 ед. жиров, 3 ед. белков, 1 ед. углеводов, 2 ед. нитра­
тов. Один килограмм корма II стоит 10 ден. ед. и содержит 3 ед.
жиров, 1 ед. белков, 8 ед. углеводов, 4 ед. нитратов.

Составить наиболее дешевый рацион питания, обеспечиваю­щий жиров не менее 6 ед., белков не менее 9 ед., углеводов не менее 8 ед., нитратов не более 16 ед.

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

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

1.7. Необходимо распилить 20 бревен длиной по 5 м каждое на бруски по 2 м и 3 м; при этом должно получиться равное количе­ство брусков каждого размера.

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

Элементы линейной алгебры и геометрии 29