Экономических специальностей

БЕЛКООПСОЮЗ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

“БЕЛОРУССКИЙ ТОРГОВО-эКОНОМИЧЕсКИЙ

УНИВЕРСИТЕТ ПОТРЕБИТЕЛЬСКОЙ КООПЕРАЦИИ”

Кафедра высшей математики

МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ

Учебно-методическое пособие

для студентов 3 курса заочной формы обучения

Экономических специальностей

Гомель 2007

УДК 519.8

ББК 22.18

М 34

Авторы-составители:

С. А. Мокеева, канд. физ.-мат. наук, ст. преподаватель; И. А. Кузменкова, канд. физ.-мат. наук, ст. преподаватель; О. А. Мокеева, ассистент; Е. М. Миронович, ассистент; А. П. Кохно, канд. физ.-мат. наук, доцент

Рецензенты:

В. Н. Семенчук, д-р физ.-мат. наук, доцент, заведующий кафедрой высшей математики Гомельского государственного университета имени Ф. Скорины; Н. Д. Романенко, канд. физ.-мат. наук, доцент кафедры высшей математики Белорусского торгово- экономического университета потребительской кооперации

Рекомендовано к изданию научно-методическим советом учреждения образования “Белорусский торгово-экономический университет потребительской кооперации”. Протокол № 5 от 14 июня 2005 г.

М 34

Математическое программирование : учебно-методическое пособие для студентов 3 курса заочной формы обучения экономических специальностей / авт.-сост. : С. А. Мокеева [и др.]. – Гомель : учреждение образования “Белорусский торгово-экономический университет потребительской кооперации”, 2007. – 96 с. ISBN 978-985-461-448-9

УДК 519.8

ББК 22.18

ISBN 978-985-461-448-9

Ó Учреждение образования “Белорусский торгово-экономический университет потребительской кооперации”, 2007

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

При изучении математического программирования студенту потребуется знание общего курса высшей математики, теории вероятностей и математической статистики.

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

Вопросы к экзамену составлены на основании программы курса.

Список рекомендуемой литературы включает наименования основных литературных источников, которые предлагается использовать студентам при изучении курса “Математическое программирование” и выполнении тестовых заданий.

ОСНОВНЫЕ ВОПРОСЫ ПРОГРАММЫ КУРСА

Тема 1. Линейное программирование

Примеры задач линейного программирования. Геометрический метод решения.

Тема 2. Симплекс-метод

Основная идея симплекс-метода. Алгоритм симплекс-метода. Метод искусственного базиса.

Тема 3. Теория двойственности в линейном программировании

Понятие двойственности. Построение двойственных задач и их свойства. Основные теоремы двойственности.

Тема 4. Транспортная задача

Закрытая и открытая модели транспортной задачи. Исходный опорный план и его построение способами северо-западного угла и минимальной стоимости. Метод потенциалов для решения транспортной задачи. Оптимальный план.

Тема 6. Нелинейное программирование

Общая задача нелинейного программирования. Метод множителей Лагранжа.

Вопросы для самоконтроля

1. Общая постановка задачи линейного программирования и формы ее записи. Особенности канонической формы записи этой задачи.

2. Определение невырожденного, вырожденного, опорного и оптимального планов.

3. Переход от задачи минимизации к задаче максимизации и наоборот.

4. Геометрическая интерпретация задачи линейного программирования.

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

6. Случаи, в которых выполняются следующие условия:

· оптимальный план единственный;

· оптимальных планов бесконечное множество;

· целевая функция не ограничена;

· задача не имеет решения;

· целевая функция достигает одновременно и максимального, и минимального значений.

Геометрическая интерпретация.

2. Симплексный метод в решении задач
линейного программирования

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

2.1. Построение начального опорного плана

Рассмотрим три случая построения начального опорного плана.

Первый случай. Пусть ЗЛП представлена системой ограничений в каноническом виде

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательности правой части (b_i ³ 0) левая часть ограничения содержит переменную с коэффициентом, равным единице, а остальные ограничения – с коэффициентом, равным нулю.

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

