Элементы математического программирования

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

Элементы математического программирования

 

 

Методические указания и контрольные задания

для студентов экономических специальностей БНТУ

 

 

Минск 2006

 

УДК 380.105 (075.8)

ББК 22.171

Л 26

 

Рецензенты:

 

В.Ф.Бубнов, А.Н.Рудый

 

 

Корзников А.Д., Матвеева Л.Д., Смирнов М.Б.

Л26 Элементы математического программирования: Методическое пособие для студентов экономических специальностей БНТУ/ Корзников А.Д., Матвеева Л.Д., Смирнов М.Б.. – Мн.: БНТУ, 2006. – 68 с.

 

Под общей редакцией А.Д.Корзникова

 

ISBN 985-479-172-6.

 

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

Пособие предназначено для студентов экономических специальностей заочного отделения БНТУ; оно может быть также полезно преподавателям, ведущим практические занятия по курсу математического программирова­ния.

 

 

Ó БНТУ 2006

 

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

 

Задание 2. Геометрическим методом найти максимум и минимум функции Z для x, y ³ 0 при заданных ограничениях:

 

Варианты:

 

1. Z = 2x + y 2. Z = 3x + y

3x - 4y £ 4 y £ 1

-x + 6y £ 8 x - 2y £ 3

x + y ³ 1 2x + y ³ 1

 

3. Z = 2x - y 4. Z = x + y

2x + y £ 3 y ³ 2

x + y ³ 6 x + y £ 7

x - 3y £ 3 -x + 2y £ 2

 

5. Z = 4x + y 6. Z = 3x - y

x - 2y ³ 0 2x + 3y £ 13

4x - y £ 14 x ³ 2

3x + y ³ 7 5x - 3y £ 22

 

 

7. Z = 2x + y 8. Z = x + 5y

x ³ 2 3x - y ³ 3

4x - y £ 8 x - y £ 4

x - y ³ -1 x + y ³ 6

 

9. Z = 5x + y 10. Z = 3x

x - 4y ³ -3 x + y £ 7

4x - 3y £ 14 2x - y £ 11

3x + y ³ 4 4x + y ³ 19

Алгоритм Симплекс-метода

Исходные данные: задача в канонической форме; целевая функция мини­мизируется; найдено начальное базисное допустимое решение (опорный план),

то есть система уравнений (2) имеет базис и все правые части уравнений b_i ³ 0 - неотрицательны; целевая функция выражена через свободные переменные.

При выполнении этих условий каждая итерация метода состоит из трех шагов:

Шаг 1. Имеющийся план проверяется на оптимальность. Если в Z – стро­ке нет отрицательных элементов, то имеющийся план оптимален и задача реше­на. Если отрицательные элементы есть, то план не оптимален. Выбираем любой отрицательный элемент Z – строки (как правило, максимальный по модулю) и считаем столбец, в котором он находится в качестве разрешающего. Пусть для определенности это столбец переменной х_s.

Шаг 2. Выбор разрешающей строки. Пусть разрешающий столбец, вы­бранный на предыдущем шаге, это столбец переменной х_s. Для каждой i -ой строки (i = 1,...,m) делим элементы столбца свободных членов “Значение” (напомним, что все они неотрицательные) на положительные элементы разрешающего столбца, стоящие в этой строке, и находим минимальное из полученных частных, т.е. находим

Пусть этот минимум достигается в строке r. Тогда r -ая строка является разрешающей, элемент a_rs - разрешающий элемент таблицы.

Шаг 3. Пересчет таблицы. Преобразованиями Жордана-Гаусса пересчи­тываем таблицу относительно разрешающего элемента a_rs, найденного на предыдущем шаге, для чего:

3.1. Делим разрешающую строку на разрешающий элемент. В результате, на месте элемента a_rs будет стоять а¢_rs = 1.

