Помощь по Теле2, тарифы, вопросы

3. Модифицированный симплекс-метод

В основу данной разновидности симплекс-метода положены такие особенности линейной алгебры, которые позволяют в ходе решения задачи работать с частью матрицы ограничений. Иногда метод называют методом обратной матрицы.

В процессе работы алгоритма происходит спонтанное обращение матрицы ограничений по частям, соответствующим текущим базисным векторам. Указанная способность делает весьма привлекательной машинную реализацию вычислений вследствие экономии памяти под промежуточные переменные и значительного сокращения времени счёта. Способность хороша для ситуаций, когда число переменных n значительно превышает число ограничений m.

В целом, метод отражает традиционные черты общего подхода к решению задач линейного программирования, включающего в себя канонизацию условий задачи, расчёт симплекс – разностей, проверку условий оптимальности, принятие решений о коррекции базиса и исключение Жордана – Гаусса. Особенности заключаются в наличии двух таблиц – основной и вспомогательной, порядке их заполнения и некоторой специфичности расчётных формул.

Зная оптимальный план этой задачи, на основе соотношений получаем оптимальный план исходной задачи.

Таким образом, процесс нахождения решения задачи нелинейного программирования включает следующие этапы:

1. Первоначальную задачу сводят к задаче линейного программирования.

2. Находят решение линейной задачи

Используя соотношения, определяют оптимальный план исходной задачи и находят максимальное значение целевой функции нелинейной задачи.

Первый этап: Получение задания к курсовой работе

1. Все числовые данные, касающиеся предполагаемых производственных и экономических процессов, берутся на основе шестизначного шифра:

Под каждую цифру записываются буквы a, b, c, d, e, f в следующем виде:

из последней строки таблицы индивидуальных заданий находим столбцы соответствующие буквам a, b, c, d, e, f. Тогда числовыми данными, необходимыми для выполнения данной курсовой работы, будут данные находящиеся в а – том столбце в строке 9, b – том столбце в строке 5, c – том столбце в строке 5, d – том столбце в строке 8, e – том столбце в строке 7и f – том столбце в строке 2.

По таблице исходных заданий для любого варианта заданий по столбцу а исполнитель получает вариант выполняемого задания. В моем случае для цифры 9 соответствует вариант 9.

На некотором заводе производится три вида продукта и при этом расходуется два вида ресурсов. Производственная функция каждого вида продукта на предприятии опишется равенствами:

где С i и - постоянные величины, i = 1, 2, 3;

X 1 – трудовые ресурсы в человеко-днях;

Х 2 – денежно-материальные средства, в тенге;

У i – получаемый продукт

Х 1 = а 1 х 1 + b 1 x 2 + c 1 x 3

Х 2 = а 2 х 1 + b 2 x 2 + c 2 x 3

Найти все неотрицательные базисные решения и определить оптимальный план F = y 1 + y 2 + y 3 .

Известно, что продукт для производства j – того вида затрачивается a ij единиц i – того ресурса. Эти затраты даются в таблицах 3.9.1. – 3.9.10

Последующие числовые данные берутся только из таблицы исходных данных выбранного варианта задания т.е. из таблицы №3.9.11.

2. По столбцу таблицы №3.9.11 для строки 8 исходной таблицей затрат единиц ресурса, будет таблица №3.9.4 т.е. следующая таблица:

3. По столбцу c – на 3 строке находим с 1 =6, α 1 =0,6

4. По столбцу d – на 5 строке определяем с 2 =5, α 2 =0,5

5. По столбцу e – по 4 строке установим, что с 3 =8, α 3 =0,4.

6. И наконец по столбцу f – в 1 строке найдем Т чел.дней =1000, П тенге = 280000

Для производства имеются трудовые ресурсы Т чел.дней и денежно-материальные средства П тенге.

Требуется найти оптимальный план выпуска продукции, при котором выпускаемый продукт будет наибольшим.

Второй этап – составление математической модели задачи

1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:

Через Х 1 обозначим ресурсы I вида.

Через Х 2 обозначим ресурсы II вида.

2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

Таким образом, получили задачу нелинейного программирования. Такие задачи называются задачами нелинейного программирования.

Решение задач нелинейного программирования осуществляется приведением их к задачам линейного программирования.

Для решения задачи линейного программирования применяется симплекс – метод.

Третий этап – выбор метода решения полученной математической задачи

1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:

8Х 1 + 4Х 2 + 6Х 3 + Х 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах...

Нахождение точки Куна-Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать при ограничениях С помощью теоремы 2 докажем, что решение является оптимальным. Имеем Так...

Лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...

Положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой...

Ба́зис (др.-греч. βασις, основа) - множество таких векторов в векторном пространстве, что любой вектор этого пространства может быть единственным образом представлен в виде линейной комбинации векторов из этого множества - базисных векторов

