10

СОДЕРЖАНИЕ

• Введение 3
• 1. Основная задача линейного программирования 4
• 2. Симплекс-метод решения транспортных задач 10
• Заключение 16
• Список литературы 17

Введение

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

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

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

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

Рассмотрим задачу линейного программирования с ограничениями-равенствами -- так называемую основную задачу линейного программирования (ОЗ) [7].

Основная задача линейного программирования (ОЗ)

Основная задача линейного программирования ставится следующим образом.

Имеется ряд переменных

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

(2.12)

или в матричной форме:

где

(2.13)

и, кроме того, обращали бы в минимум линейную функцию

(2.14)

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

Условимся называть допустимым решением ОЗ любую совокупность переменных

удовлетворяющую уравнениям (2.12).

Оптимальным решением будем называть то из допустимых решений, при котором линейная функция (2.14) обращается в минимум.

Основная задача линейного программирования не обязательно должна иметь решение. Может оказаться, что уравнения (2.12) противоречат друг другу или они имеют решение, но не в области неотрицательных значенийТогда ОЗ не имеет допустимых решений. Наконец, может оказаться, что допустимые решения 03 существуют, но среди них нет оптимального: функция Z в области допустимых решений не ограничена снизу.

Рассмотрим, прежде всего, вопрос о существовании допустимых решений ОЗ.

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

Итак, пусть имеется система уравнений (2.12). Существуют ли неотрицательные значенияудовлетворяющие этой системе? Этот вопрос рассматривается в одном из разделов математики -- линейной алгебре [15].

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

Матрицей системы линейных уравнений (2.12) является таблица (2.13).

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

Рангом матрицы называется наибольший порядок отличного от нуля определителя, который можно получить, вычеркивая из матрицы какие-то строки и какие-то столбцы [15].

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

Итак, если система уравнений-ограничений ОЗ совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг. Этот общий ранг r называется рангом системы; он представляет собой не что иное, как число линейно независимых уравнений среди наложенных ограничений.

Очевидно, ранг системы r не может быть больше числа уравнений m:

Очевидно также, что ранг системы не может быть больше общего числа переменных:

Действительно, ранг матрицы системы определяется как наибольший порядок определителя, составленного из элементов матрицы; так как число ее строк равно m, то так как число ее столбцов равно n, то

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

Рассмотрим, прежде всего, случай, когда r = n, т. е. когда число линейно независимых уравнений, входящих в систему (2.12), равно числу переменных n. Если отбросить избыточные уравнения, являющиеся линейными комбинациями других, то система уравнений-ограничений ОЗ принимает вид (т.е. здесь m = n):

(2.15)

Так как r = n, то определитель, составленный из коэффициентов

не равен нулю. Из алгебры известно, что в этом случае система (2 15) имеет единственное решение. Чтобы найти компоненту решения достаточно в определителезаменить i-й столбец столбцомсвободных членов и полученный результат разделить на

Итак присистема уравнений-ограничений ОЗ имеет единственное решение:

Если в этом решении хотя бы одна из величин отрицательна, это значит, что полученное решение недопустимо и, значит, 03 не имеет решения.

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

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

Пример 2.6. Рассматривается система двух уравнений с четырьмя неизвестными:

(2.16)

Ранг этой системы r = 2 (уравнения линейно независимы). Выберем в качестве свободных переменных, например,и, а в качестве базисных --иВыразим базисные переменные через свободные. Имеем из уравнений (2.16):

Складывая эти уравнения, получаем

Умножая второе уравнение на 2 и складывая с первым, получаем

Таким образом, базисные переменныевыражены через свободные (и). Свободным переменным можно придавать любые значения; при этом мы будем всегда получать совокупность значенийудовлетворяющую системе уравнений (2.16). Например, полагая = 0, получаем = 3, = 5, и эти значения удовлетворяют системе (2.16).

Вообще, если ранг системы уравнений ОЗ (т. е. число линейно независимых уравнений, входящих в систему ограничений) равен r, то всегда можно выразить какие-то r базисных переменных через n - r остальных (свободных) и, придавая свободным переменным любые значения, получить бесчисленное множество решений системы.

В дальнейшем для простоты, записывая уравнения ОЗ, мы будем считать их линейно независимыми; при этом ранг системы r будет равен числу уравнений m.

Итак, если число уравнений 03 r = m меньше, чем число переменных n, то система линейных уравнений имеет бесчисленное множество решений, т. е. совокупностей значений удовлетворяющих уравнениям-ограничениям (2.12). Если среди этих решений нет ни одного, для которого все неотрицательны, то это значит, что 03 не имеет допустимого решения.

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

Для того чтобы отчетливее представить себе особенности решения 03 и различные случаи, которые могут при этом встретиться, удобно воспользоваться геометрической интерпретацией.

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

