Симплекс-метод
Решение задачи линейного программирования симплексным методом, с использованием симплексной таблицы. Переход системы неравенств к канонической форме. Выполнение преобразования симплексной таблицы методом Жордано-Гаусса. Основной алгоритм симплекс-метода.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 10.11.2013 |
| Размер файла | 16,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Симплекс-метод
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = 225x1 + 100x2 + 192x3 при следующих условиях-ограничений.
15x1 + 5x2 + 4x3?6
4x1 + 3x2 + 8x3?8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
15x1 + 5x2 + 4x3-1x4 + 0x5 = 6
4x1 + 3x2 + 8x3 + 0x4-1x5 = 8
Умножим все строки на (-1) и будем искать первоначальный опорный план. линейное программирование симплекс неравенство
-15x1-5x2-4x3 + 1x4 + 0x5 = -6
-4x1-3x2-8x3 + 0x4 + 1x5 = -8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:
x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,-6,-8)
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x4 |
-6 |
-15 |
-5 |
-4 |
1 |
0 |
|
|
x5 |
-8 |
-4 |
-3 |
-8 |
0 |
1 |
|
|
F(X0) |
0 |
225 |
100 |
192 |
0 |
0 |
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-8).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x4 |
-6 |
-15 |
-5 |
-4 |
1 |
0 |
|
|
x5 |
-8 |
-4 |
-3 |
-8 |
0 |
1 |
|
|
F(X0) |
0 |
225 |
100 |
192 |
0 |
0 |
|
|
и |
0 |
225 : (-4) = -561/4 |
100 : (-3) = -331/3 |
192 : (-8) = -24 |
- |
- |
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x4 |
-2 |
-13 |
-31/2 |
0 |
1 |
-1/2 |
|
|
x3 |
1 |
1/2 |
3/8 |
1 |
0 |
-1/8 |
|
|
F(X0) |
-192 |
129 |
28 |
0 |
0 |
24 |
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1/2).
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x4 |
-2 |
-13 |
-31/2 |
0 |
1 |
-1/2 |
|
|
x3 |
1 |
1/2 |
3/8 |
1 |
0 |
-1/8 |
|
|
F(X0) |
-192 |
129 |
28 |
0 |
0 |
24 |
|
|
и |
0 |
129 : (-13) = -912/13 |
28 : (-31/2) = -8 |
- |
- |
24 : (-1/2) = -48 |
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x5 |
4 |
26 |
7 |
0 |
-2 |
1 |
|
|
x3 |
11/2 |
33/4 |
12/8 |
1 |
-1/4 |
0 |
|
|
F(X1) |
-288 |
-495 |
-140 |
0 |
48 |
0 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (26) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
|
|
x5 |
4 |
26 |
7 |
0 |
-2 |
1 |
2/13 |
|
|
x3 |
11/2 |
33/4 |
12/8 |
1 |
-1/4 |
0 |
2/5 |
|
|
F(X1) |
-288 |
-495 |
-140 |
0 |
48 |
0 |
0 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x1 |
2/13 |
1 |
7/26 |
0 |
-1/13 |
1/26 |
|
|
x3 |
12/13 |
0 |
50/208 |
1 |
1/26 |
-15/104 |
|
|
F(X1) |
-21111/13 |
0 |
-619/26 |
0 |
912/13 |
191/26 |
Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (7/26) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
|
|
x1 |
2/13 |
1 |
7/26 |
0 |
-1/13 |
1/26 |
4/7 |
|
|
x3 |
12/13 |
0 |
50/208 |
1 |
1/26 |
-15/104 |
321/25 |
|
|
F(X2) |
-21111/13 |
0 |
-619/26 |
0 |
912/13 |
191/26 |
0 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x2 |
4/7 |
35/7 |
1 |
0 |
-2/7 |
1/7 |
|
|
x3 |
11/14 |
-25/28 |
0 |
1 |
3/28 |
-5/28 |
|
|
F(X2) |
-208 |
25 |
0 |
0 |
8 |
20 |
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x2 |
4/7 |
35/7 |
1 |
0 |
-2/7 |
1/7 |
|
|
x3 |
11/14 |
-25/28 |
0 |
1 |
3/28 |
-5/28 |
|
|
F(X3) |
-208 |
25 |
0 |
0 |
8 |
20 |
Оптимальный план можно записать так:
x2 = 4/7
x3 = 11/14
F(X) = 100*4/7 + 192*11/14 = 208
В полученном плане среди значений базисных переменных имеются отрицательные значения.
Поэтому функция цели F(X) не ограничена на множестве допустимых планов, т.е. F(X) > ? и задача не имеет решения.
Отличную от нуля двойственную оценку имеют только те виды ресурсов, которые полностью используются в оптимальном плане.
Поэтому двойственные оценки определяют дефицитность ресурсов. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим, что:
1) 1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0)
10*1 + 8*1 + 0*0 = 18 = 18
2) 2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0)
4*1 + 6*1 + 0*0 = 10 = 10
Размещено на Allbest.ru
...Подобные документы
Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.
курсовая работа [58,9 K], добавлен 28.10.2014Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа [142,9 K], добавлен 24.10.2012Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Выбор языка программирования и среды разработки, программные модули и их взаимодействие между собой. Листинг разработанной программы.
курсовая работа [415,8 K], добавлен 08.09.2013Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Сущность симплекс-метода. Общая характеристика задачи о смесях. Разработка основных алгоритмов решения задачи. Решение задачи в среде визуального программирования Delphi. Проектирование интерфейса пользователя. Разработка форм ввода-вывода информации.
курсовая работа [476,6 K], добавлен 22.05.2012Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
контрольная работа [2,0 M], добавлен 02.05.2012Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Решение базовых задач линейного программирования симплекс-методом, их реализация на языке программирования С++. Математическое обеспечение; разработка алгоритма программы, решающей задачу с помощью симплекс-таблиц с произвольными свободными членами.
курсовая работа [217,8 K], добавлен 25.05.2014Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Составление производственного плана трех видов изделий при определенных возможностях машин. Написание алгоритма решения задачи симплексным методом: описание переменных, констант, нахождение разрешающего элемента, вычисление таблицы методом прямоугольника.
методичка [237,2 K], добавлен 25.09.2010Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Целевая функция с определенным направлением экстремума и система ограничений для нее. Разработка алгоритма программы, ее листинг.
курсовая работа [385,6 K], добавлен 15.05.2014
