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

Стр 1 из 8Следующая ⇒

Многие практические задачи сводятся к случаю, когда необходимо найти либо максимум или минимум функции 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_i₁x₁ единиц времени; на обработку x₂ единиц второго изделия на той же группе оборудования будет затрачено a_i₂x₂ единиц времени и т. д.

Необходимое время на обработку всех изделий на 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₁_j, a₂_j, c_j - масса, объем и стоимость единицы j-го груза;

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

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

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

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

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

Пример составления математической модели задачи

Пример №1.1. Составить математическую модель задачи.

Для производства компьютерных столов I-го и II-го видов требуются три типа ресурсов: дерево, пластик и трудозатраты. Потребности в ресурсах для производства одного стола каждого вида, запасы ресурсов, а также прибыль от реализации одного стола каждого вида, заданы в таблице 1.1.:

Таблица 1.1. – Исходные данные

Тип ресурса	Единица продукции I-го вида	Единица продукции II-го вида	Запас ресурса
Дерево (м²)
Пластик (м²)
Трудозатраты (чел/час)
Прибыль (руб.)

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

Решение.

Пусть x₁ и x₂ – количество продукции I-го и II-го вида соответственно.

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

Поэтому:

условие – ограничение по дереву имеет вид:

условие – ограничение по пластику:

условие – ограничение по трудозатратам:

Кроме того, переменные x₁, x₂ должны быть больше или равны нулю:

Прибыль при реализации продукции составит:

(руб).

Т.к. прибыль должна быть максимальной, то необходимо найти максимум функции цели .

Ответ.

Математическая модель задачи имеет вид:

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

Пример №1.2. Составить математическую модель задачи.

Фабрика производит два вида мыла: хозяйственное и туалетное. Продукция обоих видов поступает в оптовую продажу. Для производства мыла используются два ингредиента – А и В. Максимально возможные суточные запасы этих ингредиентов составляют 6 т и 8 т соответственно. Известны расходы ингридиентов А и В на 1 т соответствующих видов мыла (табл. 1.2.). Изучение рынка сбыта показало, что суточный спрос на туалетное мыло никогда не превышает спроса на хозяйственное мыло более, чем на 1 т. Кроме того, установлено, что спрос на туалетное мыло никогда не превышает 2 т в сутки. Оптовая цена одной тонны хозяйственного мыла равна 3 тыс. руб., а одной тонны туалетного мыла – 2 тыс. руб.

Таблица 1.2. – Исходные данные

Ингредиенты	Расход ингредиентов, т ингр./т мыло	Запас, т ингр./сутки
Хозяйственное мыло	Туаленое мыло
А
В

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

Решение.

Пусть x₁ – количество хозяйственного мыла,

x₂ – количество туалетного мыла.

Запись условий – ограничений:

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

(т ингр.А/сутки),