Базисом в пространстве R n называется любая система из n -линейно независимых векторов. Каждый вектор из R n , не входящих в базис, можно представить в виде линейной комбинации базисных векторов, т.е. разложить по базису.
Пусть – базис пространства R n и . Тогда найдутся такие числа λ 1 , λ 2 , …, λ n , что .
Коэффициенты разложения λ 1 , λ 2 , …, λ n , называются координатами вектора в базисе В. Если задан базис, то коэффициенты вектора определяются однозначно.

Замечание. В каждом n -мерном векторном пространстве можно выбрать бесчисленное множество различных базисов. В различных базисах один и тот же вектор имеет различные координаты, но единственные в выбранном базисе. Пример. Разложить вектор по базису .
Решение. . Подставим координаты всех векторов и выполним действия над ними:

Приравняв координаты, получим систему уравнений:

Решим ее: .
Таким образом, получим разложение: .
В базисе вектор имеет координаты .

Конец работы -

Эта тема принадлежит разделу:

Понятие вектора. Линейные операции над векторами

Вектором называется направленный отрезок имеющий определенную длину т е отрезок определенной длины у которого одна из ограничивающих его точек.. длина вектора называется его модулем и обозначается символом модуль вектора.. вектор называется нулевым обозначается если начало и конец его совпадают нулевой вектор не имеет определенного..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Базисом пространства называют такую систему векторов в которой все остальные векторы пространства можно представить в виде линейной комбинации векторов, входящих в базис.
На практике это все реализуется достаточно просто. Базис, как правило, проверяют на плоскости или в пространстве, а для этого нужно найти определитель матрицы второго, третьего порядка составленный из координат векторов. Ниже схематически записаны условия, при которых векторы образуют базис

Чтобы разложить вектор b по базисным векторам
e,e...,e[n] необходимо найти коэффициенты x, ..., x[n] при которых линейная комбинация векторов e,e...,e[n] равна вектору b:
x1*e+ ... + x[n]*e[n] = b.
Для этого векторное уравнение следует преобразовать к системе линейных уравнений и найти решения. Это также достаточно просто реализовать.
Найденные коэффициенты x, ..., x[n] называются координатами вектора b в базисе e,e...,e[n].
Перейдем к практической стороне темы.

Разложение вектора по векторам базиса

Задача 1. Проверьте, образуют ли векторы a1, a2 базис на плоскости

1) a1 (3; 5), a2 (4; 2)
Решение: Составляем определитель из координат векторов и вычисляем его

Определитель не равен нулю , следовательно векторы линейно независимы, а значит образуют базис .

2) a1 (2; -3), a2 (5;-1)
Решение: Вычисляем детерминант составленный из векторов

Определитель равен 13 (не равен нулю) - из этого следует что векторы a1, a2 является базисом на плоскости.

---=================---

Рассмотрим типичные примеры из программы МАУП по дисциплине "Высшая математика".

Задача 2. Показать, что векторы a1, a2, a3 образуют базис трехмерного векторного пространства, и разложить вектор b по этому базису (при решении системы линейных алгебраических уравнений использовать метод Крамера).
1) a1 (3; 1; 5), a2 (3; 2; 8), a3 (0; 1; 2), b (−3; 1; 2) .
Решение: Сначала рассмотрим систему векторов a1, a2, a3 и проверим определитель матрицы А

построенной на векторах отличных от нуля. Матрица содержит один нулевой элемент, поэтому детерминант целесообразнее вычислять как расписание по первому столбцу или третей строчке.

В рекзультаье вычислений получили что определитель отличен от нуля, следовательно векторы a1, a2, a3 линейно независимы .
Согласно определению векторы образуют базис в R3 . Запишем расписание вектора b по базису

Векторы равны, когда их соответствующие координаты равны.
Поэтому из векторного уравнения получим систему линейных уравнений

Решим СЛАУ методом Крамера . Для этого запишем систему уравнений в виде

Главный определитель СЛАУ всегда равен определителю составленному из векторов базиса

Поэтому на практике его не исчисляют дважды. Для нахождения вспомогательных определителей ставим столбец свободных членов на место каждого столбца главного определителя. Определители вычисляем по правилу треугольников



Подставим найденые определители в формулу Крамера



Итак, разложение вектора b по базису имеет вид b=-4a1+3a2-a3 . Координатами вектора b в базисе a1, a2, a3 будут (-4,3, 1).

2) a1 (1; -5; 2), a2 (2; 3; 0), a3 (1; -1; 1), b (3; 5; 1).
Решение: Проверяем векторы на базис - составляем определитель из координат векторов и вычисляем его

Определитель не равен нулю, следовательно векторы образуют базис в пространстве . Осталось найти расписание вектора b через данный базис. Для этого записываем векторное уравнение

и преобразуем к системе линейных уравнений

Записываем матричное уравнение

Далее для формул Крамера находим вспомогательные определители



Применяем формулы Крамера



Итак заданный вектора b имеет расписание через два вектора базиса b=-2a1+5a3, а его координаты в базисе равны b(-2,0, 5).