3376

Количество заполненных клеток равно m n 1 3 4 1 6, поэтому построенный опорный план (обозначим его X 2 ) является невырожденным. Подсчитаем стоимость всех перевозок:

F X 2 20 30 20 20 40 5 40 5 60 2 80 18 2960 р.

Так как F X 2 F X 1 , то в качестве исходного опорного плана при

применении метода потенциалов выберем план X 2 .

Составим систему уравнений для нахождения потенциалов:

u1 v2 20,u1 v3 40,u2 v3 60,u2 v4 80,u3 v1 20,u3 v3 40.

Положим v3 0 . Тогда u1 40 , u2 60 , u3 40 , v2 20 , v4 20 , v1 20 . Проверяем, выполнено ли неравенство (12.4) для пустых клеток таблицы 12.4:

u1 v1 40 ( 20) 20 40, u1 v4 40 20 60 70,

u2 v1 60 ( 20) 40 70, u2 v2 60 ( 20) 40 60, u3 v1 40 ( 20) 20 20, u3 v4 40 20 60 50 c34.

Видим, что неравенство (6.4) не выполнено для клетки (3;4), поэтому план X 2 не является оптимальным. Составим цикл, соответствующий клетке (3;4), и пометим его клетки знаками + и – (см. табл. 6.5).

Таблица 6.5

Видим, что новый план выгоднее предыдущего.

Переходим к следующему шагу. Составляем систему уравнений для нахождения потенциалов:

u1 v2 20,u1 v3 40,

u2 v3 60,u2 v4 80,

u3 v1 20,u3 v4 50.

v1 30 . Проверяем, выполнено ли неравенство (6.4) для пустых клеток таблицы

12.6:

24

u1 v1 0 30 40, u1 v4 0 60 70, u2 v1 20 30 70, u2 v2 20 20 60,

u3 v2 10 20 20, u3 v3 10 40 40.

Итак, неравенство (6.4) выполнено для всех пустых клеток последней таблицы. Следовательно, план X 3 является оптимальным.

Ответ: транспортные расходы являются минимальными при плане перевозок, содержащемся в таблице 6.6.

7. МЕТОД ОТСЕЧЕНИЙ РЕШЕНИЯ ЗАДАЧ

ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Рассмотрим задачу целочисленного программирования: найти максимум (или минимум) линейной функции (5.1) при условиях (3.1), (5.2), а также при дополнительном условии:

x j – целые числа, j 1, 2, ..., n

(условия целочисленности).

Напомним, что целой частью b числа b называется наибольшее целое число,

не превосходящее b , дробной частью b числа b называется разность b b . Опишем метод отсечений (Гомори) решения сформулированной задачи целочисленного программирования. Он включает в себя следующие этапы:

1.Симплексным методом решаем соответствующую задачу линейного программирования без условия целочисленности и находим еѐ оптимальный план.

2. Проверяем, является ли полученный оптимальный план целочисленным. Если оптимальный план удовлетворяет условию целочисленности, то процесс решения заканчивается. Иначе переходим к следующему этапу.

25

3. На основании последней симплексной таблицы составляем неравенство Гомори

hi0 j x j fi0 ,

j

где fi0 – наибольшее из значений дробных частей свободных членов (правых

при свободных неизвестных в строке с номером i0 . Неравенство Гомори добавляется к системе ограничений, в результате чего получается новая задача линейного программирования. После этого переходим к пункту 1.

Пример 7.1.

Доски длинной l 3,5 м, имеющиеся в достаточном количестве, нужно

заготовок второго вида не менее n2 70 штук.

Каждая доска может быть распилена на указанные заготовки несколькими способами.

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

Решение.

Определим все возможные способы распила доски на заготовки нужной длины. Доску длиной 3,5 м можно распилить:

1)на 3 заготовки первого вида (длиной 1 м);

2)на 2 заготовки второго вида (длиной 1,5 м);

3)на 2 заготовки первого вида и 1 заготовку второго вида, причем в последнем случае доска раскраивается без остатка.

26

Пусть x1 , x2 , x3 – число досок, распиливаемых первым, вторым и третьим способами соответственно. Очевидно, x1 , x2 , x3 – целые неотрицательные числа.

при условиях, что переменные x1 , x2 , x3 удовлетворяют системе неравенств

неотрицательны и, кроме того, целочисленны.

Введем дополнительные переменные x4 , x5 ( x4 0, x5 0 ) и заменим систему неравенств (7.2) системой уравнений

3x1 2x3 x4 57,

2x2 x3 x5 70,

или эквивалентной ей системой уравнений

Таким образом, мы получили задачу целочисленного программирования: требуется найти минимум функции (7.1) при условиях (7.3), где x j , j 1, 2, ..., 5

– неотрицательные целые числа.

Перейдем от этой задачи к следующей задаче: найти максимум функции

для переменных x1 , x2 , x3 , x4 , x5 , удовлетворяющих системе ограничений (7.3), условиям неотрицательности и условиям целочисленности.

Решив последнюю задачу, мы получим значения переменных, при которых функция (7.1) достигает минимума.

Решим последнюю задачу методом отсечений.

Найдем оптимальный план соответствующей КЗЛП без условия целочисленности.

Составим симплексные таблицы (табл. 7.1, 7.2).

Таблица 7.2

28

Так как оценки всех свободных неизвестных положительны, то план

найти максимум функции (7.4) при условиях (7.3) и условиях

функции (7.4).

План X 1 не удовлетворяет условию целочисленности.

Запишем систему уравнений, соответствующую последней таблице:

и, согласно методу отсечений, составим неравенство Гомори, выбрав второе уравнение системы (7.5) (в этом уравнении наибольшая дробная часть свободного члена). Получаем

14 x1 14 x4 12 x5 43 ,

или

x1 x4 2x5 3.

Решим новую задачу линейного программирования, состоящую в максимизации линейной функции (7.4) при ограничениях:

второго уравнений. Задача о нахождении максимума линейной функции (7.4)

при ограничениях (7.8) и условиях неотрицательности переменных, является канонической. Составим симплексную таблицу (табл. 7.3).

Таблица 7.3

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