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

 
 
 

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

     Значения  основных переменных задачи х₁ , х₂  ,х₃ , х₄, х_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)

     и исследовать его компоненты. Согласно полученному решению базисными  переменными являются х₃, х₄, х₅ ,х₆,х₈,х₁₀. 

                       

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

       
 
 

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

       

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

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 задачи:

1. x3≤[257.692]=257
2. x3≥[257.692]+1=258

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

       L(x^2*)=11792.308 

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

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

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

1) x4≤[ 46.154]=46

2. x4≥[46.154]+1=47

 

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

       L(x^3*)=11792 

       L(x^4*)= 11791 
 
 

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

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

     рисунок 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Значения  основных переменных задачи х₁ , х₂  ,х₃ , х₄, х_5, х_6, х_7, х_8, х_9, обозначают, что:

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

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

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

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

     ЗАКЛЮЧЕНИЕ 

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

 

     

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

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

Брест: БГТУ 2007

2. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.-319с.
3. Альсевич В.В., Габасов Р., Глушенков В.С. Оптимизация линейных экономических моделей: Статистические задачи. – Мн.: БГУ, 2000. -210с.
4. Балашевич В.А. Основы математического программирования. – Мн.: Вышэйшая школа, 1985.-173с.
5. Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989. – 176 с.