3.2. Ко всем остальным строкам таблицы (включая Z - строку) прибав­ляем полученную разрешающую, умноженную на элемент (-a_is), где i – номер изменяемой строки i =1,2,...,r-1,r+1,...,m. К Z – строке прибавляем разрешаю­щую строку, умноженную на (- c_s). Иначе говоря, элементы новой таблицы (со штрихом) вычисляются по формулам:

а¢_rj = a_rj / a_rs; - новые элементы разрешающей строки (j = 1, 2,..., n);

b¢_r = b_r / a_rs

а¢_ij = a_ij - a¢_rj× a_is; - новые элементы i-й строки (i =1, 2,...,m; j = 1, 2,..., n);

b¢_i = b_i - b¢_r × a_is

c¢_j = c_j - a¢_rj× c_s; - новые элементы Z - строки (j = 1, 2,..., n);

Z¢ = Z - b¢_r × c_s

В результате этих преобразований в столбце х_s везде будут стоять нули кроме r -строки, где будет 1, т.е. х_s будет новой базисной переменной, целевая функция будет выражена через новые свободные переменные, новый план Х¢ находится в столбце “Значение” и лучше предыдущего, так как значение целевой функции для нового плана равно -Z¢ < Z. Переходим к шагу 1 и повторяем всю процедуру для нового плана Х¢.

Поскольку базисных решений системы (2) конечное число, а каждое новое базисное решение лучше предыдущего, то этот процесс завершится за конечное число шагов.

 

Решение задачи линейного программирования в общем случае. Рас­смотрим следующую задачу ЛП:

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ ³ 2,

-x₁ + 2х₂ ³ 5,

x₁ + х₂ £ 10,

x_1, х₂ ³ 0.

Приведем ее к каноническому виду введением трех неотрицательных пе­ременных х₃, х₄, х₅. Получим задачу:

 

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ - х₃ = 2,

-x₁ + 2х₂ - х₄ = 5, (7)

x₁ + х₂ + х₅ = 10,

x_1, х₂, х₃, х₄, х₅ ³ 0.

При попытке решить эту задачу симплекс-методом возникает опреде­ленная трудность, связанная с тем, что нет очевидного начального базисного допустимого решения (опорного плана), так как переменные х₃ и х₄ не являют­ся базисными. Умножение первых двух уравнений на -1 также ничего не дает, поскольку соответствующее базисное решение (0, 0, -2, -5, 10) не будет до­пустимым. Пытаться просто перебирать базисные решения в попытке отыскать допустимое, нецелесообразно, так как неясно, имеет ли эта задача вообще допустимые решения.

Для решения проблемы применим метод искусственного базиса. Введем в первые два уравнения (третье не создает проблем) искусственные перемен­ные х₆ ³ 0 и х₇ ³ 0. В результате получим базис из переменных х₆, х₇, х₅.

2x₁ – х₂ - х₃ + х₆ = 2,

-x₁ + 2х₂ - х₄ + х₇ = 5, (8)

x₁ + х₂ + х₅ = 10,

 

Соответствующее базисное решение Х₀ = (0, 0, 0, 0, 10, 2, 5) является до­пустимым для ограничений (8). Однако ограничения (7) и (8) не являются экви­валентными в том смысле, что любому допустимому решению системы ограни­чений (8), в котором хотя бы одна искусственная переменная отлична от нуля, нельзя поставить в соответствие допустимое решение системы ограничений (7). С целью исключения искусственных переменных из базисного решения систе­мы ограничений (8), т.е. для получения допустимого базисного решения систе­мы ограничений (7), используем алгоритм симплекс-метода. Для того, чтобы искусственные переменные стали свободными, необходимо, чтобы они были равны нулю (сейчас х₆ = 2, х₇ = 5). Поэтому введем искусственную целевую функцию

W = х₆ + х₇.

и будем ее минимизировать при ограничениях (8). Если удастся найти базисное допустимое решение при котором W = 0 (сейчас W = 7), то тогда х₆ и х₇ будут равны нулю, поскольку они неотрицательны, и мы получим базис из основных и дополнительных переменных.

Таким образом, задача разбивается на два этапа. На первом этапе мини­мизируется искусственная целевая функция W. Этот этап закончится либо нахождением опорного плана исходной задачи (7), либо тем, что минимизи­ровать функцию W до нуля не удастся, т.е. допустимых планов нет, а значит (ввиду теоремы 1) и нет вообще допустимых решений задачи.

Если опорный план найдется, то на втором этапе решаем задачу симп­лекс-методом. Проиллюстрируем описанный выше метод искусственного бази­са, применив его к решению задачи (7).

Этап 1. Составим исходную симплекс-таблицу для задачи (8). Все вычис­ления будем проводить также и для целевой функции Z. Тогда после заверше­ния первого этапа получим целевую функцию Z, выраженную через свободные переменные.

 

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	0 0 0 0 0 1 1

 

Для того, чтобы начать минимизацию функции W, ее надо выразить через свободные переменные. Для этого, из W - строки вычтем первую и вторую строки. Получим

Таблица 1.

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	-1 -1 1 1 0 0 0	-7

 

Так как в W – строке есть отрицательные элементы, то выбираем в качест­ве разрешающего любой из первых двух столбцов, например первый. Посколь­ку min{2/2, 10/1} = 1 достигается в первой строке, то разрешающая строка – первая и разрешающий элемент а₁₁ = 2. Пересчитывая таблицу относительно этого элемента, получим новую таблицу:

Таблица 2.

Базис	х1 х2 х3 х4 х5 х7	Значение
x1 х7 x5	1 -½ -½ 0 0 0 0 3/2 -½ -1 0 1 0 3/2 ½ 0 1 0
- Z	0 -½ -3/2 0 0 0
- W	0 -3/2 ½ 1 0 0	-6

 

Так как переменная х₆ вышла из базиса, то в дальнейшем ее не исполь­зуем (вычеркиваем столбец х₆). Теперь разрешающим столбцом будет второй, разрешающей строкой – вторая и после пересчета получим (поскольку искусственная переменная х₇ выйдет из базиса, столбец х₇ также вычеркиваем):

Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

 

Этап 1 успешно завершен, так как искусственные переменные выведены из базиса и мы получили опорный план Х₀ = (3, 4, 0, 0, 3) исходной задачи (7), к которому можно применить алгоритм симплекс-метода. На втором этапе W - строка уже не нужна и мы ее вычеркиваем.

 

 

Этап 2. Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 -1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

 

Целевую функцию Z можно уменьшить (сейчас Z = -5) если ввести в базис х₃ или х₄.

Выбираем третий столбец в качестве разрешающего, т.к. –5/3 < -1/3. Разрешающей строкой будет третья, т.к. только в ней есть положительный эле­мент разрешающего столбца. Разрешающий элемент а₃₃ = 1. Пересчитывая таблицу, получим:

Таблица 4.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x3	1 0 0 1/3 2/3 0 1 0 -1/3 1/3 0 0 1 1 1
- Z	0 0 0 4/3 5/3

 

Поскольку в Z – строке таблицы 4 нет отрицательных элементов, то новый план Х₁ = (5, 5, 3, 0, 0) является оптимальным и Z_min = Z(5,5) = -10.

Задача решена полностью.

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 3. Решить задачу линейного программирования симплекс-методом (x, y ³ 0).

 

Варианты:

 

1. Z = x - 2y ® min 2. Z = -x + y ® min

3x + y ³ 8 3x - 2y ³ 7

4x + 5y £ 29 x + 2y £ 13

x + 4y ³ 10 x - 2y £ 1

 

3. Z = 2x + y ® max 4. Z = x - y ® max

-x + 2y ³ 3 -2x + 3y £ 5

-x + y £ 1 x + 2y ³ 8

3x - 2y £ 3 3x - y £ 10

 

 

5. Z = 2x + y ® max 6. Z = x + y ® max

x - y £ 0 x - y ³ 0

3x - 2y £ 3 -x + 2y £ 4

5x - 4y ³ 1 -3x + 4y ³ 2

 

7. Z = 5x + 2y ® max 8. Z = 2x + 4y ® max

3x + y ³ 9 3x + y ³ 8

2x + y ³ 7 -x + 3y ³ 4

5x + 2y £ 17 x + 2y £ 11

 

9. Z = 2x + y ® max 10. Z = x - y ® min

-x + 5y £ 4 x + 3y £ 7

x - y £ 4 2x - y £ 7

x + y ³ 2 5x + y ³ 7

 

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

 

Рассмотрим задачу линейного программирования в общей форме:

Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n ® max (1)

при ограничениях:

y ₁³0 a₁₁ x₁ + a₁₂ x₂ +...+ a_1n x_n £ b₁

y ₂³0 a₂₁ x₁ + a₂₂ x₂ +...+ a_2n x_n £ b₂

....................................... (2)

y _k³0 a_k1 x₁ + a_k2 x₂ +...+ a_kn x_n £ b_k

y _k+1 a_{k+1 1} x₁ + a_{k+1 2} x₂ +...+ a_{k+1 n} x_n = b_k+1

.......................................

y _m a_m1 x₁ + a_m2 x₂ +...+ a_mn x_n = b_m,

x_j ³ 0, j = 1,..., l; l £ n (3)

Каждому i -му ограничению из (2) соответствует переменная y _i так назы­ваемой двойственной задачи к задаче (1) – (3) (показана слева от соответст­вующего ограничения).

Двойственная задача имеет вид:

W = b₁ y₁ + b₂ y₂ +...+ b_m x_m ® min (4)

при ограничениях:

x₁ ³ 0 a₁₁ y₁ + a₂₁ y₂ +...+ a_m1 y_m ³ c₁

x₂ ³ 0 a₁₂ y₁ + a₂₂ y₂ +...+ a_m2 y_m ³ c₂

....................................... (5 )

x_l ³ 0 a_1l y₁ + a_2l y₂ +...+ a_ml y_m ³ c_l

x_l+1 a_{1 l+1} y₁ + a_{2 l+1} y₂ +...+ a _{m l+1} y_m = c_l+1

.......................................

x_n a_1n y₁ + a_2n y₂ +...+ a_mn y_m = c_n,

y_i ³ 0, i = 1,..., k; k £ n (6)

Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственнойпарой.

Сравнивая две задачи, видим, что двойственная задача по отношению к исходной (прямой) содержит те же самые коэффициенты a_ij, b_i, c_j и состав­ляется согласно следующим правилам:

1. Целевая функция (1) исходной задачи задается на максимум, а целевая функция (4) двойственной задачи – на минимум.

2. Матрица А^Т, составленная из коэффициентов при неизвестных в системе ограничений (5) двойственной задачи получается из матрицы А прямой задачи транспонированием (т.е. заменой строк столбцами):

а₁₁ а₁₂... а_1n a₁₁ a₂₁... a_m1

A = а₂₁ а₂₂... а_2n A^T = a₁₂ a₂₂... a_m2

.........................

а_m1 а_m2... а_mn a_1n a_2n... a_mn

 

3. Число переменных в двойственной задаче (4)–(6) равно числу ограниче­ний в системе (2) прямой задачи, а число ограничений в системе (5) двойствен­ной задачи равно числу переменных в прямой задаче.

4. Коэффициентами при неизвестных в целевой функции (4) двойственной задачи являются свободные члены в системе (2) прямой задачи и наоборот.

5. Если переменная x_j ³ 0, то j- ое ограничение в системе (5) двойственной задачи является неравенством “ ³ ”. Если же переменная x_j может иметь любой знак, то j -ое ограничение в системе (5) представляет собой уравнение.

Каждая из задач двойственной пары (1) – (3) и (4) – (6) фактически яв­ляется самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач, тем самым находится решение и другой задачи. Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже теоремами двойственности.

Теорема 1. (Основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план причем значения целевых функций задач при их оптимальных планах сов­падают, т.е. Z_max = W_min.

Если же целевая функция одной из задач не ограничена (для исходной (1) – (3) – сверху, для двойственной (4) – (6) – снизу), то другая задача вообще не имеет допустимых решений.

Теорема 2. (Вторая теорема двойственности). Для того, чтобы два до­пустимых решения и пары двойствен­ных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системам уравнений:

(7)

Замечание. Соотношения (7) верны только для ограничений в виде неравенств и для неотрицательных переменных.

 

Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в кано­нической форме. Вместе с тем двойственный симплекс-метод можно применять при решении задачи ЛП, свободные члены системы ограничений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).

Опишем алгоритм двойственного симплекс-метода. Рассмотрим задачу линейного программирования в канонической форме.

 

(8)

(9)

(10)

 

Пусть матрица ограничений А содержит единичную подматрицу порядка m и первые m переменных являются базисными. Среди чисел есть отрицательные. Вектор есть решение системы (9). Однако, это решение не является планом задачи (8) – (10), поскольку среди его компонент есть отрицательные числе (т.е. не выполняются ограничения (10)). Исключим базисные переменные из целевой функции z:

.

Предположим, что

Шаг 1. Составить исходную симплексную таблицу.

 

№ строки	Базис	x1	…	xm	xm+1	…	xk	…	xn	b
1 l m	x1 xl xm	1 0 0	… … …	0 0 1	a1m+1 alm+1 amm+1	… … …	ak a^*lk amk	… … …	a1n aln amn	b1 bl bm
m+1	-z	0	…	0	dm+1	…	dk	…	dn	-do

 

Шаг 2. Выяснить, имеется ли хотя бы одно отрицательное число среди элементов столбца b. Если нет, то перейти к шагу 8. Иначе – к шагу 3.

Шаг 3. Если отрицательных чисел в столбце b несколько, то выбрать наименьшее. Пусть, для определенности, это число . Строка с номером l – ведущая.

Шаг 4. Среди элементов ведущей строки l находят отрицатель­ные. Если таковых нет, то исходная задача не имеет решения. В противном случае перейти к шагу 5.

Шаг 5. Вычислить . Столбец с номером k – ведущий, - ведущий элемент.

Шаг 6. С помощью ведущего элемента провести одну итерацию метода Жордана-Гаусса.

Шаг 7. Построить новую симплексную таблицу и перейти к шагу 2.

Шаг 8. Задача линейного программирования (8) – (10) решена. По последней симплексной таблице выписать оптимальный план и минимальное значение целевой функции задачи (8) – (10).

Замечание. Если среди чисел есть отрицательные, то следует в системе ограничений (9) преобразовать свободные члены b_j в неотрица­тельные, умножив на (-1) строки, содержащие отрицательные свободные члены и решать задачу (8) – (10) методом искусствен­ного базиса.

 

Пример. Решить задачу линейного программирования:

Z = 6x₁ + 9x₂ + 3x₃ ® min

-x₁ + 2x₂ + x₃ ³ 2

3x₁ + x₂ – x₃ ³ 1 (11)

x_j ³ 0, j = 1, 2, 3.

 

Решение. Составим для задачи (11) двойственную:

W = 2y₁ + y₂ ® max

-y₁ + 3y₂ £ 6

2y₁ + y₂ £ 9 (12)

y₁ - y₂ £ 3

y₁, y₂ ³ 0

Для решения задачи (11) двойственным симплекс-методом приведем ее к каноническому виду. Для этого умножим первое и второе ограничения на (-1) и добавим соответствен­но неотрицательные дополнительные переменные x ₄ ³ 0, x₅ ³ 0:

Z = 6x₁ + 9x₂ + 3x₃ ® min

x₁ - 2x₂ - x₃ + x₄ = -2

-3x₁ - x₂ + x₃ + x₅ = -1 (13)

