ЗАДАЧИ, ПРИВОДЯЩИЕ К ЗЛП
ЗАДАЧИ, ПРИВОДЯЩИЕ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП)
Задача о смесях
Задача о наилучшем распределении ресурсов
Задача о выборе оптимальной технологии
Задача о назначениях
Задача сменно суточного планирования автобусного парка
Транспортная задача
162.50K
Category: programmingprogramming

Задачи приводящие к задаче линейного программирования. (Тема 2)

1. ЗАДАЧИ, ПРИВОДЯЩИЕ К ЗЛП

2. ЗАДАЧИ, ПРИВОДЯЩИЕ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП)

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

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

Исходные данные:
m
n

число необходимых питательных в
– число
продуктов
– количество единиц i-го
a питания
питательного вещества, содержаij щееся в единице j-го вида продукта
– норма потребления i-го
b питания
i питательного вещества
c – цена j-го продукта питания
j
x – количество единиц j-го продукта,
j
используемого
в
рационе,
подлежащее определению
n
z c x min
j j
j 1
n
aij x j bi (i 1, m)
j 1
x 0 ( j 1, n)
j

4. Задача о наилучшем распределении ресурсов

Исходные данные:
чество видов выпускаемой продукции
ство– необходимых
для производства
рес
технологические
коэффициенты,
a
т.е.
количество
единиц
i-го
ij
ресурса,
необходимого
для
производства
единицы
j-го
вида
– полные объемы имеющихся
продукции
bi ресурсов
прибыль,
получаемая
при
cj–
реализации
единицы
j-го
вида
продукта.
x ( x ,..., x ,..., x ) – план выпуска продукции
n
1
j
n
z c j x j max
j 1
n
a x
j 1
ij
j
bi (i 1, m)
x j 0 ( j 1, n)

5. Задача о выборе оптимальной технологии

Исходные данные:
n
– количество технологий
m
– количество ресурсов
bi (i 1, m) – объём ресурсов i-го вида
– эффективность технологий,
c j ( j количество
1, n)
т.е.
конечной продукции
(в денежном эквиваленте),
производимой в единицу времени по
– расход i-го ресурса в единицу
j-й
a ij технологии
времени по j-й технологии
x j – время, в течение которого
продукция производится
по j-й
n
технологии
z c x max
j 1
n
a x
j 1
ij
j
j
j
bi (i 1, m)
x j 0 ( j 1, n)

6. Задача о назначениях

Исходные данные:
n – число видов работ
специалистов, выполняющих все виды работ
n –– число
эффективность выполнения i-ым
cспециалистом
ij
j-ой работы
1, i ый человек выполняет j ую работу
xi , j
0, i ый человек не выполняет j ую работу
c
x max
i, j i, j
n
x
j 1
i, j
n
x
i 1
i, j
1 (i 1, n)
1 ( j 1, n)

7. Задача сменно суточного планирования автобусного парка

Цель: определение минимального количества автобусов для
удовлетворения потребностей пассажирских перевозок. Будем
считать, что каждые четыре часа количество автобусов
постоянно.
15
10
5
0
0:00-4:00
4:00-8:00
8:00-12:00
12:00-16:00 16:00-20:00 20:00-24:00

8.

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

9.

8 : 01 16 : 00
x1 10
16 : 01 24 : 00 x2 12
0 : 01 8 : 00 x3 8
x1 x2 x3 30
6
x
j 1
j
min
Решение:
xj 0
x1 x6 4 x1 0
x1 x2 8 x2 0
x2 x3 10 x3 0
x3 x4 7 x4 0
x4 x5 12 x5 0
x5 x6 4 x6 0
x1 x3 x5 0; x2 10; x4 12; x6 4.

10. Транспортная задача

Исходные данные:
m – число пунктов отправления ( Ai – пункт отправлени
n – число пунктов назначения( B j – пункт назначения)
ai (i 1, m) – объем продукта в пункте отправления
b j ( j 1, n) – потребность в пункте назначения
c ij
– затраты на перевозку единицы продукта из i-го пункта
отправления в j-ый пункт назначения
m
a
i 1
i
n
b j
j 1
m
n
ai b j (*)
i 1
j 1
Если выполняется условие (*), то перед нами транспортная задача
закрытого типа. В противном случае это – задача открытого типа.

11.

Cоставить такой план перевозок,
чтобы общая стоимость перевозок
была минимальной.
B1
B2

Bn
A1
X11, C11
X12, C12

X1n, C1n
A2
X21, C21
X22, C22

X2n, C2n





Am
Xm1, Cm1
Xm2 Cm2

Xmn, Cmn
m
n
c
i 1 j 1
x min
ij ij
n
xij ai , (i 1, m)
jm 1
x b , ( j 1, n)
ij
j
i 1
xij 0
English     Русский Rules