Реферат Основы симплес метода
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Введение
Целью данной курсовой работы является решение конкретной задачи линейного программирования методом симплекс-метода. Во всех таких задачах требуется найти максимум или минимум линейной функции при условии, что её переменные принимают неотрицательные значения и удовлетворяют некоторой системе линейных уравнений или линейных неравенств либо системе, содержащей как линейные уравнения, так и линейные неравенства. Каждая из этих задач является частным случаем общей задачи линейного программирования.
1.
Линейное программирование
Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование.
Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.
В самом общем виде задачу линейного программирования можно записать так:
2.
Основы симплекс-метода
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Далее рассмотрим симплексный алгоритм, не углубляясь в его обоснование.
Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).
Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем общую постановку такой задачи.
Реализация симплекс - алгоритма включает восемь шагов. Опишем их, параллельно рассматривая пример выполнения каждого шага в применении к задаче о хоккейных клюках и шахматных наборах. Условия задач указанного класса часто представляют в табличной форме (см. таблицу 1 ).
| Производственные участки | затраты времени на единицу продукции, n-час | доступный фонд времени, n-час | |
| клюшки | наборы шахмат | ||
| A | 4 | 6 | 120 |
| B | 2 | 6 | 72 |
| C | - | 1 | 10 |
| прибыль на единицу продукции, $ | 2 | 4 | |
Таблица 1
Еще раз повторим формулировку задачи из нашего примера.
Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений).
Для реализации шага в ограничения задачи вводятся дополнительные переменные. Ниже приведен порядок выполнения этой операции
Обозначим добавочные переменные несколько иначе, а именно:
В отношении добавочных переменных нужно сделать еще одно важное замечание. Все они должны иметь тот же знак, что и свободные члены системы ограничений. В противном случае используется так называемый M-метод (метод искусственного базиса).
Выполним второй шаг для нашего примера.
Шаг 3. Построение исходной симплекс-таблицы (получение первоначального допустимого базисного решения).
При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. . В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные
| Базис | Переменные | | ||||||
| | | … | | | … | | ||
| | | | … | | 1 | 0 | 0 | |
| | | | … | | 0 | … | 0 | |
| | … | … | … | … | … | … | … | … |
| | | | … | | 0 | 0 | 0 | |
| | | | .. | | 0 | | | L |
Таблица 1.1
Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений
Таблица 1.2 - Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах
| Базис | Переменные | | ||||
| | | | | | ||
| | 4 | 6 | 1 | 0 | 0 | 120 |
| | 2 | 6 | 0 | 1 | 0 | 72 |
| | 0 | 1 | 0 | 0 | 0 | 10 |
| | 2 | 4 | 0 | 0 | 0 | 0 |
Таблица 1.2
Шаг 4. Проверка условия: все
Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:
где r - номер разрешающего столбца.
Таким образом, при определении разрешающего столбца просматривается последняя строка симплексной таблицы и в ней отыскивается наибольший положительный элемент.
В нашей задаче в качестве разрешающего выберем второй столбец (соответствующий переменной
Шаг 6. Проверка условия: все
Таким образом, необходимо проверить элементы разрешающего столбца. Если среди них нет положительных, то задача неразрешима.
В нашем примере все элементы разрешающего столбца положительны (6, 6 и 1), следовательно, необходимо перейти к шагу 7.
Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:
где s - номер разрешающей строки.
Таким образом, для тех строк, где элементы разрешающего столбца положительны, необходимо найти частное от деления элемента
Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.
Для первой строки:
Для второй строки:
Для третьей строки:
Наименьший результат деления - в третьей строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную
Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. В нашем случае таковым является единица, стоящая на пересечении третьей строки и второго столбца.
Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.
Для элементов разрешающей строки используются следующие формулы:
где
Полностью результат пересчета для нашего примера можно видеть в таблице 1.3
| Базис | Переменные | | ||||
| | | | | | ||
| | 4 | 0 | 1 | 0 | -6 | 60 |
| | 2 | 0 | 0 | 1 | -6 | 12 |
| | 0 | 1 | 0 | 0 | 1 | 10 |
| | 2 | 0 | 0 | 0 | -4 | -40 |
Таблица 1.3
Таким образом, в новом базисном решении базисными переменными являются:
Доведем решение нашего примера до конца.
Вернемся к шагу 4 симплекс - алгоритма. Рассмотрим последнюю строку таблицы 1.3. В ней есть положительные элементы, значит полученное решение не является оптимальным.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец
Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и вторую строки, поскольку для третьей строки в разрешающем столбце находится нуль. Найдем частное от деления элемента
Для первой строки:
Для второй строки:
Наименьший результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную
Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 1.4).
| Базис | Переменные | | ||||
| | | | | | ||
| | 4 | 0 | 1 | 0 | -6 | 60 |
| | 2 | 0 | 0 | 1 | -6 | 12 |
| | 0 | 1 | 0 | 0 | 1 | 10 |
| | 2 | 0 | 0 | 0 | -4 | -40 |
Таблица 1.4
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 1.5.
| Базис | Переменные | | ||||
| | | | | | ||
| | 4 | 0 | 1 | -2 | 6 | 36 |
| | 1 | 0 | 0 | 1/2 | -3 | 6 |
| | 0 | 1 | 0 | 0 | 1 | 10 |
| | 2 | 0 | 0 | -1 | 2 | -52 |
Таблица 1.5
Таким образом, в очередном (третьем) базисном решении основными переменными являются: x1 = 6, x2 = 10, x3 = 36. Неосновные переменные x4 и x5 равны нулю. Значение целевой функции для этого решения равно 52.
Вернемся к шагу 4 симплекс - алгоритма. Рассмотрим последнюю строку таблицы 1.6. В ней все еще есть положительные элементы, значит полученное решение не является оптимальным, и необходимо продолжить выполнение симплекс - алгоритма.
Шаг 5. Выберем разрешающий столбец. Им окажется столбец x5, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x5 будем переводить в основные.
Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.
Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и третью строки, поскольку для второй строки в разрешающем столбце находится отрицательное число. Найдем частное от деления элемента bi на элемент, находящийся в разрешающем столбце:
Для первой строки: D1 = 60 / 4 = 15.
Для второй строки: D2 = 12 / 2 = 6.
Наименьший результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x4.
Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 1.6)
| Базис | Переменные | | ||||
| | | | | | ||
| | 0 | 0 | 1 | -2 | 6 | 36 |
| | 1 | 0 | 0 | 1/2 | -3 | 6 |
| | 0 | 1 | 0 | 0 | 1 | 10 |
| | 0 | 0 | 0 | -1 | 2 | -52 |
Таблица 1.6
Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 1.7.
| Базис | Переменные | | ||||
| | | | | | ||
| | 0 | 0 | 1/6 | -1/3 | 1 | 6 |
| | 1 | 0 | 1/2 | -1/2 | 0 | 24 |
| | 0 | 1 | -1/6 | 1/3 | 0 | 4 |
| | 0 | 0 | -1/3 | -1/3 | 0 | -64 |
Таблица 1.7
Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x1 = 24, x2 = 4, x5 = 6. Неосновные переменные x3 и x4 равны нулю. Значение целевой функции для этого решения равно 64.
Вернемся к шагу 4. Рассмотрим последнюю строку таблицы 1.7. Положительных элементов в ней не осталось, следовательно полученное решение является оптимальным. Решение задачи найдено. Оно, что естественно, совпадает с решением, полученным для этой же задачи при помощи графического метода
x1=24, x2=4
|
|
|
Рисунок 1.1
3.
Метод искусственного базиса
Для получения начального плана существует несколько алгоритмов, среди которых часто используется М-метод и метод искусственного базиса, характерной особенностью которого является то, что при решении задач линейного программирования на 1 этапе можно использовать симплекс метод.
3.1.
Алгоритм метода искусственного базиса
Для того, чтобы воспользоваться стандартной процедурой симплекс метода на 1 этапе необходимо выполнить замену. Ввести искусственную целевую функцию F′=-F.
Представление исходной системы неравенств ограничений в виде системы равенств
Ввод искусственных или вспомогательных неизвестных
В системе переменные
Формирование искусственной целевой функции, выраженной через искусственные переменные
Используем СМ для минимизации целевой функции, при этом возможны 2 пути:
* minF>0 В этом случае система уравнений, исходная система ограничений не имеет неотрицательных решений, а это значит, что и исходная задача ЛП с такой системой ограничений не имеет решений
* minF=0
Исходная система имеет по крайней мере 1 неотрицательное решение. В этом случае после нескольких итераций симплекс метода приходят к системе уравнений , в которой все переменные
3.2. Решение задачи искусственным базисом
Решим симплекс-методом задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").
Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х3 ≥ 0 и х4 ≥ 0 получим:
Система ограничений предлагает только одну допустимую базисную переменную x4, только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R1 ≥ 0 и R2 ≥ 0 Чтобы можно было применить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R1, R2 и x4. Получили, так называемую, М-задачу:
Данная система является системой с базисом, в которой R1, R2 и x4 базисные переменные, а x1, x2 и x3 свободные переменные, свободные члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:
| Базис | Переменные | Решение | |||||
| | | | | | R2 | ||
| F(x) | -4 | -16 | 0 | 0 | 0 | 0 | 0 |
| R1 | 3 | 4 | -1 | 0 | 1 | 0 | 6 |
| R2 | 1 | 3 | 0 | 0 | 0 | 1 | 3 |
| X4 | 2 | 1 | 0 | 1 | 0 | 0 | 4 |
| | -4 | -7 | 1 | 0 | -1 | -1 | - |
Таблица 1.8
В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки " Оценка " определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по f(x)-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х2, он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации симплекс-метода переменная х2 из свободной перейдет в базисную, а переменная R2 из базисной – в свободную. Запишем следующую симплекс-таблицу:
| Базис | Переменные | Решение | |||||
| | | | | | R2 | ||
| F(x) | 4/3 | 0 | 0 | 0 | 0 | 16/30 | 16 |
| R1 | 5/3 | 0 | -1 | 0 | 1 | -4/3 | 2 |
| х2 | 1/3 | 1 | 0 | 0 | 0 | 1/3 | 1 |
| X4 | 5/3 | 0 | 0 | 1 | 0 | -1/3 | 3 |
| | -5/3 | 0 | 1 | 0 | -1 | 4/3 | - |
Таблица 1.9
Разрешающий столбец х1, разрешающая строка R1, R1 выходит из базиса, x1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:
| Базис | Переменные | Решение | |||||
| | | | | | R2 | ||
| F(x) | 0 | 0 | 4/5 | 0 | -4/5 | 32/5 | 72/5 |
| х1 | 1 | 0 | -3/5 | 0 | 3/5 | -4/5 | 6/5 |
| х2 | 0 | 1 | 1/5 | 0 | -1/5 | 3/5 | 3/5 |
| х4 | 0 | 0 | 1 | 1 | -1 | 1 | 1 |
Таблица 2.0
Далее разрешающий столбец выбирается поf(x)-строке. В f(x)-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R1, который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, симплекс-методом получено оптимальное решение x1 = 6/5; x2 = 3/5; f(
4. Модифицированный симплекс – метод
Одним из модификаций симплекс-метода является улучшенный симплекс-метод.
В литературе этот метод встречается также под названием метода обратной матрицы или модифицированного симплекс-метода.
При решении задач линейного программирования, в которых n (количество переменных) существенно больше m (количество ограничений), улучшенный симплекс-метод требует по сравнению с другими значительно меньшего количества вычислительных операций и объема памяти ЭВМ.
В улучшенном симплекс-методе реализуется та же основная идея, что и в обычном симплекс-методе, но здесь на каждой итерации пересчитывается не вся матрица A-1, обратная матрице ограничений A, а лишь та часть, которая относится к текущему базису Ax.
Рассмотрим поэтапно шаги решения задачи линейного программирования улучшенным симплекс-методом:
1.В начале первого цикла нам известны обратная матрица (единичная матрица), базисное решение xb = b.
2.Образуем для каждой небазисной переменной характеристическую разность Dj, используя уравнение:
Dj = cj — = cj — pPj ,
Где p - двойственные переменные, которые можно найти следующим образом:
p = cx * ,
Где cx - вектор коэффициентов целевой функции при базисных переменных.
3.Предполагая, что используется стандартное правило выбора вводимого столбца, находим:
.
4.Если Ds ³ 0 - процедура останавливается. Текущее базисное решение является оптимальным.
5.Если Ds £ 0, вычисляем преобразованный столбец:
= Ps
6.Пусть
= (, , ..., ) .
Если все £ 0 - процедура останавливается: оптимум неограничен.
7.В противном случае находим выводимую из базиса переменную:
= q .
8.Строим увеличенную матрицу:
-1;\s\do(x:;:;:
и трансформируем ее с ведущим элементом . Первые m столбцов результат дают матрицу, обратную новому базису. Преобразуем базисное решение:
xb i Ü xb i — q * , i ¹ r,
xb r Ü q
и переходим к этапу 2.
Этот вариант называют также модифицированным симплекс-методом, поскольку он уменьшает объем вычислений на каждом шаге. Идея заключается в том, что на каждом шаге конаническую форму задачи для текущего базиса можно получить независимо от других таких форм непосредственно из исходной записи стандартной задачи ЛП. Для этого нужно: (1) сохранять исходную запись задачи на протяжении всей работы метода, это та цена, которую приходится платить за больше быстродействие;
(2) использовать так называемые симплекс – множители π – коэффициенты для непосредственного перехода от исходной записи задачи к ее текущей канонической форме базиса; и (3) использовать обращенный базис В־¹ - матрицу размера m x m, позволяющую вычислять на каждом шаге ведущий столбец a΄s и обновлять симплекс – множители π.
Преимущества метода
Улучшенный симплекс-метод, обладает значительными преимуществами по сравнению со стандартной формой. Это относится к точности, скорости и требованиям к памяти. Большая часть этих преимуществ определяется тем фактором, что, как правило, матрицы больших линейных задач (то есть с n>m>100) являются слабозаполненными, содержат малый процент ненулевых элементов.
Обычной является плотность 5% или менее. Улучшенная форма симплекс-метода в большей степени способна использовать преимущества, вытекающие из этого факта. В этой форме характеристические разности и ведущий вектор вычисляются непосредственно по исходным данным. Поскольку исходная матрица слабозаполнена, а перемножение следует производить только тогда, когда оба сомножителя отличны от нуля, то время вычислений значительно сокращается.
В дополнение к этому использование только исходных данных приводит к тому, что уменьшается возможность накопления ошибок округления. Наоборот, стандартные симплексные таблицы, даже если они первоначально являются слабозаполненными, в ходе итеративного процесса быстро заполняются ненулевыми элементами. Таким образом, время вычислений увеличивается, и, поскольку каждая таблица вычисляется из предшествующей, накопление ошибок может начать играть более серьезную роль
5.1. Решение задачи модифицированным симплекс – методом
Исходные данные:
F(
Введем выравнивающие и искусственные переменные:
Шаг 1
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Y1 | Y2 | Оценка |
| Y1 | 4 | 1 | 1 | -1 | 0 | 0 | 0 | 1 | 0 | 4 |
| Y2 | 6 | 1 | 2 | 0 | -1 | 0 | 0 | 0 | 1 | 3 |
| X5 | 12 | -1 | 2 | 0 | 0 | 1 | 0 | 0 | 0 | 6 |
| X6 | 12 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 12 |
| F(x) | 0 | -1 | -4 | 0 | 0 | 0 | 1 | 0 | 0 | max |
| Cj | -10 | -2 | -3 | -1 | 1 | 0 | 0 | -1 | -1 | max |
Таблица 2.1
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Y1 | Y2 |
| Y1 | 1 | 0,5 | 0 | -1 | 0,5 | 0 | 0 | 1 | -0,5 |
| Y2 | 3 | 0,5 | 1 | 0 | -0,5 | 0 | 0 | 0 | 0,5 |
| X5 | 6 | -12 | 0 | 0 | 1 | 1 | 0 | 0 | -1 |
| X6 | 9 | 0,5 | 0 | 0 | 0,5 | 0 | 1 | 0 | -0,5 |
| F(x) | 12 | 1 | 0 | 0 | -2 | 0 | 0 | 0 | 2 |
| Cj | -1 | 0,5 | 0 | 1 | 0,5 | 0 | 0 | -1 | 0,5 |
Таблица 2.2
Шаг 2
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Y1 | Y2 | Оценка |
| Y1 | 1 | 0,5 | 0 | -1 | 0,5 | 0 | 0 | 1 | -0,5 | 2 |
| X2 | 3 | 0,5 | 1 | 0 | -0,5 | 0 | 0 | 0 | 0,5 | 6 |
| X5 | 6 | -12 | 0 | 0 | 1 | 1 | 0 | 0 | -1 | ∞ |
| X6 | 9 | 0,5 | 0 | 0 | 0,5 | 0 | 1 | 0 | -0,5 | 18 |
| F(x) | 12 | 1 | 0 | 0 | -2 | 0 | 0 | 0 | 2 | Max |
| Cj | -1 | 0,5 | 0 | 1 | 0,5 | 0 | 0 | -1 | 0,5 | Max |
Таблица 2.3
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Y1 | Y2 |
| X1 | 2 | 1 | 0 | -2 | 1 | 0 | 0 | 2 | -1 |
| X2 | 2 | 0 | 1 | 1 | -1 | 0 | 0 | -1 | 1 |
| X5 | 10 | 0 | 0 | -4 | 3 | 1 | 0 | 4 | -3 |
| X6 | 8 | 0 | 0 | 1 | 0 | 0 | 1 | -1 | 0 |
| F(x) | 10 | 0 | 0 | 2 | -3 | 0 | 0 | -2 | 3 |
| Cj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Таблица 2.4
F(
Шаг 3
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Оценка |
| X1 | 2 | 1 | 0 | -2 | 1 | 0 | 0 | 2 |
| X2 | 2 | 0 | 1 | 1 | -1 | 0 | 0 | ∞ |
| X5 | 10 | 0 | 0 | -4 | 3 | 1 | 0 | 3,3 |
| X6 | 8 | 0 | 0 | 1 | 0 | 0 | 1 | ∞ |
| F(x) | 10 | 0 | 0 | 2 | -3 | 0 | 0 | max |
Таблица 2.5
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 |
| X1 | 2 | 1 | 0 | -2 | 1 | 0 | 0 |
| X2 | 4 | 1 | 1 | -1 | 0 | 0 | 0 |
| X5 | 4 | -3 | 0 | 2 | 0 | 1 | 0 |
| X6 | 8 | 0 | 0 | 1 | 0 | 0 | 1 |
| F(x) | 16 | 3 | 0 | -4 | 0 | 0 | 0 |
Таблица 2.6
F(x)=16 X=(0; 4; 0; 2; 4; 8)
Шаг 4
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Оценка |
| X4 | 2 | 1 | 0 | -2 | 1 | 0 | 0 | ∞ |
| X2 | 4 | 1 | 1 | -1 | 0 | 0 | 0 | ∞ |
| X5 | 4 | -3 | 0 | 2 | 0 | 1 | 0 | 2 |
| X6 | 8 | 0 | 0 | 1 | 0 | 0 | 1 | 8 |
| F(x) | 16 | 3 | 0 | -4 | 0 | 0 | 0 | max |
Таблица 2.7
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 |
| X4 | 6 | -2 | 0 | 0 | 1 | 1 | 0 |
| X2 | 6 | -0.5 | 1 | 0 | 0 | 0.5 | 0 |
| X3 | 2 | -1.5 | 0 | 1 | 0 | 0.5 | 0 |
| X6 | 6 | 1.5 | 0 | 0 | 0 | -0.5 | 1 |
| F(x) | 24 | -3 | 0 | 0 | 0 | 2 | 0 |
Таблица 2.8
F(
Шаг 5
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 | Оценка |
| X4 | 6 | -2 | 0 | 0 | 1 | 1 | 0 | ∞ |
| X2 | 6 | -0.5 | 1 | 0 | 0 | 0.5 | 0 | ∞ |
| X3 | 2 | -1.5 | 0 | 1 | 0 | 0.5 | 0 | ∞ |
| X6 | 6 | 1.5 | 0 | 0 | 0 | -0.5 | 1 | 4 |
| F(x) | 24 | -3 | 0 | 0 | 0 | 2 | 0 | max |
Таблица 2.9
| Базис | Св.члены | X1 | X2 | X3 | X4 | X5 | X6 |
| X4 | 14 | 0 | 0 | 0 | 1 | 0.3 | 1.3 |
| X2 | 8 | 0 | 1 | 0 | 0 | 0.3 | 0.3 |
| X3 | 8 | 0 | 0 | 1 | 0 | 0 | 1 |
| X1 | 4 | 1 | 0 | 0 | 0 | -0.3 | 0.7 |
| F(x) | 36 | 0 | 0 | 0 | 0 | 1 | 2 |
Таблица 3.0
Оптимальное решение найдено - F(
Заключение.
В курсовой работе проделана работа по изучению следующих вопросов:
· Рассмотрен и дан алгоритм симплекс метода.
· Разработана программа для решения разного рода задач, ее можно применить в различных отраслях, а также были сооставлены текстовые примеры, показывающие простоту и экономичность работы.
· Инструкции пользователю не нужны, так как данная программа проста и практически не требует времени на освоение.
Данная программа имеет простой интерфейс, не требует дополнительных ресурсов в виде свободного места на диске. Все вычисления производятся только в оперативной памяти. Тесты, не выявили ни каких отклонений в ходе решения программой поставленных задач.
Программа не рассчитана на неправильный ввод формата вводимых данных.
Список литературы
1. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007— ISBN 0-13-032374-8
2. Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986— ISBN 5-06-002663-9
3. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006— ISBN 5-8459-0857-4
