ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1092
Скачиваний: 2
51
рационе
.
Это
количество
продукта
содержит
a
ij
x
j
–
количество
i-
го
химического
вещества
,
а
во
всех
продуктах
дневного
рациона
общее
количество
i-
го
химического
вещества
равно
n
j
1
a
ij
x
j
и
не
должно
быть
меньше
дневной
нормы
его
потребления
,
т
.
е
.
n
j
1
a
ij
x
j
≥
b
i
.
Стоимость
всего
набора
X=(x
1
, …, x
j
, …, x
n
)
продуктов
дневного
рациона
равна
f(X) =
n
j
1
c
j
x
j
.
Таким
образом
,
приходим
к
математической
постановке
задачи
планирования
рационального
питания
в
виде
задачи
линейного
программирования
на
минимум
:
f(X) =
n
j
1
c
j
x
j
(min),
n
j
1
a
ij
x
j
≥
b
i
. i=1,2,…,m,
x
j
≥
0, j=1,2,…,n.
Задача
планирования
транспортных
перевозок
.
В
m
пунктах
производится
однородный
продукт
в
количествах
a
1
, a
2
…, a
i
, …, a
m
единиц
,
который
необходимо
перевезти
в
другие
n
пунктов
,
в
которых
этот
продукт
потребляется
в
количествах
b
1
, …, b
j
, …, b
n
.
единиц
.
Стоимость
перевозки
одной
единицы
продукта
из
i
(i = 1, 2, … m)
пункта
производства
в
j
(j=1, 2, …,
n)
пункт
потребления
равна
c
ij
денежных
единиц
,
а
производится
продукта
больше
,
чем
потребляется
,
т
.
е
.
m
i
1
a
i
≥
n
j
1
b
j
.
Требуется
сформировать
план
перевозок
продукта
,
при
котором
все
потребности
в
продукте
будут
удовлетворены
с
наименьшими
затратами
на
перевозку
.
Определим
вектор
X = (x
11
,… ,x
ij
, … ,x
mn
).
как
план
перевозок
между
поставщиками
и
потребителями
,
где
x
ij
–
количество
единиц
продукта
,
которое
перевозится
из
пункта
производства
i
в
пункт
потребления
j,
и
при
чем
либо
перевозка
имеется
,
либо
она
отсутствует
,
т
.
е
. x
ij
≥
0, i = 1, 2, … m; j = 1, 2, …,n,
Тогда
: f(X) =
m
i
1
n
j
1
c
ij
x
ij
–
суммарная
стоимость
всех
перевозок
;
из
i
пункта
производства
вывозиться
единиц
продукта
не
более
,
чем
производится
,
т
.
е
. x
i1
+ … + x
ij
+ … + x
in
≤
a
i
, i = 1, 2, … m;
в
j
пункт
потребления
завозится
единиц
продукта
не
менее
,
чем
потребляется
,
т
.
е
. x
1j
+ … + x
ij
+ … + x
mj
≥
b
j
, j = 1, 2, …, n.
Таким
образом
,
приходим
к
математической
постановке
задачи
планирования
транспортных
перевозок
в
виде
задаче
линейного
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
52
программирования
на
минимум
:
f(X) =
m
i
1
n
j
1
c
ij
x
ij
(min),
x
i1
+ … + x
ij
+ … + x
in
≤
a
i
, i = 1, 2, … m,
x
1j
+ … + x
ij
+ … + x
mj
≥
b
j
, j = 1, 2, …,n,
x
ij
≥
0, i = 1, 2, … m; j = 1, 2, …,n.
Замечание
.
При
математической
постановке
экономической
задачи
необходимо
:
-
ввести
переменные
величины
,
каждая
из
которых
определяет
некоторый
управляемый
экономический
параметр
;
-
сформировать
систему
ограничений
,
связывающие
введенные
переменные
,
используя
условия
задачи
.
-
построить
функцию
цели
(
качества
)
выбора
значений
переменных
;
Ответьте
на
вопросы
1.
Дайте
содержательную
постановку
задачи
планирования
работы
предприятия
.
2.
Опишите
процесс
математической
постановки
задачи
планирования
работы
предприятия
.
3.
Напишите
математическую
постановку
задачи
планирования
работы
предприятия
.
4.
Дайте
содержательную
постановку
задачи
планирования
рационального
питания
.
5.
Опишите
процесс
математической
постановки
задачи
планирования
рационального
питания
6.
Напишите
математическую
постановку
задачи
планирования
рационального
питания
.
7.
Дайте
содержательную
постановку
задачи
планирования
транспортных
перевозок
.
8.
Опишите
процесс
математической
постановки
задачи
планирования
транспортных
перевозок
.
9.
Напишите
математическую
постановку
задачи
планирования
транспортных
перевозок
.
Решите
самостоятельно
Задача
1.
Мастерская
может
отремонтировать
за
неделю
либо
200
машин
класса
Б
,
либо
600
машин
класса
Ж
.
Стоимость
ремонта
машины
класса
Б
равна
С
1
д
.
е
.,
а
класса
Ж
–
С
2
д
.
е
.
Сколько
и
какого
класса
машин
необходимо
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
53
ремонтировать
мастерской
за
неделю
,
чтобы
ее
доход
был
максимален
,
если
:
а
)
С
1
= 850
д
.
е
.,
С
2
= 530
д
.
е
.;
в
)
С
1
=
С
2
;
с
)
С
1
=3
С
2
;
д
)
С
1
/ C
2
= 9/2?
Задача
2.
Фирма
изготавливает
для
продажи
изделия
,
используя
цех
механической
обработки
и
цех
покраски
.
За
одну
смену
механический
цех
может
изготовить
либо
600
изделий
типа
А
,
либо
1200
изделий
типа
В
.
За
то
же
время
цех
покраски
может
обработать
либо
1200
изделий
типа
А
,
либо
800
изделий
типа
В
.
Цена
изделий
типа
А
равна
50
д
.
е
.,
а
типа
В
– 30
д
.
е
.
Рассчитайте
суточную
программу
производства
изделий
типа
А
и
В
так
,
чтобы
доход
от
их
продаж
был
максимален
,
если
:
а
)
оба
цеха
работают
одну
смену
;
в
)
механический
цех
работает
три
смены
,
а
покрасочный
–
две
смены
;
с
)
оба
цеха
работают
две
смены
,
но
из
-
за
нехватки
сырья
может
быть
изготовлено
изделий
типа
А
не
более
800
штук
,
а
изделий
типа
В
не
более
1000
штук
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
54
2.4.
Опорное
решение
канонической
задачи
линейного
программирования
Рассмотрим
каноническую
задачу
линейного
программирования
(
КЗЛП
)
(1) f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
a
11
x
1
+ … + a
1j
x
j
+ … + a
1n
x
n
= b
1
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(2) a
i1
x
1
+ … + a
ij
x
j
+ … + a
in
x
n
= b
i
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
x
1
+ … + a
mj
x
j
+ … + a
mn
x
n
= b
m
,
(3)
x
1
≥
0, .
x
j
≥
.0, x
n
≥
0.
Обозначим
векторы
условий
и
вектор
ограничений
КЗЛП
соответственно
a
11
a
1j
a
1n
b
1
,
…
…
…
…
a
i1
=
А
1
, a
ij
=
А
j
, a
in
=
A
n
,
b
i
, =
B.
…
…
…
…
a
m1
a
mj
a
mn
b
m
,
Тогда
каноническую
задачу
линейного
программирования
можно
записать
в
виде
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
(2)
n
j
1
А
j
x
j
= B,
(3)
x
j
≥
0, j=1,2,…,n.
Пусть
вектор
α
= (
α
1
, ,
α
j
, …,
α
n
)
является
допустимым
решением
задачи
(1)–(3),
т
.
е
.
этот
вектор
является
решением
системы
линейных
уравнений
(2)
и
удовлетворяет
условиям
не
отрицательности
неизвестных
(3).
При
этом
i
1
, i
2
,
..., i
k
–
номера
всех
ненулевых
координат
вектора
α
.
Определение
.
Допустимое
решение
α
= (
α
1
, ,
α
j
, …,
α
n
)
канонической
задачи
линейного
программирования
(1) – (3)
называется
опорным
решением
,
если
векторы
условий
А
i1
, A
i2
, …, Ai
k
,
соответствующие
ненулевым
координатам
вектора
α
= (
α
1
, ,
α
j
, …,
α
n
),
образуют
линейно
независимую
систему
векторов
Замечание
.
Чтобы
выяснить
,
является
ли
вектор
α
= (
α
1
, ,
α
j
, …,
α
n
)
опорным
решением
(1) – (3),
необходимо
:
проверить
,
является
ли
вектор
α
решением
системы
линейных
уравнений
(2),
проверить
,
удовлетворяет
ли
вектор
α
ограничением
(3),
выписать
номера
всех
ненулевых
координат
вектора
α
и
показать
,
что
векторы
условий
рассматриваемой
задачи
с
этими
номерами
образуют
линейно
независимую
систему
векторов
.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
55
Пример
1
.
Дана
КЗЛП
:
(1) f(X)
=
x
1
–
x
2
+
x
3
+
x
4
(min)
x
1
+
x
2
–
x
3
+ x
4
=
3,
(2)
2x
1
–
x
2
+
x
3
– x
4
=
0,
x
1
+
x
2
+
2x
3
– x
4
=
1,
(3) x
j
≥
0
, j=1,2, 3, 4
и
вектор
α
=(1, 1, 0, 1).
Определить
,
является
ли
вектор
α
опорным
решением
данной
задачи
.
▲
Подставив
координаты
вектора
α
= (1, 1, 0, 1),
в
(2) – (3),
убеждаемся
,
что
он
является
допустимым
решением
данной
задачи
.
Ненулевым
координатам
вектора
α
соответствуют
векторы
условий
А
1
,
А
2
,
А
4
,
преобразовав
которые
методом
Гаусса
,
получаем
систему
единичных
векторов
.
Это
соответствует
тому
,
что
векторы
условий
А
1
А
2
А
4
А
1
А
2
А
4
А
1
А
2
А
4
А
1
А
2
А
4
1
1 1 1 1 1 0 1 1 0 1 0
2 –1 –1
3 0 0
1 0 0
1 0 0
1 1 –1 0 0 –2 0 0 –2 0 0 1
А
1
,
А
2
,
А
4
образуют
систему
линейно
независимых
векторов
.
Следовательно
,
вектор
α
=(1, 1, 0, 1).
является
опорным
решением
данной
задачи
.
■
Пример
2
.
Дана
КЗЛП
(1) f(X)
= x
1
–
x
2
+
2x
3
(max)
(2)
x
1
+
x
2
–
x
3
=
1,
2x
1
– x
2
–
2x
3
= 2,
(3) x
j
≥
0
, j=1,2, 3.
и
вектор
α
= (2, 0, 1).
Определить
,
является
ли
вектор
α
опорным
решением
данной
задачи
.
▲
Подставив
координаты
вектора
α
=(2, 0, 1).
в
(2) – (3),
убеждаемся
,
что
он
является
допустимым
решением
данной
задачи
.
Ненулевым
координатам
вектора
α
соответствуют
векторы
условий
А
1
,
А
3
,
преобразовав
которые
методом
Гаусса
,
видим
,
A
1
A
3
A
1
A
3
1
–1
1 –1
2 –2 0 0
они
образуют
линейно
зависимую
систему
векторов
.
Следовательно
,
по
определению
,
вектор
α
=(2, 0, 1)
не
является
опорным
решением
данной
КЗЛП
.
■
Лемма
(
арифметическая
).
Пусть
α
1
,
α
2
, …,
α
l
некоторые
положительные
числа
,
а
k
1
, k
2
, …k
ненулевой
набор
чисел
,
т
.
е
.
найдется
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.