Второй случай. Пусть система ограничений имеет вид

.

Сведем задачу к каноническому виду. Для этого добавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:

,

которая имеет предпочтительный вид. Следовательно, начальный опорный план примет следующий вид:

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю: .

Третий случай. Пусть система ограничений имеет вид

.

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

.

Теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные x_n+i входят в левую часть (при b_i ³ 0) с коэффициентами, равными –1. В этом случае вводится так называемый искусственный базис путем перехода к М-задаче. Ее рассмотрим в пункте 2.9.

Симплексные таблицы

Приведя модель ЗЛП к предпочтительному виду, ее заносят в так называемую симплексную таблицу (табл. 1).

Таблица 1

БП

сБ

А0

x1

…

xj

…

xn

xn+1

xn+2

…

xn+i

…

xn+m

c1

…

cj

…

cn

cn+1

cn+2

…

cn+i

…

cn+m

xn+1

cn+1

bn+1

a11

…

a1j

…

a1n

…

…

xn+2

cn+2

bn+2

a21

…

a2j

…

a2n

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

xn+i

cn+i

bn+i

ai1

…

aij

…

ain

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

xn+m

cn+m

bn+m

am1

…

amj

…

amn

…

…

zj – cj

D0

D1

…

Dj

…

Dn

…

…

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

Применяются следующие обозначения:

· x₁, …, x_j, …, x_n – свободные переменные;

· x_n+1, x_n+2, …, x_n+i, …, x_n+m – базисные (предпочтительные) переменные;

· c₁, …, c_j, …, c_n – коэффициенты целевой функции при свободных переменных;

· с_Б = (c_n+1; c_n+2; …; c_n+i; …; c_n+m) – вектор коэффициентов целевой функции при базисных переменных;

· A₀ = (b_n+1; b_n+2; …; b_n+i; …; b_n+m)^Т – вектор-столбец свободных членов системы ограничений;

· A_j = (a_1j; a_2j; …; a_ij; …; a_mj)^T – вектор-столбец коэффициентов при переменных х_j;

· D₀ = c_Б × А₀ – значение целевой функции для начального опорного плана x₀, т. е. D₀ = z(x₀);

· D_j = c_Б × А_j – c_j – оценки свободных переменных;

· .

Последнюю строку (z_j – c_j) таблицы называют индексной строкой (строкой целевой функции или строкой оценок).

2.3. Признак оптимальности опорного плана

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

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

2.4. Переход к нехудшему опорному плану

Рассмотрим ЗЛП на максимум. Приведем ее к каноническому виду и занесем в симплексную таблицу.

Если все D_j ³ 0, то начальный опорный план x₀ оптимален.

Если же существуют D_j < 0, то план неоптимален, при определенных условиях его можно улучшить.

С этой целью выбирают разрешающий элемент.

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

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

Замечание. Если задача решается на минимум, то разрешающий столбец выбирается из условия .

Выбор разрешающей строки. Находят отношения . Они называются симплексными.

Среди симплексных отношений определяют наименьшее, т. е.

.

Если это условие выполняется при нескольких i, то в качестве i₀ можно выбрать любое.

Оно и укажет строку, в которой содержится исключаемая из базиса переменная Строка i₀, соответствующая минимальному симплексному отношению, называется разрешающей.

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

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

Замечание. Поскольку min z = –max (–z), задачу минимизации можно формально заменить задачей максимизации функции –z. Затем полученный максимум следует взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

2.5. Симплексные преобразования

Чтобы завершить шаг преобразований, ведущих к новому опорному плану, составляют таблицу по следующим правилам:

1. элементы строки i₀ новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разрешающий элемент.

2. все элементы столбца j₀ новой таблицы равны нулю, за исключением .

3. чтобы получить все остальные элементы (включая элементы индексной строки) новой таблицы, нужно воспользоваться правилом прямоугольника (рис. 6).

Рис. 6

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

.

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

Контроль вычислений