x_j ³ 0, j = 1, 2,..., 5.

Базисными переменными здесь являются переменные х ₄ и х ₅. Поскольку все коэффициенты с _j ³ 0, то критерий оптимальности для этого базисного ре­шения выполнен, однако само решение Х = (0, 0, 0, -2, -1) содержит отрица­тельные переменные, то есть не является допустимым. Естественно попытаться вывести отрицательные (не являющиеся допустимыми) переменные из базиса, сохранив при этом неотрицательность коэффициентов последней строки, так как в этом случае полученное допустимое решение будет являться и оптималь­ным. Такой подход является содержанием двойственного симплекс-метода. Проиллюстрируем его на примере решения задачи (13).

Составим исходную симплекс-таблицу.

 

Базис	х1 х2 х3 х4 х5	Значение (bi)
x 4 x 5	1 -2 -1^*1 0 -3 -1 1 0 1	-2 -1
- Z	6 9 3 0 0

 

Вычисляем Из базиса будем выводить пе­ременную x₄. Следовательно, первая строка таблицы является разрешающей. Среди элементов разрешающей строки находим отрицательные а ₁₂ = -2; a ₁₃ = -1.

Определяем Столбец, в кото­ром достигается этот минимум, соответствует переменной х ₃. Этот столбец является разрешающим и разрешающим элементом является элемент а ₁₃ = -1. Это делается для того, чтобы элементы последней строки остались неотрицательными. Проводим одну итерацию метода Жордана-Гаусса относи­тельно этого элемента, т.е. из базиса исключаем переменную х ₄ и включаем в базис переменную х ₃. Новая симплекс-таблица имеет вид:

 

Базис	х1 х2 х3 х4 х5	Значение (bi)
х 3 x 5	-1 2 1 -10 -2 -3^* 0 1 1	-3
- Z	9 3 0 3 0	-6

 

Элемент b ₂ = -3 < 0. Следовательно, разрешающей является вторая строка таблицы. Как и ранее, находим

Следовательно второй столбец – разрешающий, переменную х ₂ включаем в базис, переменную х ₅ исключаем из базиса. Пересчитывая таблицу относи­тельно элемента а ₂₂ = -3, получаем новую таблицу:

 

Базис	х1 х2 х3 х4 х5	Значение (bi)
х 3 x 2	-7/3 0 1 -1/32/3 2/3 1 0 -1/3 -1/3
- Z	7 0 0 4 1	-9

 

Среди элементов столбца “Значение” нет отрицательных чисел. В Z – строке также нет отрицательных чисел. Следовательно, найден оптимальный план: Х ^* = (0; 1; 0), при этом Z^* = Z_min = 9. По последней симплекс-таблице находим решение двойственной задачи (9). Для этого выясняем, какие перемен­ные задачи (10) входили в исходный базис. В первоначальной таблице это – х ₄, х ₅. В последней симплекс-таблице находим элементы Z – строки, соответст­вующие этим базисным переменным (с ₄ = 4, с ₅ = 1) и прибавляем к ним соот­ветствующие коэффициенты исходной целевой функции (с ₄ = с ₅ = 0). В ре­зультате получаем Y ^* = (4; 1), W ^* = W _max = 9.

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 4. Решить задачу линейного программирования двойственным симплекс-методом.

Варианты

 

1. 2.

3.	4.
5.	6.
7.	8.
9.	10.

 

V. ТРАНСПОРТНАЯ ЗАДАЧА

 

Общая постановка транспортной задачи состоит в определении оптималь­ного плана перевозок некоторого однородного груза из m пунктов отправления А ₁, А ₂,..., А _m в n пунктов назначения B₁, B ₂,..., B _n. При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Математическая модель транспортной задачи имеет вид: , (14)

(15)

(16)

(17)

 

Здесь c _ij - тарифы перевозки единицы груза из i – го пункта отправления А _i в j – ый пункт назначения B _j, b_j - потребность в грузе в j – ом пункте на­значения, a_i – запасы груза в i – ом пункте отправления.

