Решение задач линейного программирования
Решение прямой задачи линейного программирования симплексным методом с использованием симплексной таблицы. Определение максимального значения целевой функции. Расширенная матрица системы ограничений и равенств задачи. Проверка критерия оптимальности.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 06.03.2013 |
| Размер файла | 17,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Решение задач линейного программирования
Переход к КЗЛП
F(X) = 9x1 + 10x2 + 16x3 > max
при ограничениях:
18x1 + 15x2 + 12x3?360
6x1 + 4x2 + 8x3?192
5x1 + 3x2 + 3x3?180
Для приведения ЗЛП к канонической форме необходимо:
В 1-м неравенстве смысла (?) вводим базисную переменную x4. В 2-м неравенстве смысла (?) вводим базисную переменную x5. В 3-м неравенстве смысла (?) вводим базисную переменную x6.
18x1 + 15x2 + 12x3 + 1x4 + 0x5 + 0x6 = 360
6x1 + 4x2 + 8x3 + 0x4 + 1x5 + 0x6 = 192
5x1 + 3x2 + 3x3 + 0x4 + 0x5 + 1x6 = 180
F(X) = 9x1 + 10x2 + 16x3
Переход к СЗЛП
Расширенная матрица системы ограничений-равенств данной задачи:
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (, , ).
Соответствующие уравнения имеют вид:
18x1 + 15x2 + 12x3 + x4 = 360
6x1 + 4x2 + 8x3 + x5 = 192
5x1 + 3x2 + 3x3 + x6 = 180
Выразим базисные переменные через остальные:
x = - 18x1 - 15x2 - 12x3 - x4+360
x = - 6x1 - 4x2 - 8x3 - x5+192
x = - 5x1 - 3x2 - 3x3 - x6+180
Подставим их в целевую функцию:
F(X) = 9x1 + 10x2 + 16x3
Система неравенств:
18x1 - 15x2 - 12x3 - x4+360 ? 0
6x1 - 4x2 - 8x3 - x5+192 ? 0
Приводим систему неравенств к следующему виду:
18x1 + 15x2 + 12x3 + x4 ? 360
6x1 + 4x2 + 8x3 + x5 ? 192
5x1 + 3x2 + 3x3 + x6 ? 180
F(X) = 9x1 + 10x2 + 16x3 > max
Упростим систему.
F(X) = 9x1 + 10x2 + 16x3 > max
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции
F(X) = 9x1 + 10x2 + 16x3
при следующих условиях-ограничений.
18x1 + 15x2 + 12x3 + x4?360
6x1 + 4x2 + 8x3 + x5?192
5x1 + 3x2 + 3x3 + x6?180
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (?) вводим базисную переменную x7. В 2-м неравенстве смысла (?) вводим базисную переменную x8. В 3-м неравенстве смысла (?) вводим базисную переменную x9.
Матрица коэффициентов этой системы уравнений имеет вид:
|
18 |
15 |
12 |
1 |
0 |
0 |
1 |
0 |
0 |
|
|
6 |
4 |
8 |
0 |
1 |
0 |
0 |
1 |
0 |
|
|
5 |
3 |
3 |
0 |
0 |
1 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Полагая, что свободные переменные равны 0, получим первый опорный план:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
|
x7 |
360 |
18 |
15 |
12 |
1 |
0 |
0 |
1 |
|
|
x8 |
192 |
6 |
4 |
8 |
0 |
1 |
0 |
0 |
|
|
x9 |
180 |
5 |
3 |
3 |
0 |
0 |
1 |
0 |
|
|
F(X0) |
0 |
-9 |
-10 |
-16 |
0 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (8) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
|
x7 |
360 |
18 |
15 |
12 |
1 |
0 |
0 |
1 |
|
|
x8 |
192 |
6 |
4 |
8 |
0 |
1 |
0 |
0 |
|
|
x9 |
180 |
5 |
3 |
3 |
0 |
0 |
1 |
0 |
|
|
F(X1) |
0 |
-9 |
-10 |
-16 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x8 в план 1 войдет переменная x3 .
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=8
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (8), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
|
|
360-(192 * 12):8 |
18-(6 * 12):8 |
15-(4 * 12):8 |
12-(8 * 12):8 |
|
|
192 : 8 |
6 : 8 |
4 : 8 |
8 : 8 |
|
|
180-(192 * 3):8 |
5-(6 * 3):8 |
3-(4 * 3):8 |
3-(8 * 3):8 |
|
|
0-(192 * -16):8 |
-9-(6 * -16):8 |
-10-(4 * -16):8 |
-16-(8 * -16):8 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x7 |
72 |
9 |
9 |
0 |
1 |
-11/2 |
0 |
|
|
x3 |
24 |
3/4 |
1/2 |
1 |
0 |
1/8 |
0 |
|
|
x9 |
108 |
23/4 |
11/2 |
0 |
0 |
-3/8 |
1 |
|
|
F(X1) |
384 |
3 |
-2 |
0 |
0 |
2 |
0 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (9) и находится на пересечении ведущего столбца и ведущей строки.
симплексный задача линейный программирование
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
x7 |
72 |
9 |
9 |
0 |
1 |
-11/2 |
0 |
|
|
x3 |
24 |
3/4 |
1/2 |
1 |
0 |
1/8 |
0 |
|
|
x9 |
108 |
23/4 |
11/2 |
0 |
0 |
-3/8 |
1 |
|
|
F(X2) |
384 |
3 |
-2 |
0 |
0 |
2 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 2 войдет переменная x2 .
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x7 плана 1 на разрешающий элемент РЭ=9
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
|
|
72 : 9 |
9 : 9 |
9 : 9 |
0 : 9 |
1 : 9 |
|
|
24-(72 * 1/2):9 |
3/4-(9 * 1/2):9 |
1/2-(9 * 1/2):9 |
1-(0 * 1/2):9 |
0-(1 * 1/2):9 |
|
|
108-(72 * 11/2):9 |
23/4-(9 * 11/2):9 |
11/2-(9 * 11/2):9 |
0-(0 * 11/2):9 |
0-(1 * 11/2):9 |
|
|
384-(72 * -2):9 |
3-(9 * -2):9 |
-2-(9 * -2):9 |
0-(0 * -2):9 |
0-(1 * -2):9 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
|
x2 |
8 |
1 |
1 |
0 |
1/9 |
|
|
x3 |
20 |
1/4 |
0 |
1 |
-1/18 |
|
|
x9 |
96 |
11/4 |
0 |
0 |
-1/6 |
|
|
F(X2) |
400 |
5 |
0 |
0 |
2/9 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Оптимальный план можно записать так:
x2 = 8
x3 = 20
x9 = 96
F(X) = 10*8 + 16*20 = 400
Возвращаемся к системе уравнения в СЗЛП.
x = - 18x1 - 15x2 - 12x3 - x4+360
x = - 6x1 - 4x2 - 8x3 - x5+192
x = - 5x1 - 3x2 - 3x3 - x6+180
Подставим в них найденные переменные.
x = -18*0 -15*8 -12*20 -1*0 + 0*0 + 0*0 + 360 = 0
x = -6*0 -4*8 -8*20 + 0*0 -1*0 + 0*0 + 192 = 0
x = -5*0 -3*8 -3*20 + 0*0 + 0*0 -1*0 + 180 = 96
Размещено на Allbest.ru
...Подобные документы
Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Составление плана выпуска продукции с целью получения максимальной прибыли при ее реализации. Вид и запас сырья, прибыль от единицы продукции и общее количество. Приведение системы ограничений к каноническому виду. Составление симплексной таблицы.
практическая работа [12,8 K], добавлен 24.05.2009Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Численные методы поиска безусловного экстремума. Задачи безусловной минимизации. Расчет минимума функции методом покоординатного спуска. Решение задач линейного программирования графическим и симплексным методом. Работа с программой MathCAD.
курсовая работа [517,9 K], добавлен 30.04.2011Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Симплексный метод как универсальное решение задач линейного программирования. Применение метода Жордана-Гаусса для системы линейных уравнений в канонической форме. Опорное решение системы ограничений. Критерий оптимальности. Задача канонической формы.
презентация [2,0 M], добавлен 11.04.2013Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций.
курсовая работа [126,5 K], добавлен 21.05.2010Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Общее понятие вектора и векторного пространства, их свойства и дополнительные структуры. Графический метод в решении задачи линейного программирования, его особенности и область применения. Примеры решения экономических задач графическим способом.
курсовая работа [1,2 M], добавлен 14.11.2010Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.
курсовая работа [197,1 K], добавлен 09.04.2013Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
контрольная работа [79,4 K], добавлен 04.06.2010Геометрический смысл решений неравенств, уравнений и их систем. Определение понятия двойственности с помощью преобразования Лежандра. Разбор примеров нахождения переменных или коэффициентов при неизвестных в целевой функции двойственной задачи.
дипломная работа [2,6 M], добавлен 30.04.2011Поиск участков возрастания и убывания функций, классификация экстремума. Умножение матриц АВ–1С. Теория вероятности события и случайных величин. Построение интервальной группировки данных. Решение задачи линейного программирования, построение графика.
контрольная работа [127,1 K], добавлен 11.11.2012
