Автор работы: Пользователь скрыл имя, 29 Октября 2014 в 18:21, курсовая работа
Целью данной работы является решение конкретной задачи линейного программирования. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства.
ВВЕДЕНИЕ 3
1. ПОСТАНОВКА ЗАДАЧИ 4
2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ 6
3. ВЫБОР, ОБОСНОВАНИЕ И ОПИСАНИЕ МЕТОДА РЕШЕНИЙ РАССМАТРИВАЕМОЙ ЗАДАЧИ 9
3.1. Общая задача линейного программирования 9
3.2. Выбор метода реализации модели 11
3.3. Алгоритм симплекс-метода 12
4. РЕШЕНИЕ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ 16
4.1. Решение прямой задачи линейного программирования симплексным методом 16
4.2. Составление и решение двойственной задачи 30
5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ 35
ЗАКЛЮЧЕНИЕ 43
СПИСОК БИБЛИОГРАФИЧЕСКИХ ИСТОЧНИКОВ 44
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x2 в план 3 войдет переменная x6 . Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x2 плана 2 на разрешающий элемент РЭ=0.67.
На месте разрешающего элемента в плане 3 получаем 1. В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6 .
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
466666.67 / 0.67 = 700000 |
-0.33 / 0.67 = -0.5 |
1 / 0.67 = 1.5 |
x3 |
x4 |
x5 |
x6 |
0 / 0.67 = 0 |
1 / 0.67 = 1.5 |
0 / 0.67 = 0 |
0.67 / 0.67 = 1 |
x7 |
x8 |
x9 |
x10 |
-1 / 0.67 = -1.5 |
0 / 0.67 = 0 |
0.33 / 0.67 = 0.5 |
0 / 0.67 = 0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
x8 |
500000 |
0.5 |
-0.5 |
0 |
-0.5 |
0 |
0 |
1.5 |
1 |
-0.5 |
0 |
x6 |
700000 |
-0.5 |
1.5 |
0 |
1.5 |
0 |
1 |
-1.5 |
0 |
0.5 |
0 |
x10 |
350000 |
0.25 |
-0.25 |
0 |
-0.35 |
0.2 |
0 |
0.35 |
0 |
-0.15 |
1 |
F(X3) |
14700000 |
-0.5 |
1.5 |
0 |
2.5 |
4 |
0 |
0.5 |
0 |
2.5 |
0 |
Итерация №3.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (0.5) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1400000 |
x8 |
500000 |
0.5 |
-0.5 |
0 |
-0.5 |
0 |
0 |
1.5 |
1 |
-0.5 |
0 |
1000000 |
x6 |
700000 |
-0.5 |
1.5 |
0 |
1.5 |
0 |
1 |
-1.5 |
0 |
0.5 |
0 |
- |
x10 |
350000 |
0.25 |
-0.25 |
0 |
-0.35 |
0.2 |
0 |
0.35 |
0 |
-0.15 |
1 |
1400000 |
F(X4) |
14700000 |
-0.5 |
1.5 |
0 |
2.5 |
4 |
0 |
0.5 |
0 |
2.5 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x8 в план 4 войдет переменная x1 . Строка, соответствующая переменной x1 в плане 4, получена в результате деления всех элементов строки x8 плана 3 на разрешающий элемент РЭ=0.5.
На месте разрешающего элемента в плане 4 получаем 1. В остальных клетках столбца x1 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
500000 / 0.5 = 1000000 |
0.5 / 0.5 = 1 |
-0.5 / 0.5 = -1 |
x3 |
x4 |
x5 |
x6 |
0 / 0.5 = 0 |
-0.5 / 0.5 = -1 |
0 / 0.5 = 0 |
0 / 0.5 = 0 |
x7 |
x8 |
x9 |
x10 |
1.5 / 0.5 = 3 |
1 / 0.5 = 2 |
-0.5 / 0.5 = -1 |
0 / 0.5 = 0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x3 |
400000 |
0 |
1 |
1 |
1 |
1 |
0 |
-2 |
-2 |
1 |
0 |
x1 |
1000000 |
1 |
-1 |
0 |
-1 |
0 |
0 |
3 |
2 |
-1 |
0 |
x6 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
x10 |
100000 |
0 |
0 |
0 |
-0.1 |
0.2 |
0 |
-0.4 |
-0.5 |
0.1 |
1 |
F(X4) |
15200000 |
0 |
1 |
0 |
2 |
4 |
0 |
2 |
1 |
2 |
0 |
1. Проверка критерия
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x3 |
400000 |
0 |
1 |
1 |
1 |
1 |
0 |
-2 |
-2 |
1 |
0 |
x1 |
1000000 |
1 |
-1 |
0 |
-1 |
0 |
0 |
3 |
2 |
-1 |
0 |
x6 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
x10 |
100000 |
0 |
0 |
0 |
-0.1 |
0.2 |
0 |
-0.4 |
-0.5 |
0.1 |
1 |
F(X5) |
15200000 |
0 |
1 |
0 |
2 |
4 |
0 |
2 |
1 |
2 |
0 |
Оптимальный план можно записать так:
x3 = 400000 акров земли;
x1 = 1000000 акров земли;
x6 = 1200000 акров земли.
F(X) = 8 • 400000 + 6 • 1000000 + 5 • 1200000 = 15200000
Таким образом максимальный урожай составит 15200000.
Проведем анализ оптимального плана. В оптимальный план вошла дополнительная переменная x10. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 4-го вида в количестве 100000.
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 1> 0 в столбце x2 означает, что использование x2 - не выгодно.
Значение 0 в столбце x3 означает, что использование x3 - выгодно.
Значение 2> 0 в столбце x4 означает, что использование x4 - не выгодно.
Значение 4> 0 в столбце x5 означает, что использование x5 - не выгодно.
Значение 0 в столбце x6 означает, что использование x6 - выгодно.
Значение 2 в столбце x7 означает, что теневая цена (двойственная оценка) равна 2.
Значение 1 в столбце x8 означает, что теневая цена (двойственная оценка) равна 1.
Значение 2 в столбце x9 означает, что теневая цена (двойственная оценка) равна 2.
Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений
двойственной задачи
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A:
1 |
0 |
1 |
0 |
1 |
0 |
1400000 |
0 |
1 |
0 |
1 |
0 |
1 |
1200000 |
2 |
3 |
3 |
3 |
3 |
2 |
5600000 |
0.2 |
0.2 |
0.1 |
0.1 |
0.3 |
0.3 |
700000 |
6 |
6 |
8 |
5 |
4 |
5 |
0 |