Решение алгебраических и трансцендентных уравнений

Скачать 2.1 Mb.

Название	Решение алгебраических и трансцендентных уравнений
страница	23/27
Дата публикации	26.05.2015
Размер	2.1 Mb.
Тип	Решение

100-bal.ru > Математика > Решение

1 ... 19 20 21 22 23 24 25 26 27

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

Решим ГРАФИЧЕСКИМ СПОСОБОМ пример 3. Его удобно применять, когда в задаче 2 (реже 3) неизвестных. В этом случае сначала строим область допустимых решений и в результате получаем многоугольник (многогранник). Затем можно действовать двумя способами. Во-первых, можно найти значения целевой функции в каждой из вершин и выбрать наименьшее. Во-вторых, можно нарисовать линии уровня целевой функции (это будут параллельные прямые) и с помощью них определить нужную нам вершину.

или

Надо найти точку, в которой целевая функция имеет максимум. Для этого необходимо начертить график функции f = 0, т.е. 7х1 + 5х2 = 0 и сдвигать его параллельно в сторону увеличения функции f до тех пор, пока он все еще будет пересекать наш многоугольник (пересекаться с областью решений). Итак, самое оптимальное решение - точка (2;4), f = 340.

Двойственная задача

В матричном виде задача, двойственная к задаче линейного программирования в общем виде, имеет вид: А^tY  C, Y  0, V=(b,y) -> max.

Если взять двойственную задачу к двойственной, то получим исходную задачу. (Здесь А^t - транспонированная матрица).

ТЕОРЕМА. Задача линейного программирования корректна тогда и только тогда, когда исходная и двойственная задачи являются допустимыми. При этом минимум целевой функции в исходной задаче равен максимуму целевой функции в задаче двойственной.

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

Напишем к задаче 2 двойственную:

, поэтому двойственная задача имеет вид:

и в ней ищется максимум функции V = 200y₁ + 130y₂ + 75y₃

Упражнение: написать двойственную задачу к задаче 3.

СИМПЛЕКС - МЕТОД

Будем исследовать задачу линейного программирования в КАНОНИЧЕСКОЙ ФОРМЕ:

АХ = В, Х 0, f = (с, х) -> min.

При этом пусть A - матрица размером r*n, где r - число независимых уравнений, n-число переменных, r
Заданная система имеет бесконечно много решений, при этом множество решений системы образует пространство размерности n-r. Чтобы его описать, надо выбрать n-r свободных переменных, тогда оставшиеся r переменных будут называться базисными и выражаться через свободные переменные.

Договоримся, что свободные переменные имеют номера с r+1 до n-ого, т.е. базисными переменными являются x₁,...,x_r.

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

Если свободным переменным придать значение, равное 0, то получим решение: (b₁,b₂,...,b_r,0,0,...,0).

В каком случае этот набор будет допустимым решением задачи? Так как х_i должны быть неотрицательными, то и все b_i должны быть неотрицательными. Такое решение задачи называется базисным решением. Базисных решений много. Геометрический смысл базисного решения состоит в том, что это координаты одной из вершин многогранника допустимых значений в n-мерном пространстве. Если задача корректна, то одно из базисных решений задачи будет оптимальным. Следовательно, перебирая все вершины и вычисляя значение целевой функции в каждой из них, мы можем найти решение задачи. Однако, данный процесс очень трудоемок: для нахождения одного базисного решения придется решать систему уравнений r*n (а количество базисных решений равно числу сочетаний из n по r, т.е. весьма велико).

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

1 ... 19 20 21 22 23 24 25 26 27

Похожие:

	Урока по теме: «уравнения. Решение задач с помощью уравнений» Зун учащихся по теме «Уравнения. Решение задач с помощью уравнений», навыков устных и письменных вычислений, упрощения алгебраических...		Урок математики в 6 ом классе по теме : «решение уравнений» Обучающие цели: повторение, обобщение и систематизация знаний учащихся по теме «Решение уравнений» и их применение отработка практических...
	Тематический план модуля «Решение некоторых трансцендентных уравнений и неравенств» Методические указания по выполнению выпускной квалификационной работы для специальности среднего профессионального образования 030912...		Тематический план курса I. Целые рациональные уравнения. 21 Лекция... Сведение уравнения к квадратному с помощью удачной подстановки. 13 Решение возвратных и обобщенных возвратных уравнений. 23 Решение...
	Урок конференция по теме "Решение задач с помощью квадратных уравнений" 8-й класс Решение задач с помощью квадратных уравнений”. Продолжить закрепление решение квадратных уравнений по формуле		Решение иррациональных уравнений и систем (10 класс) Цель: Закрепить решение иррациональных уравнений; развивать логическое мышление; расширять кругозор учащихся
	Дипломная работа «О некоторых применениях алгебры матриц» В данной дипломной работе рассматривается новые применения матриц в теории систем линейных уравнений, теории чисел и теории алгебраических...		Радиофизический факультет Ип в различных системах. Также содержание дисциплины направлено на обучение студентов основам решения задач линейной алгебры, решения...
	Оригинальность идеи и подхода, использование разнообразных приемов Определители. И их применение к решению систем линейных алгебраических уравнений		Тема: Решение задач с помощью системы уравнений первой и второй степени. Здравствуйте, ребята. Ещё начиная с начальной школы вы учились решать задачи. Для этого с каждым годом вы обучались всё новым и новым...
	Тема : Решение показательные уравнений Сегодня я дам вам действовать,чтобы вы поняли и запомнили способы и методы решения показательных уравнений		Урок математики в 4 классе по теме «Решение уравнений вида х×8 = 26 + 70» Познакомить с приемом решения уравнений на основе знаний связи между множителями и произведением
	Конспект урока на обобщающее повторение алгебры в 11 классе по теме... Повторение и обобщение знаний учащихся по теме «Решение тригонометрических уравнений и неравенств»		Элективный курс. Выполнила учитель математики моу сош №29 г. Чебоксары Морушкина Вера Васильевна Решение линейных уравнений (и уравнений приводимых к линейным), содержащих параметр. 5
	Программа по формированию навыков безопасного поведения на дорогах... Развитие и совершенствование техники алгебраических преобразований, решения уравнений, неравенств, систем		Решение уравнений, содержащих параметры, один из труднейших разделов... Предлагаемый курс «Методы решения алгебраических задач с параметром» является предметно-ориентированным и предназначен для реализации...

Школьные материалы

Решение алгебраических и трансцендентных уравнений

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

Двойственная задача

СИМПЛЕКС - МЕТОД

Похожие: