Автор работы: Пользователь скрыл имя, 23 Апреля 2013 в 23:07, курсовая работа
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Введение………………………………………………………….…………4
Теоретическая часть…………………………………………………………6
Понятия линейного программирования……………………………6
Общая задача линейного программирования……………..….……6
Симплекс-метод……………………………………………..………7
Алгоритм Симплекс-метода: ………………………………………8
Метод искусственного базиса: ………………………………….…8
Двойственный симплекс-метод………………………………….…9
Практическая часть………………………………………………………12
Решение задачи линейного программирования…………………12
графический метод……………………………………………………….12
метод симплекс-таблица…………………………………………………26
Решение задачи на определение планового объёма и структуры товарооборота……………………………………………………………………36
Решение двойственной задачи линейного программирования…39
составление двойственной задачи линейного программирования……39
установка сопряженных пар переменных прямой и двойственной задач……………………………………………………………………………...39
решение двойственной задачи…………………………………..….……39
Заключение………………………………………………………..………44
Использованная литература……………………………………...………45
Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке h выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
max=[0.86, 12,3.33, ∞]=0.86
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (3.5) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
y1 |
3 |
0 |
3,5 |
-1 |
0 |
0 |
0,5 |
1 |
-0,5 |
0,86 |
x4 |
6 |
0 |
0,5 |
0 |
1 |
0 |
1,5 |
0 |
-1,5 |
12 |
x5 |
5 |
0 |
1,5 |
0 |
0 |
1 |
0,5 |
0 |
-0,5 |
3,33 |
x1 |
0 |
1 |
-0,5 |
0 |
0 |
0 |
-0,5 |
0 |
0,5 |
∞ |
z |
0 |
0 |
-2 |
0 |
0 |
0 |
-1 |
0 |
1 |
|
h |
-3 |
0 |
-3,5 |
1 |
0 |
0 |
-0,5 |
0 |
1,5 |
|
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 2 войдет переменная x2
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент =3.5
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Представим расчет каждого элемента в виде таблицы:
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
0,86 |
0 |
1 |
-0,3 |
0 |
0 |
0,14 |
0,29 |
-0,14 |
|
x4 |
5,57 |
0 |
0 |
0,14 |
1 |
0 |
1,43 |
-0,14 |
-1,43 |
|
x5 |
3,71 |
0 |
0 |
0,43 |
0 |
1 |
0,29 |
-0,43 |
-0,29 |
|
x1 |
0,43 |
1 |
0 |
-0,1 |
0 |
0 |
-0,4 |
0,14 |
0,43 |
|
z |
1,71 |
0 |
0 |
-0,6 |
0 |
0 |
-0,7 |
0,57 |
0,71 |
|
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
Итерация №3.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке Z выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai7
и из них выберем наименьшее:
max=[∞,∞,6,3, ∞]=3
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
0,86 |
0 |
1 |
-0,3 |
0 |
0 |
0,14 |
0,29 |
-0,14 |
6 |
x6 |
5,57 |
0 |
0 |
0,14 |
1 |
0 |
1,43 |
-0,14 |
-1,43 |
3,9 |
x5 |
3,71 |
0 |
0 |
0,43 |
0 |
1 |
0,29 |
-0,43 |
-0,29 |
13 |
x1 |
0,43 |
1 |
0 |
-0,1 |
0 |
0 |
-0,4 |
0,14 |
0,43 |
∞ |
z |
1,71 |
0 |
0 |
-0,6 |
0 |
0 |
-0,7 |
0,57 |
0,71 |
|
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x6
Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x4 плана 2 на разрешающий элемент РЭ=1.43
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6 .
Представим расчет каждого элемента в виде таблицы:
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
0,31 |
0 |
1 |
-0,3 |
-0,1 |
0 |
0 |
0,3 |
-0 |
∞ |
x6 |
3,90 |
0 |
0 |
0,1 |
0,70 |
0 |
1 |
-0,1 |
-1 |
39 |
x5 |
2,58 |
0 |
0 |
0,4 |
-0,2 |
1 |
0 |
-0,4 |
0 |
6,47 |
x1 |
1,99 |
1 |
0 |
-0,1 |
0,28 |
0 |
-0 |
0,10 |
0,03 |
∞ |
z |
4,44 |
0 |
0 |
-0,5 |
0,49 |
0 |
-0 |
0,50 |
0,01 |
|
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
Итерация №4.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке Z выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
max=[∞,39,6.47, ∞]=6.47
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (0.4) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
0,31 |
0 |
1 |
-0,3 |
-0,1 |
0 |
0 |
0,3 |
-0 |
∞ |
x6 |
3,90 |
0 |
0 |
0,1 |
0,70 |
0 |
1 |
-0,1 |
-1 |
39 |
x5 |
2,58 |
0 |
0 |
0,4 |
-0,2 |
1 |
0 |
-0,4 |
0 |
6,47 |
x1 |
1,99 |
1 |
0 |
-0,1 |
0,28 |
0 |
-0 |
0,10 |
0,03 |
∞ |
z |
4,44 |
0 |
0 |
-0,5 |
0,49 |
0 |
-0 |
0,50 |
0,01 |
|
h |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|