Материал: 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

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

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