Автор работы: Пользователь скрыл имя, 31 Октября 2013 в 08:53, курсовая работа
Цель данной курсовой работы: изучить и научиться применять на практике симплекс - метод для решения задач линейного программирования в случаи произвольных свободных членов. Задачи курсовой работы:
изучить теоретический материал;
на примерах рассмотреть симплекс метод.
Введение 3
1 Симплекс-метод 5
1.1 Общая характеристика симплекс-метода 5
1.2 Общая идея симплексного метода 12
1.3 Симплекс-метод решения задачи линейного программирования 14
2 Решение задачи при помощи симплекс – метода 20
2.1 Постановка задачи 20
2.2 Решение поставленной задачи 21
2.3 Решение задачи при помощи табличного процессора Microsoft Excel 25
Список используемых источников 32
Приложение А – Решение элементов 33
Приложение Б – Решение элементов 34
Матрица коэффициентов A = a(ij) этой системы уравнений представлена в таблице 2.2.
Таблица 2.2 - Матрица коэффициентов
0,38 |
0,001 |
0,002 |
1 |
0 |
0 |
0 |
0,38 |
0,001 |
0,002 |
0 |
-1 |
0 |
1 |
0 |
0,09 |
0,5 |
0 |
0 |
-1 |
0 |
0 |
0,02 |
0,08 |
0 |
0 |
0 |
-1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7.
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0.05,0.008,0.22)
Базисное решение называется допустимым, если оно неотрицательно пример представлен на таблице 2.3.
Таблица 2.3 - Базисное решение
Базис |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
X4 |
0,008 |
0,38 |
0,001 |
0,002 |
1 |
0 |
0 |
0 |
X5 |
0,012 |
0,38 |
0,001 |
0,002 |
0 |
-1 |
0 |
0 |
X6 |
0,22 |
0 |
0,09 |
0,5 |
0 |
0 |
-1 |
0 |
X7 |
0,05 |
0 |
0,02 |
0,08 |
0 |
0 |
0 |
-1 |
F(X0) |
0,228 |
0,34 |
-0,06 |
0,1 |
-1 |
-1 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее: min =0,44. Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен (0,5) и находится на пересечении ведущего столбца и ведущей строки, пример в таблице 2.4.
Таблица 2.4 – Итерация ноль
Базис |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
X4 |
0,008 |
0,38 |
0,001 |
0,002 |
1 |
0 |
0 |
1 |
X5 |
0,012 |
0,38 |
0,001 |
0,002 |
0 |
1 |
0 |
1 |
X6 |
0,22 |
0 |
0,09 |
0,5 |
0 |
0 |
1 |
0 |
X7 |
0,05 |
0 |
0,02 |
0,08 |
0 |
0 |
0 |
1 |
F(X1) |
0,228 |
0,34 |
-0,06 |
0,1 |
-1 |
-1 |
0 |
0 |
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент 0,5.
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент «РЭ».
НЭ = (СЭ* РЭ - А*В)/РЭ |
(1.25) |
СЭ - элемент старого плана, РЭ - разрешающий элемент (0,5), А и В - элементы старого плана, образующие прямоугольник с элементами СЭ и РЭ.
Представим расчет каждого элемента представлен в приложении А.
После преобразований получаем новую таблицу 2.5.
Таблица 2.5 – Расчет элементов
Базис |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x4 |
0 |
0,38 |
0 |
0 |
1 |
0 |
0,004 |
0 |
x5 |
0 |
0,38 |
0,001 |
0,002 |
-1 |
0 |
0 |
1 |
x3 |
0,44 |
0 |
0,18 |
1 |
0 |
0 |
-2 |
0 |
x7 |
0,015 |
0 |
0,01 |
0 |
0 |
0 |
0,16 |
-1 |
F(X) |
0,184 |
0,3 |
-0,078 |
0 |
-1 |
-1 |
0 |
0 |
Итерация №1.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее: min =0,02. Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (0,38) и находится на пересечении ведущего столбца и ведущей строки, пример в таблице 2.6.
Таблица 2.6 – Первая итерация
Базис |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x4 |
0 |
0,38 |
0 |
0 |
1 |
0 |
0,004 |
0 |
x5 |
0 |
0,38 |
0,001 |
0,002 |
-1 |
0 |
0 |
1 |
x3 |
0,44 |
0 |
0,18 |
1 |
0 |
0 |
-2 |
0 |
x7 |
0,015 |
0 |
0,01 |
0 |
0 |
0 |
0,16 |
-1 |
F(X) |
0,184 |
0,3 |
-0,078 |
0 |
-1 |
-1 |
0 |
0 |
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 2 войдет переменная x1
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=0,38
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Расчет каждого элемента представлен в приложении В.
После преобразований получаем новую таблицу 2.7.
Таблица 2.7 – Расчет элементов
Базис |
План |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x1 |
0 |
1 |
0,0017 |
0 |
2,63 |
0,00 |
0,01053 |
0,00 |
x5 |
0 |
0 |
0,00036 |
0,002 |
-2 |
0 |
-0,004 |
1 |
x3 |
0,44 |
0 |
0,18 |
1 |
0 |
0 |
-2 |
0 |
x7 |
0,01 |
0 |
0,0056 |
0 |
0 |
0 |
0,16 |
-1 |
F(X) |
0,18 |
0 |
-0,08 |
0 |
-1,89 |
-1,0 |
0 |
0 |
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.