ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.07.2021
Просмотров: 1091
Скачиваний: 2
46
с
m
переменными
и
n
ограничениями
в
виде
линейных
уравнений
,
если
1
n–m
2.
12.
Почему
данная
дисциплина
имеет
название
–
математическое
программирование
?
Решите
самостоятельно
Задача
1
.
В
условиях
примера
3
через
год
условия
инвестирования
изменились
,
а
именно
:
1.
Прибыль
от
1
д
.
е
.,
инвестированной
в
акции
ТНК
стала
в
два
раза
больше
,
а
по
акциям
КПК
прибыль
осталась
на
прежнем
уровне
.
2.
Стоимость
акции
ТНК
возросла
в
1,5
раза
,
а
цена
акций
КПК
упала
на
20%.
Инвестор
решил
купить
акций
ТНК
как
минимум
в
два
с
лишним
раза
больше
,
чем
акций
КПК
.
Дайте
ответы
на
вопросы
,
поставленные
в
примере
3.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
47
2.2.
Общая
задача
линейного
программирования
Рассмотрим
математическую
постановку
задачи
,
в
которой
функции
f(X)
и
f
i
(X), i = 1, 2, …, m,
являются
линейными
.
Найти
наибольшее
или
наименьшее
значение
функции
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
при
условии
,
что
(2)
n
j
1
a
ij
x
j
≤
b
i
, i
I
M={1,2,…,m},
(3)
n
j
1
a
ij
x
j
= b
i
, i
M \ I,
(4)
x
j
≥
0, j
J
N=(1, 2, …, n}
Задача
(1) – (4)
называется
общей
задачей
линейного
программирования
;
функция
f(X) –
целевой
функцией
или
функцией
качества
;
система
линейных
неравенств
(2)
и
линейных
уравнений
(3) –
системой
ограничения
,
а
неравенства
(4) –
условием
неотрицательности
переменных
.
К
частным
случаям
общей
задачи
линейного
программирования
относятся
:
каноническая
задача
и
стандартная
задача
.
1.
Каноническая
задача
линейного
программирования
(
КЗЛП
),
когда
I = Ø,
J = N, b
i
≥
0, i
M
и
находится
наибольшее
или
наименьшее
значение
функции
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
при
условии
,
что
n
j
1
a
ij
x
j
= b
i
, i =1,2,…,m,
x
j
≥
0, j=1, 2, …, n.
2.
Задача
линейного
программирования
стандартного
вида
,
когда
J=N, I=M
и
находится
наибольшее
или
наименьшее
значение
функции
f(X) =
n
j
1
γ
j
x
j
+
γ
0
,
при
условии
,
что
n
j
1
a
ij
x
j
≤
b
i
, i =1,2,…,m,
x
j
≥
0, j = 1, 2, …, n.
Замечание
.
В
задачах
линейного
программирования
на
максимум
(
минимум
)
находятся
значения
координат
вектора
Х
= (
х
1
, …,
х
j
, …,
х
n
),
при
которых
достигается
наибольшее
(
наименьшее
)
значение
целевой
функции
.
Определение
.
Вектор
α
= (
α
1
, …,
α
n
)
называется
допустимым
решением
задачи
линейного
программирования
(1)–(4),
если
он
является
решением
ограничений
(2) – (3)
и
удовлетворяет
условию
(4).
Множество
всех
допустимых
решений
задачи
(1)–(4)
обозначим
через
W.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
48
Определение
.
Допустимое
решение
α
0
= (
α
1
0
, …,
α
n
0
)
задачи
линейного
программирования
(1) – (4)
на
максимум
(
или
минимум
)
целевой
функции
f(X)
называется
оптимальным
решением
,
если
для
всех
допустимых
решений
этой
задачи
выполняется
неравенство
f(
α
0
)
≥
f(
α
) (
или
f(
α
0
)
≤
f(
α
) ).
Замечание
.
Оптимальное
решение
задачи
линейного
программирования
(1) – (4)
является
точкой
глобального
экстремума
функции
f(X)
на
множестве
допустимых
решений
W.
Определение
.
Решить
задачу
линейного
программирования
это
,
значит
,
найти
оптимальное
решение
этой
задачи
,
или
доказать
,
что
оптимального
решения
этой
задачи
не
существует
.
Простейшие
свойства
задач
линейного
программирования
1
0
.
Оптимальное
решение
задачи
линейного
программирования
не
изменится
,
если
целевую
функцию
помножить
на
любое
положительное
число
,
либо
прибавить
к
целевой
функции
любое
число
.
Доказательство
этого
утверждения
можно
провести
самостоятельно
,
используя
графический
метод
решения
задачи
линейного
программирования
.
2
0
.
Рассмотрим
общую
задачу
линейного
программирования
:
(1)
f(X) =
n
j
1
γ
j
x
j
+
γ
0
(max),
(2)
n
j
1
a
ij
x
j
≤
b
i
, i
I
M={1,2,…,m},
(3)
n
j
1
a
ij
x
j
= b
i
, i
I \ M={1,2,…,m},
(4)
x
j
≥
0, j
J
N=(1, 2, …, n}
Умножив
целевую
функцию
(1)
на
(–1),
рассмотрим
новую
задачу
,
а
именно
,
(1
’
) f
1
(X) = –
n
j
1
γ
j
x
j
–
γ
0
= – f(X) (min),
(2
’
)
n
j
1
a
ij
x
j
≤
b
i
, I
I
M={1,2,…,m},
(3
’
)
n
j
1
a
ij
x
j
= b
i
, i
I \ M={1,2,…,m},
(4
’
) x
j
≥
0, j
J
N=(1, 2, …, n}.
Вектор
α
0
является
оптимальным
решением
задачи
(1) – (4)
на
максимум
тогда
и
только
тогда
,
когда
α
0
является
оптимальным
решением
задачи
(1
’
)–(4
’
)
на
минимум
.
▲
Необходимость
.
Пусть
W
есть
множество
допустимых
решений
задачи
(1)–(4)
и
задачи
(1
’
)–(4
’
),
а
вектор
α
0
является
оптимальным
решением
задачи
(1)–(4)
на
максимум
.
Тогда
,
по
определению
глобального
максимума
,
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
49
выполняется
неравенство
f(
α
0
)
≥
f(
α
)
для
любого
вектора
α
W.
Умножив
последнее
неравенство
на
минус
единицу
,
получим
новое
неравенство
–f(
α
0
)
≤
–
f(
α
)
и
с
учетом
обозначения
целевой
функции
задачи
(1
’
)–(4
’
)
имеем
f
1
(
α
0
)
≤
f
1
(
α
)
для
любого
вектора
α
W.
Откуда
,
по
определению
глобального
минимума
функции
f
1
(X),
вектор
α
0
является
оптимальным
решением
задачи
(1
’
)–(4
’
)
на
минимум
.
Таким
образом
,
необходимость
доказана
.
Для
доказательства
достаточности
следует
провести
рассуждения
в
обратной
последовательности
.
■
Замечание
.
В
дальнейшем
будем
рассматривать
решение
задач
линейного
программирования
только
на
минимум
,
так
как
задача
на
максимум
может
быть
сведена
к
соответствующей
задаче
на
минимум
.
Ответьте
на
вопросы
1.
Опишите
общую
задачу
линейного
программирования
.
2.
Опишите
каноническую
задачу
линейного
программирования
.
3.
Опишите
задачу
линейного
программирования
стандартного
вида
.
4.
Дайте
определение
допустимого
решения
задачи
линейного
программирования
.
5.
Дайте
определение
оптимального
решения
задачи
линейного
программирования
.
6.
Как
понимать
высказывание
: «
решить
задачу
линейного
программирования
»?
7.
Какие
действия
с
целевой
функцией
не
влияют
на
результат
решения
задачи
линейного
программирования
?
8.
Какие
действия
с
целевой
функцией
задачи
линейного
программирования
приводят
к
тому
,
что
оптимальное
решение
задачи
на
максимум
совпадает
с
оптимальным
решением
той
же
задачи
только
на
минимум
?
9.
Дайте
доказательство
утверждения
,
которое
является
правильным
ответом
на
вопрос
в
п
.7.
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.
50
2. 3.
Примеры
задач
линейного
программирования
Задача
планирования
работы
предприятия
.
Предприятие
располагает
m
видами
ресурсов
и
имеет
возможность
выпускать
однородную
продукцию
,
используя
n
различных
технологических
способов
.
За
единицу
времени
использования
j-
го
технологического
способа
(j = 1,2,…,n)
расходуется
a
ij
единиц
i-
го
ресурса
,
запас
которого
равен
b
i
(i = 1,2,…,m),
и
выпускается
c
j
единиц
продукции
.
Требуется
сформировать
такой
план
работы
предприятия
,
чтобы
выпуск
продукции
был
наибольшим
,
а
расход
каждого
вида
ресурса
не
превосходил
его
запаса
.
Обозначим
через
x
j
–
время
использования
j-
го
технологического
способа
.
Тогда
:
X = (x
1
, … ,x
j
, … , x
n
) –
план
(
программа
)
работы
предприятия
,
в
котором
,
естественно
,
что
все
переменные
не
отрицательны
,
т
.
е
. x
j
≥
0, j = 1, 2, …, n;
n
j
1
c
j
x
j
–
планируемое
к
выпуску
количество
продукции
;
a
ij
x
j
–
количество
i-
го
ресурса
,
которое
расходуется
при
использовании
j-
го
технологического
способа
;
n
j
1
a
ij
x
j
–
общий
расход
i-
го
ресурса
при
выполнении
всей
программы
не
должен
превышать
его
запасов
на
предприятии
,
т
.
е
.
n
j
1
a
ij
x
j
≤
b
i
.
Таким
образом
,
приходим
к
математической
постановке
задачи
планирования
работы
предприятия
в
виде
задачи
линейного
программирования
на
максимум
: f(X) =
n
j
1
c
j
x
j
(max),
n
j
1
a
ij
x
j
≤
b
i
. i=1,2,…,m;
x
j
≥
0, j=1,2,…,n.
Задача
планирования
рационального
питания
.
В
продаже
имеется
n
видов
продуктов
.
В
единице
продукта
j-
го
вида
(j = 1, 2, …, n)
содержится
a
ij
единиц
i-
го
химического
элемента
. (i = 1,2,…,m),
необходимого
для
организма
.
Известна
b
i
–
дневная
норма
потребления
i-
го
химического
вещества
и
цена
c
j
единицы
j-
го
продукта
.
Необходимо
составить
рацион
так
,
чтобы
затраты
на
покупку
продукта
были
минимальными
при
условии
,
что
в
продуктах
содержится
химических
веществ
не
меньше
дневной
нормы
.
Обозначим
через
x
j
количество
единиц
j-
го
продукта
в
дневном
Для самостоятельной работы
студентов ЧОУ ВПО МБИ
Москва 2013г.