Решение задач линейного программирования 3

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

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

«БРЕСТСКИЙ ГОСУДАОСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра информатики и прикладной математики

КУРСОВАЯ РАБОТА

на тему

«РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ»

по дисциплине «Системный анализ и исследование операций»

Выполнил студент

Допущен к защите

Результаты защиты

БРЕСТ 2009

СОДЕРЖАНИЕ

Введение………………………………………………………………………………

Постановка задачи оптимизации……………………………………….

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ………………………………...

Обоснование выбора метода решения задачи……………………

Решение задачи оптимизации…………………………………………….

АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ И УСТОЙЧИВОСТЬ………

Предварительный анализ оптимального решения………………...

Исследование чувствительности целевой функции………………..

Исследование устойчивости оптимального базисного плана……..

ПОИСК ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ………………..

ЗАКЛЮЧЕНИЕ………………………………………………………………………….

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ…………………………………….

Введение

Исследование операций изучает хорошо структурированные задачи. Хорошо структурированная задача – задача, для которой существует математическая модель с одним критерием качества. Математическая модель – отражение интересующих нас свойств объектов или явлений с помощью математических символов.

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

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

Математическая модель – отображение оригинала в виде математических объектов, переменных, функций, уравнений и неравенств.

В простейшем случае математическая модель содержит три объекта:

совокупность неизвестных величин xi, i=1..n, значения которых необходимо найти. В совокупности эти значения образуют множество решений.

множество допустимых решений которые могут принимать xi, i=1..n. В хорошо формализованных задачах это множество может быть описано с помощью системы неравенств gj(x1,x2 , .. , xm)<=0, j=1..m.

оценка качества допустимого решения. В простейшем случае оценка качества осуществляется с помощью специальной функции f(x1,x2,…,xn), которую называют целевой функцией.

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

f(x1,x2,…,xn) extr(max,min)

gi(x1,x2,…,xn)<= 0, i=1..n, гдеg – ограничение целевой функции.

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

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

Имеется множество допустимых решений X.Имеется совокупность критериев K{K1, K2,..., Kn} с помощью которых производится оценка качества решений X. Требуется найти такое решение xX, которое является наилучшим с точки зрения критериев K1, K2,..., Kn. Такая задача и будет называться задачей исследования операций.

Исследование операций

Теория очередей

Детерминированные задачи — задачи, которые не содержат в себе элементов случайности.

Задачи дискретного программирования отличаются от задач математического программирования тем, что в задачах дискретного программирования на значения переменных xi накладывается требование дискретности, т.е. xi может принимать не любые значения из диапазона (a, b), а из множества конкретных фиксированных значений а1, а2, ..., аk. Простейшим примером является требование целочисленности.

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

Стохастические задачи — задачи, которые содержат в своей постановке вероятностные элементы.

До недавнего времени теория очередей сводилась всего к трем законам:

1). Соседняя очередь всегда движется быстрее
2). Как только вы переходите в соседнюю очередь, ваша прежняя начинает двигаться быстрее.

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

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

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

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

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

Пусть

-количество дней работы судов 1 типа на 1 линии

-количество дней работы судов 2 типа на 1 линии

-количество дней работы судов 3 типа на 1 линии

-количество дней работы судов 1 типа на 2 линии

-количество дней работы судов 2 типа на 2 линии

-количество дней работы судов 3 типа на 2 линии

-количество дней работы судов 1 типа на 3 линии

-количество дней работы судов 2 типа на 3 линии

-количество дней работы судов 3 типа на 3 линии

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

(2.1)

Так же у каждого из судов есть производительность. Она отличается в зависимости от типов судов и от линий. Так же есть заданный объём перевозок(таблица 1). Запишем следующие ограничения:

(2.2)

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

Исходя из этих данных запишем целевую функцию:

L(x)= (2.3)

Математическая модель задачи будет выглядеть следующим образом

(2.4)

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

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

Достаточное условие оптимальности: если в задаче на максимум коэффициенты целевой функции отрицательны, то соответствующий базисный план оптимален.

В задаче на минимум достаточное условие — неотрицательные коэффициенты целевой функции.

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

Для решения задач симплекс-методом необходимо:

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

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

