Автор работы: Пользователь скрыл имя, 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. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x7 в план 1 войдет переменная x3 . Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x7 плана 0 на разрешающий элемент РЭ=1.
На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
1400000 / 1 = 1400000 |
1 / 1 = 1 |
0 / 1 = 0 |
1 / 1 = 1 |
x4 |
x5 |
x6 |
x7 |
0 / 1 = 0 |
1 / 1 = 1 |
0 / 1 = 0 |
1 / 1 = 1 |
x8 |
x9 |
x10 |
0 / 1 = 0 |
0 / 1 = 0 |
0 / 1 = 0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
x8 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
x9 |
1400000 |
-1 |
3 |
0 |
3 |
0 |
2 |
-3 |
0 |
1 |
0 |
x10 |
560000 |
0.1 |
0.2 |
0 |
0.1 |
0.2 |
0.3 |
-0.1 |
0 |
0 |
1 |
F(X1) |
11200000 |
2 |
-6 |
0 |
-5 |
4 |
-5 |
8 |
0 |
0 |
0 |
Итерация №1.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
- |
x8 |
1200000 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1200000 |
x9 |
1400000 |
-1 |
3 |
0 |
3 |
0 |
2 |
-3 |
0 |
1 |
0 |
466666.67 |
x10 |
560000 |
0.1 |
0.2 |
0 |
0.1 |
0.2 |
0.3 |
-0.1 |
0 |
0 |
1 |
2800000 |
F(X2) |
11200000 |
2 |
-6 |
0 |
-5 |
4 |
-5 |
8 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 2 войдет переменная x2 . Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x9 плана 1 на разрешающий элемент РЭ=3.
На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
1400000 / 3 = 466666.67 |
-1 / 3 = -0.33 |
3 / 3 = 1 |
0 / 3 = 0 |
x4 |
x5 |
x6 |
x7 |
3 / 3 = 1 |
0 / 3 = 0 |
2 / 3 = 0.67 |
-3 / 3 = -1 |
x8 |
x9 |
x10 |
0 / 3 = 0 |
1 / 3 = 0.33 |
0 / 3 = 0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
x8 |
733333.33 |
0.33 |
0 |
0 |
0 |
0 |
0.33 |
1 |
1 |
-0.33 |
0 |
x2 |
466666.67 |
-0.33 |
1 |
0 |
1 |
0 |
0.67 |
-1 |
0 |
0.33 |
0 |
x10 |
466666.67 |
0.17 |
0 |
0 |
-0.1 |
0.2 |
0.17 |
0.1 |
0 |
-0.0667 |
1 |
F(X2) |
14000000 |
0 |
0 |
0 |
1 |
4 |
-1 |
2 |
0 |
2 |
0 |
Итерация №2.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai6
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (0.67) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
1400000 |
1 |
0 |
1 |
0 |
1 |
x8 |
733333.33 |
0.33 |
0 |
0 |
0 |
0 |
x2 |
466666.67 |
-0.33 |
1 |
0 |
1 |
0 |
x10 |
466666.67 |
0.17 |
0 |
0 |
-0.1 |
0.2 |
F(X3) |
14000000 |
0 |
0 |
0 |
1 |
4 |
x6 |
x7 |
x8 |
x9 |
x10 |
min |
0 |
1 |
0 |
0 |
0 |
- |
0.33 |
1 |
1 |
-0.33 |
0 |
2200000 |
0.67 |
-1 |
0 |
0.33 |
0 |
700000 |
0.17 |
0.1 |
0 |
-0.0667 |
1 |
2800000 |
-1 |
2 |
0 |
2 |
0 |
0 |