Геометрическая интерпретация, которой мы пользовались при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных переменных n - m > 3, а затруднительна уже при n - m = 3. Для нахождения решения задачи линейного программирования в общем случае (при произвольном числе свободных переменных) применяются не геометрические, а вычислительные методы. Из них наиболее универсальным является так называемый симплекс-метод.

Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется п переменных и т независимых линейных ограничений, заданных в форме уравнений. Мы знаем, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то к переменных в качестве свободных и выразим через них остальные т базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных а остальные m выражены через них:

(2.22)

Предположим, что все свободные переменные равны нулю.

При этом мы получим:

Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные членынеотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию Z через свободные переменные

(2.23)

Очевидно, что приПроверим, может ли быть улучшено решение, т. е. получено уменьшение функции Z c увеличением каких-нибудь из переменных (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициентыв (2.23) положительны, то увеличение каких-либо из переменныхне может уменьшить Z; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентовесть отрицательные, то, увеличивая некоторые из переменных(те, коэффициенты при которых отрицательны), мы можем улучшить решение.

Пусть, например, коэффициентв (2.23) отрицателен. Значит, есть смысл увеличить, т. е. перейти от данного опорного решения к другому, где переменнаяне равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличиватьследует с осторожностью, так чтобы не стали отрицательными другие переменныевыраженные через свободные переменные, в частности черезформулами (2.22).

Например, если коэффициент прив соответствующем уравнении (2.22) отрицателен, то увеличениеможет сделать отрицательным. Наоборот, если среди уравнений (2.22) нет уравнения с отрицательным коэффициентом прито величину можно увеличивать беспредельно, а, значит, линейная функция Z не ограничена снизу и оптимального решения ОЗ не существует.

Допустим, что это не так и что среди уравнений (2.22) есть такие, в которых коэффициент приотрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличение опасно -- оно может сделать их отрицательными.

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

Здесь свободный член, а коэффициентотрицателен.

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

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

Базисными переменными при этом будут

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

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

(2.24)

Требуется минимизировать линейную функцию

Приводя неравенства к стандартному видуи вводя добавочные переменныепереходим к условиям-равенствам:

(2.25)

Число переменных (n = 7) на 4 превышает число уравнений (т = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пусть в качестве свободных переменных выступают Положим их равными нулю и получим опорное решение:

При этих значениях переменных Z= 0.

Это решение не оптимально, поскольку в линейной функции Z коэффициент приотрицателен. Значит, увеличиваяможно уменьшить Z.

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

Определим, какая из этих переменных раньше обратится в нуль при увеличенииОчевидно, что этоона станет равной нулю приа величина-- только при = 5.

Выбирается переменная у, и вводится в число свободных вместоЧтобы разрешить систему (2.25) относительно поступим следующим образом. Разрешим первое уравнение (2.25) относительно новой базисной переменной

Это выражение подставляется вместо во второе уравнение:

(2.26)

Что касается третьего уравнения, то оно, как не содержащее не изменится. Система (2.25) приведена к виду со свободными переменнымии базисными

Выразим функцию Z через новые свободные переменные:

(2.27)

Положим теперь свободные переменные равными нулю. Функция приобретает значение Z=-2, что меньше (лучше), чем прежнее значение Z= 0.

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

Поменяем местами переменные-- первую исключим из числа свободных, а вторую -- включим. Для этого разрешим второе уравнение (2.26) относительнои подставимв первое уравнение. Получим следующий вид системы (2.25):

(2.28)

Выразим Z через новые свободные переменные:

(2.29)

Полагая , получим Z = -10.

Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении (2.29) неотрицательны. Итак, оптимальное решение ОЗ найдено:

При таких значениях переменных линейная функция Z принимает минимальное значение:

Заметим, что в рассмотренном примере нам не пришлось искать опорное решение: оно сразу же получилось, когда мы положили свободные переменные равными нулю. Это объясняется тем, что в уравнениях (2.25) все свободные члены были неотрицательны и, значит, первое же попавшееся решение оказалось опорным. Если это окажется не так, можно будет прийти к опорному решению с помощью такой же процедуры обмена местами некоторых базисных и свободных переменных, повторно решая уравнения до тех пор, пока свободные члены не станут неотрицательными [7].

Заключение

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

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

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

Список литературы

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.

2. Баумоль У. Экономическая теория и исследование операций. - М.; Наука, 2004.

3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.

4. Боровков А.А. Математическая статистика. М.: Наука, 2004.

5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004

6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.

7. Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.

8. Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.

9. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. - 3-е изд., исп. - М.: Дело, 2002.

10. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005

11. Пехелецкий И.Д. Математика: учебник для студентов. - М.: Академия, 2003.

12. Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.

13. Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебное пособие. - Димитровград, 2002