Автор работы: Пользователь скрыл имя, 23 Апреля 2013 в 23:07, курсовая работа
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Введение………………………………………………………….…………4
Теоретическая часть…………………………………………………………6
Понятия линейного программирования……………………………6
Общая задача линейного программирования……………..….……6
Симплекс-метод……………………………………………..………7
Алгоритм Симплекс-метода: ………………………………………8
Метод искусственного базиса: ………………………………….…8
Двойственный симплекс-метод………………………………….…9
Практическая часть………………………………………………………12
Решение задачи линейного программирования…………………12
графический метод……………………………………………………….12
метод симплекс-таблица…………………………………………………26
Решение задачи на определение планового объёма и структуры товарооборота……………………………………………………………………36
Решение двойственной задачи линейного программирования…39
составление двойственной задачи линейного программирования……39
установка сопряженных пар переменных прямой и двойственной задач……………………………………………………………………………...39
решение двойственной задачи…………………………………..….……39
Заключение………………………………………………………..………44
Использованная литература……………………………………...………45
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 3 войдет переменная x3
Строка, соответствующая переменной x3 в плане 4, получена в результате деления всех элементов строки x5 плана 3 на разрешающий элемент =0.4
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x3 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x3 и столбец x3 .
Представим расчет каждого элемента в виде таблицы:
Базис |
Свободные член |
Переменные |
Оценочные Отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
2.25 |
0 |
1 |
0 |
-0.25 |
0.75 |
0 |
0 |
0 |
|
x6 |
3.25 |
0 |
0 |
0 |
0.75 |
-0.25 |
1 |
0 |
-1 |
|
x3 |
6.5 |
0 |
0 |
1 |
-0.5 |
2.5 |
0 |
-1 |
0 |
|
x1 |
2.75 |
1 |
0 |
0 |
0.25 |
0.25 |
0 |
0 |
0 |
|
z |
2.25 |
0 |
1 |
0 |
-0.25 |
0.75 |
0 |
0 |
0 |
|
h |
3.25 |
0 |
0 |
0 |
0.75 |
-0.25 |
1 |
0 |
-1 |
|
1.Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
x2 |
2.25 |
0 |
1 |
0 |
-0.25 |
0.75 |
0 |
0 |
0 |
|
x6 |
3.25 |
0 |
0 |
0 |
0.75 |
-0.25 |
1 |
0 |
-1 |
|
x3 |
6.5 |
0 |
0 |
1 |
-0.5 |
2.5 |
0 |
-1 |
0 |
|
x1 |
2.75 |
1 |
0 |
0 |
0.25 |
0.25 |
0 |
0 |
0 |
|
z |
2.25 |
0 |
1 |
0 |
-0.25 |
0.75 |
0 |
0 |
0 |
|
h |
3.25 |
0 |
0 |
0 |
0.75 |
-0.25 |
1 |
0 |
-1 |
|
Оптимальный план можно записать так: [2.75;2,25;6.5;0;0; 3.25]
Zmax = 2·2.75 + 1·2.25 = 7.75
Для постановки задачи на минимум целевую функцию запишем так:
Z=0-(-2x1-1x2) => min
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
y1, x4, x5, y2
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,4,5,0,9,2)
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
y1 |
3 |
1 |
3 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x4 |
6 |
3 |
-1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
x5 |
5 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
y2 |
0 |
2 |
-1 |
0 |
0 |
0 |
-1 |
0 |
1 |
|
z |
0 |
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
h |
-3 |
-3 |
-2 |
1 |
0 |
0 |
1 |
0 |
0 |
|
Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода.
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке h выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
max=[3, 2,5,0]=0
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
y1 |
3 |
1 |
3 |
-1 |
0 |
0 |
0 |
1 |
0 |
3 |
x4 |
6 |
3 |
-1 |
0 |
1 |
0 |
0 |
0 |
0 |
2 |
x5 |
5 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
5 |
y2 |
0 |
2 |
-1 |
0 |
0 |
0 |
-1 |
0 |
1 |
0 |
z |
0 |
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
h |
-3 |
-3 |
-2 |
1 |
0 |
0 |
1 |
0 |
0 |
|
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной y2 в план 1 войдет переменная x1
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки y2 плана 1 на разрешающий элемент =0
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
После преобразований получаем новую таблицу:
Базис |
Свободные член |
Переменные |
Оценочные отношения | |||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
y1 |
y2 | |||
|
y1 |
3 |
0 |
3,5 |
-1 |
0 |
0 |
0,5 |
1 |
-0,5 |
|
x4 |
6 |
0 |
0,5 |
0 |
1 |
0 |
1,5 |
0 |
-1,5 |
|
x5 |
5 |
0 |
1,5 |
0 |
0 |
1 |
0,5 |
0 |
-0,5 |
|
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 |
|
Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке h выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .