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

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

2. Линейное программирование

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

3.

Математическая модель задачи оптимизации ЗЛП это
совокупность
соотношений,
содержащих
целевую
функцию и ограничения на ее аргументы записывается в
общем виде так:
F ( x) c1x1 c2 x2 ... c j x j ... cn xn m a x(min)
при ограничениях
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a12 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
...............................................................,
.
ai1 x1 ai 2 x2 ... aij x j ... ain xn bi ,
..............................................................,
am1 x1 am 2 x2 ... amj x j ... amn xn bm
x j 0, i 1, m, j 1, n.
x j - неизвестные,
aij , bi , c j
- заданные постоянные величины
Ограничения могут быть заданы уравнениями.

4.

В краткой записи ЗЛП имеет вид:
n
F ( x) c j x j max(min)
j 1
n
a x
j 1
ij
j
bi ,
при ограничениях
x j 0, i 1, m, j 1, n.
Экстремум целевой функции ищется на допустимом
множестве решений, определяемом системой ограничений,
причем все или некоторые неравенства
в системе
ограничений могут быть записаны в виде уравнений.

5.

Для составления математической модели
ЗЛП необходимо :
1)обозначить переменные;
2)составить целевую функцию;
3)записать систему ограничений в
соответствии с целью задачи;
4)записать систему ограничений с учетом
имеющихся в условии задачи показателей.
Если все ограничения задачи заданы
уравнениями, то модель такого вида
называется канонической.
Если хоть одно из ограничений дано
неравенством, то модель неканоническая.

6. Экономико-математическая модель задачи.

n
F ( X ) c j x j min,
j 1
n
a x
j 1
ij
x j 0,
j
bi ,
i 1, m,
j 1, n.
Целевая функция представляет собой суммарную
стоимость смеси, а функциональные ограничения
являются ограничениями по содержанию
компонентов в смеси: смесь должна содержать
компоненты в объемах, не менее указанных.

7.

8. Примеры задач, которые сводятся к ЗПЛ.

1. задача оптимального распределения ресурсов
при планировании выпуска продукции на
предприятии (задача об ассортименте);
2. задача на максимум выпуска продукции при
заданном ассортименте;
3. задача о смесях (рационе, диете и т.д.);
4. транспортная задача;
5. задача о рациональном использовании
имеющихся мощностей;
6. задача о назначениях.

9. 1.Задача оптимального распределения ресурсов

10. 1.Задача оптимального распределения ресурсов.

n
Предположим, что предприятие выпускает различных
изделий. Для их производства требуется
различных видов
ресурсов (сырья, рабочего и
m
машинного времени, вспомогательных материалов).
Эти ресурсы ограничены и составляют в
b1 , b2 , ..., bm условных
планируемый период
единиц. Известны также технологические
коэффициенты aij , которые указывают, сколько
единиц i-го ресурса требуется для производства
изделия j-го вида. Пусть прибыль, получаемая
предприятием при реализации единицы изделия j-го
вида , равна c j . В планируемый период все
показатели aij , bi , c j предполагаются постоянными.

11.

Требуется составить такой план выпуска
продукции, при реализации которого
прибыль предприятия была бы
наибольшей.
Экономико-математическая модель
n
задачи
F c j x j max,
j 1
n
a x
j 1
ij
x j 0,
j
bi ,
i 1, m,
j=1, n.

12.

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

13.

Пример Для изготовления трех видов
изделий А, В и С используется токарное, фрезерное,
сварочное и шлифовальное оборудование. Затраты времени
на обработку одного изделия для каждого из типов
оборудования указаны в табл. В ней же указан общий фонд
рабочего времени каждого из типов используемого
оборудования, а также прибыль от реализации одного
изделия каждого вида.
Требуется
Тип
Затраты времени
Общий
определить,
оборудования
(станко-часы)
фонд
на обработку одного изделия
рабочего
сколько изделий и ка
каждого вида
времени
оборудован
кого вида следует
ия
А
В
С
(часы)
изготовить
предприятию, чтобы
Фрезерное
2
4
5
120
прибыль от их
Токарное
1
8
6
280
реализации была
Сварочное
7
4
5
240
максимальной.
Шлифовальное
4
6
7
360
Составить
Прибыль (руб.)
10
14
12
математическую

14.

15.

16.

17.

18.

Таким образом, приходим к следующей ЗЛП:
Требуется среди всех неотрицательных
решений системы неравенств
2 x1 4 x2 5 x3 120,
x 8 x 6 x 280,
1
2
3
7 x1 4 x2 5 x3 240,
4 x1 6 x2 7 x3 360.
найти такое, при котором целевая функция
F 10 x1 14 x2 12 x3
принимает максимальное значение.

19.

ение занимается разработкой и производством комплексных удобрений. На да
питания не менее bi(i = 1, 2,…, m);
ь данной экономической ситуации. Обозначим через xj количество j-го удобре
сно «химико-экономической» характеристике тукосмеси, имеет место следую
дель предложенной экономической ситуации имеет следующий вид:
xn min,
ание задачи о смесях. К ним относят задачи определения состава сплавов, кор

20. Задача о смесях.

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

21.

Научно-производственное
объединение
занимается
разработкой и производством комплексных удобрений. На
данный момент в своем распоряжении оно имеет n видов
удобрений, каждое из которых содержит m элементов
непосредственного питания растений. Такими элементами
могут быть азот, фосфор, калий, магний, медь, марганец…
Известно, что одна единица j-го вида удобрений (j =
1, 2,…, n) содержит aij единиц i-го (i = 1, 2,…, m) элемента
непосредственного питания растений и имеет стоимость cj.
Необходимо изготовить смешанное комплексное
удобрение
(тукосмесь),
получаемое
механическим
смешением имеющихся удобрений. При этом тукосмесь
должна иметь следующую «химико-экономическую»
характеристику:
- содержание каждого i-го элемента питания не менее
bi(i = 1, 2,…, m);
- наименьшую стоимость.

22.

23.

24.

Рассмотрим математическую модель данной
экономической ситуации.
Обозначим через xj количество j-го удобрения,
используемого при изготовлении тукосмеси. Конечно, xj ≥ 0
(j = 1, 2,…, n).
Для каждого i-го элемента питания (i = 1, 2,…, m),
согласно «химико-экономической» характеристике
тукосмеси, имеет место следующее неравенствоограничение: ai1x1 + ai2x2 + ... + ainxn ≥ bi.
Стоимость комплексного удобрения составляет
c1x1 + c2x2 + ... + cnxn.
Эту величину необходимо минимизировать.
Таким образом, математическая модель предложенной
экономической ситуации имеет следующий вид:
L(X) = c1x1 + c2x2 + ... + cjxj + ... + cnxn min,

25.

26. Пример 2

Продукцией гормолокозавода являются
молоко, кефир и сметана, расфасованные в
тару. На производство 1 т молока, кефира и
сметаны требуется соответственно1010,1010
и 9450 кг молока. При этом затраты рабочего
времени при разливе 1 т молока и кефира
составляют 0,18 и 0,19 машино-часов. На
расфасовке 1 т сметаны заняты специальные
автоматы в течение 3,25 часов.

27.

Всего для производства цельномолочной
продукции завод может использовать 136000
кг молока. Основное оборудование может
быть занято в течение 21,4 машино-часов, а
автоматы по расфасовке сметаны – в течение
16,25 часов. Прибыль от реализации 1 т
молока, кефира и сметаны соответственно
равна 30, 22 и 136 руб. Завод должен
ежедневно производить не менее 100 т
молока, расфасованного в бутылки. На
производство другой продукции нет
ограничений.

28.

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

29. Решение

x1 т
Пусть завод будет производить
молока, x2 т кефира и x3 т сметаны.
Тогда ему необходимо
1010 x1 1010 x2 9450 x3 кг молока.
Так как завод может использовать
ежедневно не более 136000 кг молока,
то должно выполняться неравенство
1010 x1 1010 x2 9450 x3 136000

30.

Ограничения на время по расфасовке
молока и кефира 0,18x1 0,19 x2 21,4
и по расфасовке сметаны 3, 25x3 16, 25 .
Так как ежедневно должно
вырабатываться не менее100 т молока,
то x1 100 .
По экономическому смыслу
x2 0, x3 0.

31.

Общая прибыль от реализации всей продукции равна
руб.
Таким образом,
30 x1 22 x2 136 x3
приходим к следующей задаче:
F 30 x1 22 x2 136 x3 max
при ограничениях
1010 x1 1010 x2 9450 x3 136000,
0,18 x 0,19 x
21, 4,
1
2
3, 25 x2
16, 25,
x1
100,
x1 0, x2 0, x3 0.
Так как целевая функция линейная и ограничения
заданы системой неравенств, то эта задача является
ЗЛП.

32.

33.

34.

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

35.

36. Задача о раскрое

На швейной фабрике ткань может быть
раскроена несколькими способами для
изготовления нужных деталей швейных
изделий.
Пусть при j-ом варианте
раскроя 100ì 2 изготавливается bij деталей
i-го вида, а величина отходов при данном
варианте раскроя равна cij ì 2 . Зная, что
деталей i-го вида следует изготовлять Bi
штук, требуется раскроить ткань так, чтобы
было получено необходимое количество
деталей каждого вида при минимальных
общих отходах. Составить математическую
модель задачи.

