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

Многие практические задачи сводятся к случаю, когда необходимо найти либо максимум или минимум функции f(x₁, x₂,…, x_n):

f(x₁, x₂,…, x_n)→max(min), (1.1)

и на переменные x₁, x₂, …, x_n наложены различные ограничения в виде неравенств или равенств:

Функция (1.1) называется функцией цели (целевой функцией, линейной функцией, линейной формой).

Соотношения (1.2) – (1.5) представляют собой запись условий ограничений (неравенств ограничений, система ограничений) функции (1.1).

Программирование– нахождение экстремума (max или min) функции (1.1) при заданных ограничениях (1.2) – (1.5), т.е. другими словами, найти оптимальное решение функции f(x₁, x₂, …, x_n) при наложенных ограничениях.

Линейное программирование (задачи линейного программирования) – это нахождение оптимального решения (оптимального плана) при условии, что функция цели f(x₁, x₂, …, x_n) линейна, все условия ограничения линейны и x₁, x₂, …, x_n ≥ 0.

Пусть имеется n переменных x₁, x₂, …, x_n. Необходимо найти такие значения этих переменных, чтобы достигался max или min функции цели (линейной):

F=c₁x₁+c₂x₂+…+c_nx_n→max(min), (1.6)

при соответствующей системе ограничений:

(1.7)

Для конкретной практической задачи система ограничений может содержать любой из знаков неравенства. Но сами переменные x₁, x₂, …, x_n всегда должны быть больше либо равны нулю.

Необходимо найти решение системы ограничений X=(x₁, x₂, …, x_n), при котором функция цели (1.6) будет принимать экстремальное значение (max или min). При этом данное решение должно удовлетворять системе ограничений (1.7). Нахождение такого решения и составляет задачу линейного программирования (ЛП).

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

(1.8)

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

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

(1.9)

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

(1.10)

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

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

Пусть:

i - номер группы оборудования (i=1,2,…,m);

j - номер вида изделия (j=1,2,…,n) ;

a_ij - норма времени на обработку единицы j-ого изделия на i-й группеоборудования;

b_i - фонд времени работы i-й группы оборудования;

c_j - прибыль на одно изделие j-ого вида;

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

- искомый план производства.

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

На обработку x₁ единиц первого изделия на i-й группе оборудования будет затрачено a_i1x₁ единиц времени; на обработку x₂ единиц второго изделия на той же группе оборудования будет затрачено a_i2x₂ единиц времени и т. д.

Необходимое время на обработку всех изделий на i-й группе оборудования будет равно сумме ( ).

Эта сумма не может превышать фонд времени работы i-й группыоборудования, т. е. должна быть меньше либо равна . Выписывая такие условия для всех m групп оборудования, формирется система:

(1.11)

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

.

При плане производства ( ) прибыль предприятия будет равна

. (1.12)

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

Система линейных неравенств (1.11) и линейная форма (1.12) образуют математическую модель задачи о рациональном использовании производственных мощностей. Среди всех решений системы линейных неравенств (1.11), удовлетворяющих условию неотрицательности переменных, необходимо найти такое решение, при котором линейная форма (1.12) принимает наибольшее возможное значение. Это - задача линейного программирования.

Исходные параметры задачи могут быть представлены в виде матрицы А удельных затрат ресурсов, вектора В объемов ресурсов и вектора С удельной прибыли:

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

Производственное объединение получило заказ на изготовление n видов изделий в количествах d₁, d₂, …, d_n соответственно. Объединению подчинены m предприятий, на каждом из которых может быть выполнен заказ на любое изделие.

Пусть

b_i - действительный фонд времени работы i-го предприятия;

a_ij и c_ij - соответственно норма расхода времени и себестоимость изготовления единицы j-го изделия на i-м предприятии;

x_ij - число изделий j-го вида, которое поручается изготовить i-му предприятию.

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

при условии, что будут соблюдены ограничения по фонду времени работы каждого предприятия

, где ,

и будет изготовлено необходимое количество изделий каждого вида

, .

причем по смыслу задачи

, где , .

Задача о диете. Необходимые в дневном рационе питания m видов питательных веществ содержатся в n видах продуктов.

Пусть

a_ij - количество единиц i-го питательного вещества в единице j-го продукта;

b_i - необходимое количество единиц i-го питательного вещества в дневном рационе;

c_j - стоимость единицы j-го продукта.

Задача состоит в том, чтобы найти план покупок , минимизирующий суммарные затраты:

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

, где ,

причем по смыслу задачи , где .

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

Пусть

j - номер типа груза;

n - число типов грузов;

a_1j, a_2j, c_j - масса, объем и стоимость единицы j-го груза;

b₁, b₂ - грузоподъемность и вместимость грузового отсека корабля;

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

Задача состоит в том, чтобы найти набор , максимизирующий суммарную ценность

при ограничениях по грузоподъемности и вместимости

,

где , , x_j – целое, .