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

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

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

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

Целью данного курсового проекта является рассмотрение задачи линейного программирования, решения ее симплекс методом, а также с помощью табличного редактора MS Excel.

1. Постановка задачи

Управление городским автобусным парком решило провести исследование возможности более рациональной организации своей работы с целью снижения интенсивности внутригородского движения. Сбор и обработка необходимой информации позволили сделать вывод, что необходимое минимальное количество автобусов существенно меняется в течение суток. Длительность непрерывного использования автобусов на линии равна 8 ч в сутки (с учетом необходимых затрат времени на текущий ремонт и обслуживание). Необходимо узнать, какое количество автобусов нужно выпускать на линию в каждой из смен при условии, что общее количество автобусов, выходящих на линию в течение суток, должно быть минимальным (Таблица 1):

Таблица 1 - Расписание автобусов по сменам

2. Построение математической модели задачи

Пусть X₁ - смена 1, X₂ - смена 2, X₃ - смена 3, X₄ - смена 4, X₅ - смена 5, X₆ - смена 6.

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

X₁ + X₆?4,

X₁ + X₂?8,

X₂ + X₃?10,

X₃ + X₄?7,

X₄ + X₅?12,

X₅ + X₆?4,

X₁ , X₂ , X₃ , X₄ , X₅ , X₆ ? 0.

После чего целевая функция имеет вид:

Z(x) = X₁+X₂+X₃+X₄+X₅+X₆ > min

Математическая модель задачи имеет вид:

Z(x) = X₁+X₂+X₃+X₄+X₅+X₆ > min

X₁ + X₆?4,

X₁ + X₂?8,

X₂ + X₃?10,

X₃ + X₄?7,

X₄ + X₅?12,

X₅ + X₆?4,

X₁ , X₂ , X₃ , X₄ , X₅ , X₆ ? 0.

3. Основные теоретические сведения

Симплекс-метод

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

Симплекс-метод основывается на следующем:

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

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

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

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

Привести задачу к каноническому виду;

2. Определить число и состав базисных и свободных переменных;

3. Выразить базисные переменные через свободные. Число базисных переменных определяется по количеству ограничений. В общем случае, m любых переменных X₁, X₂,…,X_m можно выразить через оставшиеся X_m+1,X_m+2,…,X_n. Переменные X₁,…,X_n называются базисными, а переменные X_m+1,…, X_n - свободными.

Выразить целевую функцию через свободные переменные.

Построить начальную симплекс-таблицу.

Проверить решение на оптимальность: если в Д-строке все значения ? 0, то решение: X=(B₁,...,B_m) является оптимальным. Если же существует Д_j<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.

Д_j=? C_i - A_ij (1)

Рассмотрим все столбцы, в которых Д_j<0. Если существует хотя бы один такой столбец, у которого все коэффициенты A_ij<0, то задача решения не имеет, т.к. множество допустимых решений неограниченно, и целевая функция неограниченно возрастает. Если же таких столбцов нет, то улучшаем решение.

Строим новую симплекс-таблицу. Выбираем свободную переменную, которую нужно ввести в базис (выбор разрешающей строки). Рассмотрим какой-либо k-й столбец и все его элементы, которые больше 0. Для всех этих элементов находим отношение b_i / A_ik и выбираем строку, которая соответствует минимальному значению этого отношения. Соответствующая i переменная выводится из базиса. При нескольких одинаковых отношениях берем любую строку. Элемент A_ik называется разрешающим элементом (ключевым). Выбираем свободную переменную, которую надо ввести в базис. Выбор разрешающего (ключевого столбца). Это столбец с минимальным значением Д_j. Начинаем заполнять новую k-ю строку, записывая в нее элементы i-строки, поделенные на ключевой элемент. Оставшиеся строки заполняем следующим образом: k-ю строку последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы в k-м столбце получить везде 0 (кроме 1 в k-й строке).

После заполнения новой симплекс-таблицы, возвращаемся к проверке оптимальности решения (пункт 6).

4. Решение задачи симплекс-методом

Приведем задачу к каноническому виду:

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

автобус расписание симплекс математический

X₁ + X₆?4,

X₁ + X₂?8,

X₂ + X₃?10,

X₃ + X₄?7,

X₄ + X₅?12,

X₅ + X₆?4,

X₁ , X₂ , X₃ , X₄ , X₅ , X₆ ? 0.

= >

X₁ + X₆ - X₇ = 4,

X₁ + X₂ - X₈ = 8,

X₂ + X₃ - X₉ = 10,

X₃ + X₄ - X₁₀ = 7,