Наличие линейных уравнений (15) и (16) обеспечивает доставку необхо­димого количества груза в каждый из пунктов назначения и вывоз всего имею­щегося груза из всех пунктов отправления. При этом, ввиду (17), исключаются обратные перевозки. Задача (14) – (17) является частным случаем задачи линей­ного программирования, однако, в силу своей специфики решается специаль­ным методом.

Если выполняется так называемое условие баланса

, (18)

то такая транспортная задача называется закрытой. Если условие баланса (18) не выполняется, то задача называется открытой.

Теорема 1. Для разрешимости транспортной задачи необходимо и доста­точно, чтобы выполнялось условие баланса (5).

Если то вводится фиктивный (n + 1) - ый пункт назначения с потребностью и соответствующие тарифы полагают рав­ными нулю, т.е. c _{i n+1} = 0 (i = 1,2,..., m). Аналогично, при вводится фиктивный, (m+1) – ый пункт отправления с запасами груза , при этом тарифы на перевозку из этого пункта также полагают равными нулю, c _{m+1 j} = 0.

Для решения задачи (14) – (17) применяется метод потенциалов, который по существу, является другой формой симплекс-метода.

Опишем алгоритм метода. Исходные данные транспортной задачи запишем в таблице

bj ai	b 1	b 2	...	b n
a 1	c 11	c 12	...	c 1n
a 2	c 21	c 22	...	c 2n
	...	...	...	...
a m	c m1	c m2	...	c mn

 

1. Построение начального опорного плана. Система ограничений (16)-(17) содержит m×n неизвестных и m+ n уравнений, связанных отношением (18). Невырожденный опорный план задачи содержит m + n – 1 положительных пе­ревозок или компонент. Таким образом, если каким-либо способом получен не­вырожденный опорный план задачи, то в матрице (x_ij) значений его компонент положительными являются только m + n – 1, а остальные равны нулю.

Клетки, в которых находятся отличные от нуля перевозки, называются за­нятыми, остальные – незанятыми. Занятые клетки соответствуют базисным не­известным, и для невырожденного опорного плана их количество равно m + n-1.

Для построения начального опорного плана применим метод минималь­ной стоимости.

Выбираем клетку с минимальной стоимостью (если их несколько, возь­мем любую из них). Пусть, например, . Тогда в клетку (l, k) записы­вают число . При этом, если , то значение b_k уменьшают на a_l и «закрывают» строку с номером l, так как ресурсы l -го поставщика исчерпаны. Если , то значение a_l уменьшают на b_k и «закрывают» столбец с номером k, что означает удовлетворение спроса k- го потребителя. Если же a_l = b_k, то «закрывают» строку или столбец по выбору.

Вышеописанную процедуру повторяют для оставшейся транспортной таблицы до тех пор, пока не будут закрыты все строки и столбцы.

2. Построение системы потенциалов. Система потенциалов строится для невырожденного опорного плана и имеет вид:

где - стоимость перевозки единицы груза занятой (базисной) клетки в i – ой строке и j -ом столбце.

Вычисление потенциалов удобно проводить по таблице, положив равным нулю один из потенциалов и затем последовательно находя все остальные по­тенциалы вычитанием из стоимостей базисных клеток уже известных потен­циалов. Потенциалы поставщиков записывают справа, а потенциалы потре­бителей - внизу транспортной таблицы.

3. Проверка опорного плана на оптимальность. Для каждой свободной клетки вычисляют оценки

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

4. Построение цикла и нахождение нового опорного плана. Среди отрица­тельных оценок выбираем наименьшую. Пусть

В клетке (l, k) нарушено условие оптимальности. Для улучшения опорно­го плана необходимо в клетку (l, k) отправить некоторое количество груза, превратив ее тем самым в базисную. Эта операция эквивалентна действию по замене базиса в симплекс-методе.

Клетку (l, k) отмечают