37.

Решение. Предположим, что по j-ому
2
варианту раскраивается x j сотен ì
2
100ì
ткани. Поскольку при раскрое
ткани по j-ому варианту получается bij
деталей i-го вида , по всем вариантам
раскроя из используемых тканей будет
получено
bi1 x1 bi 2 x2 ... bin xn Bi (i 1, m).
Общая величина отходов по всем
вариантам раскроя составит
F c1 x1 c2 x2 ... cn xn .

38.

Таким образом, приходим к следующей
задаче:
Найти минимум функции
n
F c1 x1 c2 x2 ... cn xn c j x j
j 1
при условии, что ее переменные
удовлетворяют ограничениям
n
b x
j 1
ij
xj 0
j
Bi
(i 1, m),
( j 1, n)

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

Опр.1.Общей задачей линейного программирования
называется задача, которая состоит в определении
максимального (минимального) значения функции
n
F c j x j (1)
при условиях
n
a x
j 1
ij
n
j
bi
aij x j bi
j 1
(i 1, k ),
(i k 1, m),
(2)
j 1
xj 0
( j 1, l , l n),
где aij , bi , c j -заданные постоянные величины и
k m.

40.

41.

42.

Опр.2.Функция (1) называется целевой, а
условия (2)-ограничениями задачи.
Опр.3. Совокупность чисел
X ( x1 , x2 ,..., xn )
,
удовлетворяющих ограничениям задачи
(1)-(2), называются допустимым
решением (или планом).

43. Основная задача ЛП

Опр.4. Основной , или канонической ЗЛП называется
задача, состоящая в определении значения целевой
функции
F ( x) c1 x1 c2 x2 ... c j x j ... cn xn max(min)
при условии, что система ограничений представлена
в виде системы уравнений:
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a12 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
...............................................................,
.
ai1 x1 ai 2 x2 ... aij x j ... ain xn bi ,
..............................................................,
am1 x1 am 2 x2 ... amj x j ... amn xn bn
x j 0, i 1, m, j 1, n.

44.

45.

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

46. Пример.

Записать в форме основной задачи ЛП задачу: найти
максимум функции
F 3x1 2 x2 5x4 x5
при условиях
2 x1 x3 x4 x5 2,
x x 2 x x 3,
1 3
4
5
2 x2 x3 x4 2 x5 6,
x1
x4 5 x5 8,
x1 , x2 , x3 , x4 , x5 0.

47.

Перейдем от ограничений –неравенств к
ограничениям-равенствам.
У нас имеется 4 неравенства, поэтому введем 4
дополнительные переменные.
Тогда запишем уже основную задачу линейного
программирования: максимизировать функцию
F 3x1 2 x2 5x4 x5
при условиях
2 x1 x3 x4 x5 x6 2,
x x 2 x x x 3,
1 3
4
5
7
2 x2 x3 x4 2 x5 x8 6,
x1
x4 5 x5 x9 8,
x1 , x2 , x3 , x4 , x5 0.

48.

49. Свойства основной ЗЛП.

Перепишем ЗЛП в векторной форме: найти максимум
функции F c1 x1 c2 x2 ... cn xn при условиях
x1 P1 x2 P2 ... xn Pn P0 ,
x j 0 ( j 1, n).
Здесь
b1
a11
a12
a1n
b
a
a
a
P0 2 ; P1 21 , P2 22 ;...; Pn 2 n .
...
...
...
...
bm
am1
am 2
amn

50.

Перепишем ЗЛП в векторной форме
2 x1 x3 x4 x5 x6 2,
x x 2 x x x 3,
1 3
4
5
7
2 x2 x3 x4 2 x5 x8 6,
x1
x4 5 x5 x9 8,
x1 , x2 , x3 , x4 , x5 0.
b1
a11
b
a21
2
P0
; P1
, P2
...
...
bm
am1
x1 P1 x2 P2 ... xn Pn P0 ,
x j 0 ( j 1, n).
F c1 x1 c2 x2 ... cn xn
a12
a1n
a
a2 n
22
;...; Pn
.
...
...
am 2
amn

51.

План X ( x1 , x2 ,..., xn ) называется
опорным, если все компоненты
базисного решения системы
ограничений канонической задачи
линейного программирования
неотрицательны.
Число положительных компонент
опорного плана не может быть больше
m, т.е.числа уравнений в ограничениях.

52.

Опорный план называется
невырожденным, если он содержит m
положительных компонент. В противном
случае он называется вырожденным.
План, при котором целевая функция
ЗЛП принимает свое максимальное
(минимальное ) значение , называется
оптимальным.