X₄ + X₅ - X₁₁ = 12,

X₅ + X₆ - X₁₂ = 4,

X₁ , X₂ , X₃ , X₄ , X₅ , X₆ ? 0.

Если система ограничений содержит знак « > », то добавляется переменная со знаком «-». Если знак «<», то к левой части неравенства добавляется дополнительная переменная со знаком «+».

Дополнительные переменные вводят в целевую функцию с нулевым коэффициентом: X₇ , X₈ , X₉ , X₁₀ , X₁₁ , X₁₂.

Выражаем базисные переменные:

X₇ = -4 + X₁ + X₆,

X₈ = -8 + X₁ + X₂,

X₉ = -10 + X₂ + X₃,

X₁₀ = -7 + X₃ + X₄,

X₁₁ = -12 + X₄ + X₅,

X₁₂ = -4 + X₅ + X₆.

Для нахождения начального опорного решения строим начальную симплекс - таблицу (Таблица 2):

Таблица 2 - начальная симплекс-таблица

Начальное опорное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₁ , X₂ , X₃ , X₄ , X₅ , X₆ соответствуют отрицательные значения Дj = -1. Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член b_i = -12. Ведущая строка - X₁₁. В строке X₁₁ так же найдем максимальный по модулю отрицательный свободный член, равный -1. Столбец X₅ - ведущий. Выбираем базисную переменную, которую нужно вывести из базиса - (-1), разрешающий элемент, так как находится на пересечении ведущей строки и столбца. Соответственно Х₁₁ выводим из базиса.

Заполняем строку переменной Х₅ , для этого записываем в нее элементы строки Х₁₁ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₅ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₅ нули, кроме 1 в новой строке (Таблица 3):

Таблица 3 - Шаг 1

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₁ , X₂ , X₃ , X₄ , X₆ соответствуют отрицательные значения Дj = -1.Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-10). Ведущая строка - X₉. В строке X₉ так же найдем максимальный по модулю отрицательный свободный член (-1), разрешающий элемент, так как находится на пересечении ведущей строки и столбца, поэтому X₉ выводим из базиса. Столбец X₃ - ведущий.

Заполняем строку переменной Х₉ , для этого записываем в нее элементы строки Х₃ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₉ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₃ нули (Таблица 4):

Таблица 4 - Шаг 2

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₁ , X₆ , X₁₁ соответствуют отрицательные значения Дj = -1. Ведущая строка - X₁₂. В столбце X₆ так же найдем максимальный по модулю отрицательный свободный член (-1), разрешающий элемент, так как находится на пересечении ведущей строки и столбца, поэтому строку X₁₂ выводим из базиса. Столбец X₆ - ведущий. Заполняем строку переменной Х₆ , для этого записываем в нее элементы строки Х₁₂ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₁₂ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₆ нули. Строим новую симплекс-таблицу (Таблица 5):

Таблица 5 - Шаг 3

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₁ , X₄ , X₆ , X₁₁ соответствуют отрицательные значения Дj = -1. Ведущая строка - X₁₀ , в ней найдем максимальный по модулю отрицательный свободный член (-1), он является разрешающим элементом, так как находится на пересечении ведущей строки и столбца. Столбец X₄ - ведущий. Заполняем строку переменной Х₄ , для этого записываем в нее элементы строки Х₁₀ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₁₀ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₄ нули. Пересчитаем таблицу (Таблица 6):

Таблица 6 - Шаг 4

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₁ , X₁₀ соответствуют отрицательные значения Дj. Ведущая строка - X₈. В столбце X₂ так же найдем максимальный по модулю отрицательный свободный член (-2), разрешающий элемент, так как находится на пересечении ведущей строки и столбца, поэтому строку X₈ выводим из базиса. Столбец X₂ - ведущий. Заполняем строку переменной Х₈ , для этого записываем в нее элементы строки Х₂ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₂ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₈ нули (Таблица 7):

Таблица 7 - Шаг 5

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, векторам X₈ , X₁₀ , X₁₂ соответствуют отрицательные значения Дj. Ведущая строка - X₇. В столбце X₁₀ так же найдем максимальный по модулю отрицательный свободный член (-1), разрешающий элемент, так как находится на пересечении ведущей строки и столбца, поэтому строку X₇ выводим из базиса. Столбец X₁₀ - ведущий. Заполняем строку переменной Х₁₀ , для этого записываем в нее элементы строки Х₇ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₇ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₁₀ нули (Таблица 8):

Таблица 8 - Шаг 6

