Общая и основная задачи ЛП

Содержание математического программирования. Постановка общей и основной задач линейного программирования

Термин математическое программирование предложил математик Дорфман. Содержание МП составляют теория и методы решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и/или неравенствами). Слово "программирование" означает "планирование" или "поиск наилучших планов". МП является одним из разделов науки об исследовании операций.

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

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

Общая схема формирования модели:

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

2. выражение взаимосвязей, присущих явлению, в виде математических соотношений, эти соотношения образуют систему ограничений задачи;

3. количественное выражение выбранного критерия оптимальности в форме целевой функции;

4. математическая формулировка задачи как задачи нахождения экстремума целевой функции при условии выполнения ограничений, накладываемых на переменные.

Примеры задач ЛП.

Задача 1. Использование сырья. Предприятие может выпускать два вида продукции (P₁,P₂). На их изготовление расходуется три вида сырья (S₁,S₂,S₃). Запасы сырья, нормы их расхода на единицу изделия a_ij(i = 1,2,3; j = 1,2), себестоимость c_j(j=1,2) и цены приведены в таблице:

Тип сырья	Запас cырья	Нормы расхода сырья на изделие
P1	P2
S1
S2
S3
Себестоимость, $
Цены, $

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

Построим математическую модель: обозначим x ₁и x ₂– количество выпускаемой продукции P ₁и P ₂. На изготовление изделий P ₁, P ₂будет израсходовано 10 x ₁+ 20 x ₂единиц сырья S₁. По условию имеем: 10 x ₁+ 20 x ₂£ 100.

Аналогичным образом получаем ограничения по другим видам сырья:

20 x ₁+ 10 x ₂£ 120,

20 x ₁+ 20 x ₂£ 140.

В результате реализации единицы изделия P₁предприятие получит прибыль (7–5) = 2 усл. ед.; единицы изделия P₂– прибыль (13–10) = 3 усл. ед. Общая прибыль составит:

f (x ₁, x ₂) = 2 x ₁+ 3 x ₂.

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

Задача 2. Транспортная задача. В двух пунктах отправления сосредоточен однородный груз в количестве 5 и 15 т. Груз необходимо доставить трем потребителям, потребности которых таковы: 1-й потребитель – 6 т, 2-й потребитель – 10 т, 3-й потребитель – 4 т. Известны также затраты на перевозку единицы груза из i-го пункта отправления в каждый j-й пункт потребления:

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

Математическая модель: обозначим x _ij– объем перевозок груза из i-го пункта отправления в j-й пункт потребления (i = 1,2; j = 1,2,3). Тогда получим:

F(x) = x ₁₁+ 9 x ₁₂+ 7 x ₁₃+ 8 x ₂₁+ 5 x ₂₂+ 4 x ₂₃®min

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

Общая и основная задачи ЛП

Общая задача. Найти максимальное значение линейной целевой функции

(1.1)

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

(1.2)

где c _j, a _ij, b _i– действительные числа,

x _j– переменные.

Совокупность чисел , удовлетворяющих ограничениям (1.2), называется допустимым решением или планом.

План , при котором целевая функция z принимает свое максимальное значение, называется оптимальным.

Каноническая форма. Задачу ЛП будем считать приведенной к каноническому виду, если

1) требуется найти максимум целевой функции;

2) система ограничений (1.2) содержит только равенства;

3) правые части системы ограничений неотрицательны.

Переход от общей формы к канонической:

1) если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию , тогда ;

2) чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства;

3) если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на "-1" обе части равенства, в котором в правой части стоит отрицательное число.

Задачу ЛП в канонической форме называют основной задачей.

Дата добавления: 2015-11-14