Вспомнить одну или более итераций симплекс-метода, которые включают:

проверку достаточных условий оптимальности и выбор ведущей переменной

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

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

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

(3.1)

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

i1, i2, …, im — индексы базисных переменных.

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

(3.2)

Jб = {i1, i2, …, im} — базисные переменные

Jн = {j1, j2, …, jm} — небазисные переменные

Jб Jн = J = {1, 2, …, n}

Используя уравнение системы (3.2) мы можем исключить базисные переменные из целевой функции:

(3.3)

xj 0, j = J(3.4) — известные ограничения.

Задачу линейного программирования с целевой функцией (3.3) и ограничениями (3.2) и (3.4) будем называть задачей линейного программирования в симплексной форме, если все свободные члены bi 0, .

(3.5)

Такой задаче ставим в соответствие базисный план, который состоит из:

Введем дополнительное обозначение:

Задачу (5) можно переписать в следующем виде:

(3.6)

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

1 этап: проверяем достаточное условие оптимальности (таблица) базисного плана.

Если в задаче на максимум коэффициенты целевой функции удовлетворяет условию:

в задаче на минимум:

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

Допустим, что достаточное условие оптимальности не выполняется. В этом случае найдем максимальный по модулю, не удовлетворяющий условию оптимальности, коэффициент целевой функции. Соответствующую переменную назовем ведущей. Этот индекс обозначен через j*. Соответствующий столбец симплексной таблицы назовем ведущим.

2 этап: вычисление оптимально допустимого шага.

Из системы основных ограничений симплексной формы следует:

Из вытекает, что

(3.7)

Очевидно, что соотношение (7) может нарушаться только в том случае, если , поэтому для каждой базисной переменной :

, то соответствующая базисная переменная ни при каком значении не обращается в ноль.

Максимально допустимый шаг определим как минимум из чисел .

возможны 2 случая:

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

(конечное число)

называется ведущей или разрешающей переменной.

3 этап: преобразование симплексной таблицы.

Как уже отмечалось в пункте 1, должна выводиться из базиса, на ее место вводится переменная — небазисная.

Нарисуем новую симплексную таблицу.

(3.8)

(3.9)

(3.10)

(3.11)

Правила:

На место ведущего элемента в новой таблице записывается элемент, обратный ведущему.

,

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

i — номер произвольной строки.

Элементы ведущего столбца получаются из старых элементов делением последних на ведущий элемент.

4)

,

,

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

Двухфазный симплекс-метод.

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

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

Начальный базис вспомогательной задачи составляют переменные:

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

2. в ограничениях, которые не находятся в предпочтительном виде,- фиктивные переменные

Целевую функцию вспомогательной задачи выражаем через небазисные переменные и решаем систему обычным симплекс-методом(описан выше).

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

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

4. Решение задачи оптимизации

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

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

Введём фиктивные переменные х16, х17, х18 и решим задачу относительно их:

Будем решать задачу табличным симплекс-методом, как описывалось ранее.

Этой симплексной таблице соответствует начальный базисный план х(0) = (0,0,0,0,0,0,0,0,0,0,0,0,300,300,300,3000,5400,3300). L (x(0)) = 11700. Этот план не оптимален, так как целевая функция вспомогательной задачи на минимум содержит отрицательные коэффициенты.

Выбираем базисный столбец и разрешающую строку:

Пересчёт симплексной таблицы происходит по правилам, описанным в разделе 3.

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

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

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

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

Произведём пересчёт симплексной таблицы

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

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

Произведём пересчёт симплексной таблицы:

Поскольку строка L таблицы не содержит положительных элементов, то базисный план х(1) = (0,0,257.693,300,46.154,42.308,0,253.846,0,92.308,0,0,0,0,0). L (x(2)) = 11792.308 является оптимальным. Решение задачи окончено.

Значения основных переменных задачи х1 , х2 ,х3 , х4, х5, х6, х7, х8, х9, обозначают, что:

-суда 1 типа должны работать только на 2 линии

-суда 2 типа должны работать 46.15385 дней на 2 линии и 253.84615 дней на 3 линии

-суда 3 типа должны работать 257.69231 дней на 1 линии и 42.30769 дней на второй линии

При этом максимальная загрузка суден составит 11792.308 млн. тонно-миль.

5.АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ И УСТОЙЧИВОСТЬ

5.1. Предварительный анализ оптимального решения

Первые три ограничения являются количественными, т.к. исходят из обязательного заданного объёма перевозок.

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

5.2. Исследование чувствительности целевой функции

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

(5.1)

и исследовать его компоненты. Согласно полученному решению базисными переменными являются х3, х4, х5 ,х6,х8,х10.

Вычислим обратную матрицу:

Найдём оптимальный двойственный план:

Дадим экономическую оценку полученным результатам:

1) Увеличение заданного объёма перевозок на 1 линии к увеличению суммарной максимальной загрузки судов не приведёт

2) Увеличение заданного объёма перевозок на 2 линии к увеличению суммарной максимальной загрузки судов не приведёт

3) Увеличение заданного объёма перевозок на 3 линии на 1 единицу приведёт к увеличению суммарной максимальной загрузки судов на 1

4) Увеличение общего времени эксплуатации судов на 1 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 14 млн.тнно-миль.

5) Увеличение общего времени эксплуатации судов на 2 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 15 млн.тнно-миль.

6) Увеличение общего времени эксплуатации судов на 3 линии на 1 сутки приведёт к увеличению максимальной загрузки судов на 12 млн.тнно-миль.

5.3. Исследование устойчивости оптимального базисного плана

Определим интервал устойчивости

, (5.2)

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

Найдём интервал устойчивости для первого ограничения:

Таким образом, интервал устойчивости для b1 составляет:

Найдём интервал устойчивости для второго ограничения:

Таким образом, интервал устойчивости для b2 составляет:

Найдём интервал устойчивости для третьего ограничения:

Таким образом, интервал устойчивости для b3 составляет:

Найдём интервал устойчивости для четвёртого ограничения:

Таким образом, интервал устойчивости для b4 составляет:

Найдём интервал устойчивости для пятого ограничения:

Таким образом, интервал устойчивости для b5 составляет:

Найдём интервал устойчивости для шестого ограничения:

Таким образом, интервал устойчивости для b6 составляет:

6.ПОИСК ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ

Для поиска оптимального целочисленного решения воспользуемся методом ветвей и границ. Для этого нецелочисленную компоненту оптимального решения x3=257.692. Исходя из этого решаем 2 задачи:

x3≤[257.692]=257

x3≥[257.692]+1=258

Решив симплекс-методом задачи с дополнительными ограничениями (1) и (2), получим одно решения:

L(x2*)=11792.308

При ограничении x3≥258 решения не существует.

x2* не является целочисленным поэтому процесс решения продолжается дальше. Это решение содержит одну нецелочисленную компоненту х5.

Исходя из этого решаем 2 задачи:

1) x4≤[ 46.154]=46

x4≥[46.154]+1=47

Решив симплекс-методом задачи с дополнительными ограничениями (1) и (2), получим 2 решения:

L(x3*)=11792

L(x4*)= 11791

Найдено оптимальное целочисленное решение – это решение задачи 3.

Поиск решения можно изобразить графически:

рисунок

Значения основных переменных задачи х1 , х2 ,х3 , х4, х5, х6, х7, х8, х9, обозначают, что:

-суда 1 типа должны работать 299 дней на 2 линии и 1 день на 3 линии

-суда 2 типа должны работать 47 дней на 2 линии и 253 дня на 3 линии

-суда 3 типа должны работать 250 дней на 1 линии и 50 дней на второй линии

При этом максимальная загрузка суден составит 11792 млн. тонно-миль

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

Ракецкий В.М. Методические указания и задания к курсовой работе “Решение задач линейного программирования” по дисциплине “Системный анализ и исследование операций”

Брест: БГТУ 2007

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

Альсевич В.В., Габасов Р., Глушенков В.С. Оптимизация линейных экономических моделей: Статистические задачи. – Мн.: БГУ, 2000. -210с.

Балашевич В.А. Основы математического программирования. – Мн.: Вышэйшая школа, 1985.-173с.

Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989. – 176 с.