Данное решение не является оптимальным, так как в рассматриваемой задаче на минимум, вектору X₁₁ соответствует отрицательное значение Дj = -1. Ведущая строка - X₅. В столбце X₁₁ найдем максимальный по модулю отрицательный свободный член (-1), разрешающий элемент, так как находится на пересечении ведущей строки и столбца, поэтому строку X₅ выводим из базиса. Столбец X₁₁ - ведущий. Заполняем строку переменной Х₁₁ , для этого записываем в нее элементы строки Х₅ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₁₁ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₅ нули. Строим итоговую симплекс-таблицу (Таблица 9):

Таблица 9 - Итоговая симплекс-таблица

Так как Дj?0, то данное решение оптимально. В строке Z нет отрицательных элементов, следовательно, найдено оптимальное решение Z=26 при значениях переменных равных:

X₂=8, X₃=2, X₄=12, X₆=4.

Z(X) = 1*8 + 1*2 + 1*12 + 1*4 = 26

Ответ: снижение интенсивности внутригородского движения будет достигнуто, если во вторую смену добавить 8 автобусов, в третью - 2, в четвертую - 12, а в шестую - 4 автобуса. Общее количество автобусов равно 26.

5. Решение задачи в MS Excel

Для решения задачи необходимо ввести начальную информацию (Рисунок 1):

Рисунок 1 - Исходные данные

Пусть X₁ - смена 1, X₂ - смена 2, X₃ - смена 3, X₄ - смена 4, X₅ - смена 5, X₆ - смена 6.

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

X₁ + X₆?4,

X₁ + X₂?8,

X₂ + X₃?10,

X₃ + X₄?7,

X₄ + X₅?12,

X₅ + X₆?4,

X₁ , X₂ , X₃ , X₄ , X₅ , X₆ ? 0.

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

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

Вся разработанная информация сводится в развернутую математическую модель и заносится в рабочий лист MS Excel.

Столбец I, названный «Сумма произведений», предназначен для определения суммы произведений значений искомых неизвестных (ячеек I5:I10). В ячейку I5 была записана формула =A5*A4+B5*B4+C5*C4+D5*D4+E5*E4+F5*F4+0, а в ячейку H3 - =B4*B2+C4*C2+D4*D2+E4*E2+F4*F2+G4*G2+H4, эта ячейка будет являться целевой.

Из всего следует вывод, что построен опорный план и получено первое допустимое решение.

Для оптимизации имеющегося плана воспользуемся инструментом «Поиск решения», которое имеет следующий вид (Рисунок 2):

Рисунок 2 - Поиск решения

Далее необходимо сохранить найденное решение (Рисунок 3):

Рисунок 3 - Сохранение результатов

Получаем итоговую симплексную таблицу (Рисунок 4):

Рисунок 4 - Итоговая таблица

Z(X) = 1*4 + 1*4 + 1*6 + 1*6 + 1*6 = 26

Ответ: снижение интенсивности внутригородского движения будет достигнуто, если в первую и вторую смену добавить по 4 автобуса, а в третью, четвёртую и пятую по 6 автобусов. Всего необходимо добавить 26 автобусов.

Заключение

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

Решение данной задачи позволяет разработать более рациональную математическую модель для оптимизации работ маршрутного транспорта. Снижение интенсивности внутригородского движения будет достигнуто, если во вторую смену добавят 8 автобусов, в третью - 2 автобуса, в четвертую - 12, и в шестую - 4 автобуса. Всего необходимо добавить 26 автобусов.

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

1. Гмурман В. Е Теория вероятностей и математическая статистика: учеб. пособие. - 12 - е изд., перераб. - М.: Высшее образование, 2008. - 479 с.

2. Гмурман В. Е. Руководство к решению задач по теории вероятностей и математической статистике: учебное пособие. - 11-е изд., перераб. - М.: Высшее образование, 2008. - 404 с.

3. Красс М. С., Чупрынов Б. П. Математические методы и модели для магистров экономики: учебное пособие. - СПб.: Питер, 2006. - 496 с.

4. Кутузов А. Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Exсel: Учеб. Пособие. СПб.: Изд - во Политехн. ун - та, 2007. - 88 с.

5. Сборник задач по высшей математике для экономистов: учебное пособие/ Под ред. В. И. Ермакова. - М.:ИНФРА - М, 2008. - 575 с.

6. Оуэн Г. Теория игр / Г. Оуэн; Пер. с англ. И. Н. Врублевской, Г. Н. Дюбина, А. Н. Ляпунова. - 2-е изд. - М.: Вузовская книга, 2007. - 216 с.

Размещено на Allbest.ru