Материал: 3376
для переменных x1 , x2 , x3 , x4 , x5 , удовлетворяющих системе ограничений (7.3), условиям неотрицательности и условиям целочисленности.
Решив последнюю задачу, мы получим значения переменных, при которых функция (7.1) достигает минимума.
Решим последнюю задачу методом отсечений.
Найдем оптимальный план соответствующей КЗЛП без условия целочисленности.
Составим симплексные таблицы (табл. 7.1, 7.2).
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.1 |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
Б |
f |
1 |
1 |
1 |
|
|
|
0 |
|
0 |
|
|
|
|
|
fi |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
his |
||||||||||
x1 |
x2 |
|
x3 |
|
x4 |
|
x5 |
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
–1 |
x1 |
19 |
1 |
0 |
|
|
2 |
|
|
|
|
1 |
|
0 |
|
|
20 |
1 |
|
|
28 |
1 |
|
||||||||
|
3 |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
3 |
|
|
2 |
|
|||||||||||
–1 |
x2 |
35 |
0 |
1 |
|
1 |
|
|
|
0 |
|
|
1 |
|
36 |
|
|
|
70 |
|
|||||||||||
2 |
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
F X 0 54 |
0 |
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
53 |
1 |
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
6 |
|
|
3 |
|
|
2 |
|
|
3 |
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 7.2
С |
Б |
f |
|
|
|
|
1 |
|
|
1 |
1 |
0 |
|
|
0 |
|
|
|
|
|
|
|
fi |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
his |
|
|||||
|
|
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
–1 |
x3 |
28 |
1 |
|
|
|
3 |
|
|
0 |
1 |
|
1 |
|
0 |
|
|
30 |
1 |
|
|
|
|
|
|||||||
2 |
|
|
2 |
|
|
|
|
2 |
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
–1 |
x2 |
20 |
3 |
|
|
|
3 |
|
1 |
0 |
|
1 |
|
|
|
1 |
|
20 |
3 |
|
|
|
|
|
|||||||
4 |
|
|
|
|
4 |
|
|
|
|
4 |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
4 |
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F X 1 49 |
1 |
|
|
1 |
|
|
0 |
0 |
|
1 |
|
|
|
1 |
|
|
48 |
1 |
|
|
|
|
|||||||||
|
|
4 |
|
|
4 |
|
|
2 |
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28
Так как оценки всех свободных неизвестных положительны, то план
|
1 |
|
|
3 |
|
1 |
|
|
|
X |
|
|
0; 20 |
|
; 28 |
|
; 0; 0 |
|
является оптимальным для задачи, в которой требуется |
|
|
|
|||||||
|
|
|
|
4 |
|
2 |
|
|
|
найти максимум функции (7.4) при условиях (7.3) и условиях
неотрицательности переменных, F X 1 49 |
1 |
– наибольшее значение |
|
4 |
|||
|
|
функции (7.4).
План X 1 не удовлетворяет условию целочисленности.
Запишем систему уравнений, соответствующую последней таблице:
|
3 |
|
x x |
1 |
|
x 28 |
1 |
, |
|
|
|
|||||||
|
|
|
|
|
|
|||||||||||||
|
2 |
1 |
3 |
2 |
4 |
|
|
2 |
|
|
|
|
||||||
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
(7.5) |
|||||
|
|
3 |
|
|
|
1 |
|
|
|
1 |
|
|
|
3 |
|
|||
|
|
|
|
x1 x2 |
|
|
|
x4 |
|
|
|
x5 |
20 |
|
|
|||
4 |
|
4 |
|
2 |
4 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
и, согласно методу отсечений, составим неравенство Гомори, выбрав второе уравнение системы (7.5) (в этом уравнении наибольшая дробная часть свободного члена). Получаем
14 x1 14 x4 12 x5 43 ,
или
x1 x4 2x5 3.
Решим новую задачу линейного программирования, состоящую в максимизации линейной функции (7.4) при ограничениях:
|
3 |
|
x x |
|
1 |
|
x |
|
|
28 |
1 |
, |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
2 |
|
1 |
|
3 |
2 |
|
|
4 |
|
|
|
2 |
|
|
|
|
|
||||
|
|
|
3 |
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
3 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
x1 |
x2 |
|
|
|
|
|
x4 |
|
|
|
x5 |
20 |
|
, |
(7.6) |
||||
4 |
|
4 |
|
2 |
4 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
x1 |
x4 2x5 3; |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x j 0, |
j 1, 2, ..., 5; |
|
|
x j |
– целые числа. |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
29 |
|
|
|
|
|
|
Введем |
|
новую |
|
дополнительную переменную |
x6 x6 0 и заменим |
|||||||||||||||||
систему (7.6) системой уравнений |
|
||||||||||||||||||||||||||
|
3 |
|
x x |
|
1 |
|
x |
|
|
|
28 |
1 |
, |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
2 |
1 |
|
|
3 |
2 |
|
|
|
|
4 |
|
|
|
2 |
|
|
|
|
|
|
||||||
|
|
3 |
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
|
3 |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
x1 |
x2 |
|
|
|
|
|
|
|
x4 |
|
|
x5 |
20 |
|
|
, |
(7.7) |
||||||
4 |
|
4 |
|
2 |
4 |
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
x1 x4 2x5 x6 3. |
|
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Система (7.7) равносильна системе |
|
||||||||||||||||||||||||||
x |
|
2x |
|
3x |
|
3 |
x 24, |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
||||||||||||||||||||
|
3 |
|
|
|
4 |
|
5 |
|
|
|
2 |
6 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
x4 |
x5 |
|
|
|
|
|
23, |
|
|
|
|
|
|
(7.8) |
|
|||||||||
x2 |
|
|
|
|
x6 |
|
|
|
|
|
|
|
|||||||||||||||
|
4 |
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
x1 |
|
x4 2x5 x6 3, |
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
получающейся из системы (7.7) |
исключением неизвестной x1 из первого и |
||||||||||||||||||||||||||
второго уравнений. Задача о нахождении максимума линейной функции (7.4)
при ограничениях (7.8) и условиях неотрицательности переменных, является канонической. Составим симплексную таблицу (табл. 7.3).
Таблица 7.3
С |
|
|
Б |
|
|
f |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
fi |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
his |
|
|||||
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
–1 |
|
|
x3 |
|
24 |
0 |
0 |
1 |
–2 |
–3 |
|
3 |
|
|
21 |
1 |
|
|
|
|
|
|||
|
|
|
2 |
|
|
2 |
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
–1 |
|
|
x2 |
|
23 |
0 |
1 |
0 |
1 |
1 |
|
3 |
|
25 |
1 |
|
|
|
|
|
||||
|
|
|
|
|
4 |
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
–1 |
|
|
x1 |
|
3 |
1 |
0 |
0 |
1 |
2 |
–1 |
6 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
|
X * |
|
50 |
0 |
0 |
0 |
0 |
0 |
|
1 |
|
|
49 |
3 |
|
|
|
|
|||||
4 |
|
|
4 |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
30
Так как оценки всех свободных неизвестных неотрицательны, то план X * 3; 23; 24; 0; 0; 0 является оптимальным планом последней задачи,
F X * 50 – максимальное значение функции (7.4). Отсюда вытекает, что минимальное значение функции (7.1) равно 50 и достигается при x1 3, x2 23, x3 24 .
Ответ: необходимое количество заготовок будет получено из наименьшего количества досок (50 досок), если 3 доски распилить первым способом, 23 доски – вторым способом, 24 доски – третьим способом.
Вопросы для контроля.
1.Постановка задачи линейного программирования.
2.Графический метод решения задач линейного программирования.
3. Метод Гаусса-Жордана решения системы линейных уравнений. 4. Базисные решения системы линейных уравнений.
5. Допустимые базисные решения системы линейных уравнений.
6.Специальные линейные модели математического программирования.
7.Канонический вид задачи ЛП.
8.Симплексный метод решения задачи линейного программирования.
9.Основная схема алгоритма cимплексного метода.
10.Транспортная задача.
11.Закрытая транспортная задача.
12.Открытая транспортная задача.
13.Метод потенциалов решения транспортной задачи.
14.Постановка задачи целочисленного программирования.
15.Основные процедуры алгоритмической схемы “ветвей и границ“.
16.Метод потенциалов решения транспортной задачи.
17. Метод отсечений решения задач целочисленного программирования.
Библиографический список
Основная литература:
1. Красс М. С. Математика в экономике: математические методы и модели [Текст] : учеб. для бакалавров : рек. УМО ВО в качестве учеб. для студентов высш. учеб. заведений, обучающихся по эконом. направлениям и
31
специальностям / М. С. Красс, Б. П. Чупрынов; под ред. М. С. Красса; Финанс. ун-т при Правительстве РФ. - 2-е изд., испр. и доп. - М. : Юрайт, 2014. - 541 с. - Электронная версия в ЭБС "Юрайт".
Дополнительная литература:
1. Математика для экономистов: от Арифметики до Эконометрии [Текст] : учеб.-справ. пособие : рек. УМО вузов Рос. Федерации по образованию в обл. мат. методов в экономике в качестве учеб. пособия для студентов высш. учеб. заведений / Н. Ш. Кремер, Б. А. Путко, И. М. Тришин; под ред. Н. Ш. Кремера; Финанс. ун-т при Правительстве Рос. Федерации. - 4-е изд., перераб. и доп. - М. : Юрайт, 2014. - 724 с. - Электронная версия в ЭБС "Юрайт".
32