Для контроля вычислений элементов индексной строки применяются формулы D₀ = c_Б × А₀, D_j = с_б × А_j – c_j.

2.7. Альтернативный оптимум (признак бесконечности
множества оптимальных планов)

Теорема 3.Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов.

Следствие. Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки свободных переменных положительны, то найденный оптимальный план единственный.

Вопросы для самоконтроля

1. Суть симплекс-метода. Свойства задач линейного программирования, на которых он основан.

2. Последовательность этапов практической реализации алгоритма симплекс-метода при решении задач линейного программирования.

3. Построение начального опорного плана (3 случая).

4. Случаи, когда опорный план оптимален.

5. Переход к нехудшему опорному плану.

6. Симплексные преобразования.

7. Признак бесконечности множества оптимальных планов.

8. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание.

9. Признак неограниченности целевой функции.

10. Необходимость использования симплекс-метода с искусственным базисом (М-метода). Суть этой модификации симплекс-метода.

11. Определение искусственной переменной. Случаи, при которых она вводится. Коэффициент, соответствующий ей в линейной функции. Проведение анализа плана по индексной строке.

12. Признак несовместности системы ограничений.

Вопросы для самоконтроля

1. Определение двойственной задачи в линейном программировании.

2. Модели двойственных задач.

3. Правила для построения двойственной задачи.

4. Основные теоремы теории двойственности и достаточный признак оптимальности.

5. Экономический смысл теорем двойственности, экономическая интерпретация свойств двойственных оценок.

Транспортная задача

4.1. Постановка транспортной задачи по критерию
стоимости в матричной форме

В m пунктах отправления A₁, A₂, …, A_m, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим a₁, a₂,…, a_m. Данный продукт потребляется в n пунктах B₁, B₂,…, B_n, которые будем называть потребителями; объем потребления обозначим b₁, b₂, …, b_n. Известны расходы (транспортные издержки) на перевозку единицы продукта из пункта A_i (i = 1, 2, …, m) в пункт B_j (j = 1, 2, …, n), которые равны c_ij и приведены в матрице транспортных расходов (издержек) C = (c_ij).

Требуется составить план перевозок, при котором весь продукт вывозится из пунктов A_i в пункты B_j в соответствии с потребностью и общая величина транспортных расходов (издержек) будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_i в пункт B_j, через x_ij. Предполагается, что все x_ij ³ 0. Совокупность всех переменных x_ij для краткости обозначим X.

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

	(15)
	(16)
	(17)

при этом (15) – целевая функция, (16) – ограничения по потребностям и запасам, (17) – условие неотрицательности.

Стоимость всех перевозок выражается линейной функцией (15). Условия (16) означают полное удовлетворение спроса во всех пунктах потребления и определяют полный вывоз продукции от всех поставщиков.

Для наглядности условие транспортной задачи (ТЗ) можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (матрицей планирования).

Матрицу X = (x_ij)_m´n будем называть матрицей перевозок,матрицу C = (c_ij)_m´n – матрицей тарифов, а число c_ij – тарифом клетки (i; j).

Будем называть план перевозок X = (x_ij)_m´n допустимым, если он удовлетворяет ограничениям (16).

Допустимый план перевозок, доставляющий минимум целевой функции (15), называется оптимальным.

Таблица 13

Потребители, Вj	В1	В2	…	Вп	Запасы, аi
Поставщики, Аi
	c11	c12		c1n
A1	x11	x12	…	x1n	a1
	c21	c22		c2n
A2	x21	x22	…	x2n	a2
	cm1	cm2		cmn
Am	xm1	xm2	…	xmn	am
Потребности, bj	b1	b2	…	bn

Теорема 8 (о существовании допустимого плана). Для того, чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства

(18)

(сумма запасов продукта равна сумме спроса на него).

Условие (18) является условием баланса.

Метод потенциалов

Сущность этого метода состоит в следующем. После того, как найден первоначальный невырожденный план перевозок, каждому поставщику A_i (каждой строке) ставится в соответствие некоторое число , а каждому потребителю B_j (каждому столбцу) – некоторое число . Числа u_i, v_j – потенциалы A_i и B_j (u_i, v_j произвольного знака).

Согласно теореме о потенциалах, числа u_i и v_j выбирают так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетки, т. е.

.

(21)

Так как всех занятых клеток должно быть m + n – 1, а чисел u_i и v_j должно быть m + n, то для нахождения потенциалов u_i, v_j получаем систему из m + n – 1 уравнений (21) с m + n неизвестными. В этой системе уравнений на одно меньше, чем неизвестных, поэтому один потенциал можно задать произвольно, например равным нулю. Тогда остальные потенциалы определяются однозначно.

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

.

(22)

При этом S_ij – оценка свободной клетки.

Если для всех свободных клеток оценки S_ij ³ 0, то опорный план перевозок является оптимальным.

Если хотя бы для одной из клеток S_ij < 0, то план неоптимален, и нужно переходить к новому плану.

4.5. Переход к новому плану

порядок перехода к новому плану следующий:

1. Клетка, для которой значение S_ij минимально, является перспективной и подлежит загрузке. Если таких клеток несколько, то берем любую.

2. Для выбранной перспективной клетки строим цикл, т. е. составляем замкнутый контур, по которому следует перераспределить груз. Цикл строится лишь для свободной клетки. Если из занятых клеток образуется цикл, то план перевозок не является опорным. Контур представляет собой замкнутую ломаную линию, состоящую из горизонтальных и вертикальных направленных отрезков (пересекаются под прямым углом), соединяющих середины клеток, из которых одна (именно перспективная) свободна, а все остальные загружены. В цикле всегда четное число клеток. Для каждой свободной клетки такой контур существует и является единственным. Точка, в которой меняется направление контура (горизонтальное на вертикальное или наоборот), называется вершиной цикла. В одной строке или одном столбце могут находиться две и только две вершины.

Точки самопересечения контура вершинами не являются.

Некоторые примеры циклов приведены на рис. 7.

рис. 7

3. Расставим поочередно знаки “+” и “–” в вершинах цикла. В перспективной клетке ставим знак “+”; затем, двигаясь по вершинам цикла, ставим поочередно знаки “–” и “+”, пока не придем к исходной вершине.

4. В клетках, соответствующих “отрицательным” вершинам, отыскивается наименьший груз (обозначим его q), который “перемещается” по клеткам цикла, т. е. прибавляется к поставкам x_ij в клетках со знаком “+” (включая свободную) и вычитается в клетках со знаком “–”.

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

Процесс продолжается, пока не получится оптимальный план перевозок. В результате остается подсчитать минимальные расходы (z_min).

Примечание. Если все S_ij > 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка S_ij = 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

4.6. Алгоритм решения транспортной задачи
методом потенциалов

приведем алгоритм метода потенциалов:

1. Условие задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас продукта с суммарным спросом и в случае нарушения равенства (18) вводят фиктивного поставщика (потребителя).

3. Строят начальный опорный план по одному из правил.

4. Вычисляют потенциалы поставщиков и потребителей u_i и v_j , решив систему уравнений типа (21).

5. Вычисляют оценки S_ij для всех свободных клеток по формуле (22). Если оценки всех свободных клеток неотрицательны, то исследуемый план является оптимальным, и остается подсчитать транспортные расходы. Если же среди оценок есть отрицательные, то выбирают клетку с наименьшей отрицательной оценкой и переходят к следующему пункту алгоритма.

6. Загружают выделенную в предыдущем пункте свободную клетку (пункт 4.5), получают новый опорный план и возвращаются к пункту 4 алгоритма.

Пример 8. Решить транспортную задачу методом потенциалов, для которой известно, что a_i – запас груза i-го поставщика, b_j – потребность j-го потребителя, C = (c_ij) – матрица затрат на перевозку одной единицы груза:

a1 = 12; a2 = 3; a3 = 10;

b1 = 14; b2 = 10; b3 = 6;

.

Решение

Поместим все данные задачи в табл. 14.

Таблица 14

bj
ai

Проверим, сколько единиц однородного продукта содержат поставщики (12 + 3 + 10 = 25) и сколько единиц однородного продукта нужно доставить потребителям (14 + 10 + 6 = 30).

Так как 25 < 30, т. е. , то имеем открытую модель транспортной задачи.

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

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

.

Все тарифы на доставку продукта фиктивным поставщиком равны нулю: .

Имеем ТЗ закрытого типа, которую решаем методом потенциалов (табл. 15).

Построим первоначальный (опорный) план методом “минимального элемента” (табл. 16).

Таблица 15

	bj
	ai

Таблица 16

	bj
	ai

В результате получаем матрицу перевозок

План X₁ является невырожденным (m + n – 1 = 4 + 3 – 1 = 6). Общая стоимость перевозки грузов по этому плану составит

z₁ = 1 × 7 + 0 × 5 + 1 × 3 + 4 × 7 + 5 × 3 + 0 × 5 = 53.

Потенциалы поставщиков и потребителей определены непосредственно на рис. 8.

	7 –	5 +
	7 +		3 –
5		5 –	· +

Рис. 8

Имеют место следующие оценки свободных клеток:

S13 = 2 – (–3 + 5) = 0;	S32 = 6 – (0 + 3) = 3 > 0;
S21 = 3 – (– 4 + 4) = 3 > 0;	S41 = 0 – (–3+ 4) = –1 < 0;
S22 = 4 – (– 4 + 3) = 5 > 0;	S43 = 0 – (–3 + 5) = –2 < 0.

Так как S₄₁ < 0 и S₄₃ < 0, то план является неоптимальным. Наиболее потенциальной и перспективной является клетка (4; 3). Строим для клетки (4; 3) цикл непосредственно на рис. 8. В цикл войдут клетки (4; 3), (3; 3), (3; 1), (1; 1), (1; 2), (4; 2). Проставим знаки “+” и “–” в цикле поочередно, начиная со свободной клетки. Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, – . В результате смещения по циклу получим новый план (рис. 9).

Для этого плана определяем новые потенциалы и оценки свободных клеток:

S13 = 2 – (0 + 0) = 2 > 0;	S32 = 6 – (3 + 0) = 3 > 0;
S21 = 3 – (1 + 1) = 1 > 0;	S33 = 5 – (3 + 0) = 2 > 0;
S22 = 4 – (1 + 0) = 3 > 0;	S41 = 0 – (0 + 1) = –1 < 0.

	4 –	8 +		u1 = 0
				u2 = 1
				u3 = 3
5	+ ·	–		u4 = 0
	v1 = 1	v2 = 0	v3 = 0

Рис. 9

Так как S₄₁ < 0, то план является неоптимальным. Строим для клетки (4; 1) цикл непосредственно на рис. 9. В цикл войдут клетки (4; 1), (1; 1), (1; 2), (4; 2). Проставим знаки в цикле. В отрицательных вершинах построенного для клетки (4; 1) цикла наименьшее количество груза – .

После смещения по циклу 2 единиц груза получим новый план перевозок (рис. 10).

				u1 = 0
				u2 = 0
				u3 = 3
				u4 = –1
	v1 = 1	v2 = 0	v3 = 1

Рис. 10

Как и для предыдущего плана перевозок, все потенциалы поставщиков и потребителей определены на рис. 10. Имеют место следующие оценки свободных клеток:

S13 = 2 – (0 + 1) = 1 > 0,	S32 = 6 – (3 + 0) = 3 > 0,
S21 = 3 – (0 + 1) = 2 > 0,	S33 = 5 – (3 + 1) = 1 > 0,
S22 = 4 – (0 + 0) = 4 > 0,	S42 = 0 – (–1 + 0) = 1 > 0.

Оценки всех свободных клеток положительны, полученный план перевозок является оптимальным и единственным:

.

Наши рекомендации