Решение задачи одним из математических методов




НазваниеРешение задачи одним из математических методов
страница1/4
Дата публикации17.10.2016
Размер9,76 Kb.
ТипРешение
  1   2   3   4
1. Предмет и задачи курса. Экономико-математическая модель задачи линейного программирования. Пример.

Математическое программирование – дисциплина, занимающаяся изучением экстремальных задач (max/min), разработкой методов их решения.

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

^ Этапы линейного программирования:

  1. постановка задачи (словесная формулировка), формулировка условий задачи, выбор критериев оптимальность

  2. сбор необходимых данных, составление исходной матрицы

  3. построение экономико-математической модели

  4. решение задачи одним из математических методов

  5. анализ полученных результатов

Экономико-математическая модель.

Для производства 3 видов изделий (A,B,C) используется 3 вида различного сырья в количестве 180, 210, 244 единицы. Нормы затрат каждого вида сырья на производство единицы продукции данного вида приведены в таблице:

I

4

2

1

II

3

1

3

III

1

2

5

Цена от реализации изделий:

A

B

C

10

14

12

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

Решение: пусть предприятие производит x1 изделий вида А, x2 изделий вида B и x3 изделий вида С. Так как производство ограничено имеющимся сырьем и количеством изготовляемых изделий, то должны выписываться условия:

1+2х23

12+3х3

х1+2х2+5х3

все x0,

Z = 10x1+14x2+12x3 (max).

Методы решения:

  1. графический (быстро и наглядно решает простейшие задачи)

  2. симплекс-метод (универсальный метод)

  3. метод потенциалов (им решаются транспортные задачи)

Необходим контроль, анализ решений, корректировка оптимального плана.

2. Общая постановка задачи линейного программирования. Каноническая форма задачи линейного программирования.

Найти совокупность значений x1, x2, … , xn, удовлетворяющим условию и доставляющим функции Z экстремальное значение.

n

∑aijxj (<=, =>,=)bi - ограничения (1,1)

i=1

xj=>0 - условия неотрицательности (1,2)

i=1,m

j=1,n
n

Z = ∑cjxj - целевая функция (1,3)

i=1

Совокупность значений переменных x1, x2, … , xn, удовлетворяющих условиям 1.1-1.3 называется допустимым планом. Оптимальным планом называется такое решение, при котором целевая функции достигает экстремума.

Канонический вид задачи линейного програмирования:

а11х1+ а12х2+ …+а1jхj+..+a1nxn=b1

а21х1+ а22х2+…+ а2jхj+..+a2nxn=b2

аi1х1+ аi2х2+…+ аijхj+..+ainxn=bi

аm1х1+ аm2х2+…+ аmjхj+..+amnxn=bm

все xi =>0, i=1,n j=1,m

Z=c1x1+c2x2+…+cnxn (max)

Приведение задачи к каноническому виду:

  1. переход от ограничений-неравенств к ограничениям-равенствам (ограничение-неравенство вида  сводится к ограничению-равенству добавлением к его левой части дополнительной (балансовой) неотрицательной переменной, а вида  - вычитанием)

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

  3. переход задачи min к max (Z = Z)

3. Система линейных алгебраических уравнений (СЛАУ). Метод Гаусса. Пример.

Система м линейных уравнений с н переменными имеет вид:

а11х1+ а12х2+ …+а1jхj+..+a1nxn=b1

а21х1+ а22х2+…+ а2jхj+..+a2nxn=b2

аi1х1+ аi2х2+…+ аijхj+..+ainxn=bi

аm1х1+ аm2х2+…+ аmjхj+..+amnxn=bm

где аij, bi (i=1,n j=1,m) - произвольные числа при переменных, называемые коэффициентами при переменных и свободныи членами уравнений.

В более краткой записи с помощью знаков суммирования систему можно записать:

n

∑aijxj =bi

j=1

Решение такой системы – это набор чисел, при подстановке которых в эту систему каждое уравнение превращается в тождество. Совместной СЛАУ называется такая система, которая имеет хотя бы одно решение. Если система решений не имеет, то она называется несовместной.

^ Метод Гаусса.

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

Ход решения

  1. умножая 1-ое уравнение на подходящие числа и прбавляя полученные уравнения соответственно ко второму, третьему ,… m-му уравнению системы, исключим переменную х1 из всех последующих уравнений, начиная со второго.

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

4. Матрицы.

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

Матрица состоящая из одной строки, называется матрицей (вектором) – строк, а из одного столбца – матрицей –столбцом

Матрица называется квадратной, если число ее строк = числу ее столбцов. Элементы матрицы, у которых номера столбца = номеру строки (i=j), называются диагональными и образуют главную диагональ матрицы. Если все недиоганальные элементы квадратной матрицы =0, то матрица назыв диагональной. Если у диагональной матрицы все диагональные элементы = 1, то матрица назыв единичной матрицей. Матрица любого порядка назыв нулевой, если все ее эл-ты = 0

^ Операции над матрицами.

  1. Умножение матрицы на число. Все эл-ты матрицы умножаем на это число. Произведением матрицы А на число № назыв матрица В=№А.

  2. Сложение матриц. Сумма 2х матриц одинакового размера назыв матрица С=А+В, эл-ты которой cij=aij+bij

  3. Вычитание. А-В=А+(-1)*В

  4. Умножение матриц. Умножение матрицы А на матрицу В определено, когда число столбцов 1ой матрицы =числу строк второй. Тогда произведением матриц А*В назыв такая матрица С, каждый элемент которой сij равен сумме произведений элементов i-ой строки матрицы А на соответствующие элементы j-го столбца матрицы В.

  5. Транспонирование. Переход от матрицы А к матрице А’, в которой строки и столбцы поменялись местами с сохранением порядка.

  6. Возведение в степень. Целой положительной степенью А в степени м (м>1)квадратной матрицы А называется произведение м матриц, равных А.


В матрице А размера m x n вычеркиванием каких-либо строк и столбцов можно вычленить квадратные подматрицы k-го порядка, где k≤min(m;n). Определители таких подматриц называются минорами k-го порядка матрицы А.

^ Ранг матрицы – наивысший порядок отличных от нуля миноров матрицы.
5. Обратная матрица.

Матрица А(-1) называется обратной по отношению к квадратной матрице А, если при умножении этой матрицы на данную как справа, так и слева получается единичная матрица.

Теорема: Обратная матрица А(-1)существует (и единственна) тогда и только тогда, когда исходная матрица невырожденная.

Необходимость. Пусть матрица А имеет обратную А (-1), т.е. А*А (-1)= А(-1)А=Е. Тогда по свойству определителя (определитель произведения двух квадратных матриц равен произведению их определителей) │А*А(-1)│= │А│*│А(-1)│= │Е│=1, т.е. │А│=/0 и │A(-1) =/ 0

Достаточность. Пусть │А│=/ 0.Рассмотрим квадратную матрицу n-ого порядка Ẫ, называемую присоединенной, элементы которой являются алгебраическими дополнениями элементов матрицы А’, транспонированной к А: ẫij= А’ij=Aji (i=1,n; j=1,n) тогда элементы произведения матриц Ẫ*А=В определяются по правилу умножения матриц: bij = s=1∑n ẫisasj = s=1∑n Asi asj =

|A| i=j

0 при i=/j

Поэтому матрица В является диагональной, элементы ее главной диагонали = определителю исходной матрицы. Аналогично доказывается, что произведение А на Ẫ равно той же матрице В:А* Ẫ= Ẫ*А=В. Отсюда следует, что если в качестве обратной матрицы взять матрицу А(-1)= 1/ │А│* Ẫ (│А│<>0) (1)

То произведение А(-1) *А и А*А(-1) равны единичной матрице Е n-ого порядка: А(-1)*А=А*А(-1)= 1/│А│*В=Е

Алгоритм вычисления:

  1. находим определитель исходной матрицы. Если │А│=0, то матрица А – вырожденная и обратной матрицы не существует. Если │А│<>0, то матрица А – невырожденная и обратная матрица существует.

  2. Находим матрицу А’, транспонированную к А

  3. Находим алгебраическое дополнение элементов транспонированной матрицы А’ij=Aij (i=1,n; j=1,n) и составляем из них присоединенную матрицу Ẫ: ẫij= А’ij= Аij

  4. Вычисляем обратную матрицу по формуле (1,14)

  5. Проверяем правильность вычисления обратной матрицы А(-1), исходя из ее определения А*А (-1)= =А(-1)А=Е


^ 6. Неопределенная система ЛАУ. Базисные.

Неопределённая система линейных алгебраических уравнений имеет бесчисленное множество решений. Придав свободным неизвестным нулевое значение получим решение системы, которое называется базисом.

Если система приведена к единичному базису, то её базисное решение находится сразу. Для этого необходимо положить свободные неизвестные равными нулю, тогда свободные члены определят значения базисных неизвестных.

Чтобы найти все базисные решения системы не возвращаясь вновь к исходной системе, используют преобразование однократного перемещения, основанном на методе Ж. Гаусса.

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

Число базисных решений не должно превышать число С

Сrn=n!/r!(n-r)!

N – количество неизвестных в системе.

R – ранг матрицы (кол-во уравнений в системе)
^ 7. Множества. Выпуклые линейные комбинации.

Пусть на плоскости х10х2 заданы две точки А1(х’1х’2) и А2(х’’1х’’2), определяющие направленный отрезок А1А2. Выразим координаты произвольной внутренней точки через координаты его концов, векторы А1А и А1А2 параллельны и одинаково направленные: А1А = t(А1А2), 0<=t<=1

A1A2=(x1-x’1;x2-x’2), A1A2=(x’’1-x’1;x’’2-x’2), x1-x’1=t(x’’1-x’1), x2-x’2=t(x’’2-x’2)

x1=(1-t)x’1+tx’’1, 1-t=λ1, t= λ2

x1= λ1x’1+ λ2x’’1, x2= λ1x’2+ λ2x’’2

λ1≥0 λ2≥0, λ1+ λ2=1

учитывая, что координаты точки А являются суммами одноимённых координат точек А1 и А2, умноженных соответственно на числа λ1 и λ 2, окончательно получаем:

А= λ1А1+ λ2А2, λ 1<=0, λ2≥0, λ1+λ2=1

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

При условии λ1=1 и λ2=0 точка А совпадает с началом отрезка А1, λ1=0 λ2=1 – с концом

Таким образом если t пробегает все значения от 0 до1 то точка А описывает отрезок А1А2. Точки А1 и А2 называют угловыми или крайними точками отрезка А1А2. Из определения линейной выпуклой комбинации точек очевидно что угловая точка не может быть представлена как выпуклая линейная комбинация 2 других точек отрезка.

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

Точка выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь 2 других различных точек данного множества.
^ 8. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.

Доказательство. Возьмем для простоты n=2, а в качестве многоугольника – треугольник X1X2X3. Через произвольную точку Х треугольника проведем отрезок Х1Х4. Поскольку точка Х лежит на этом отрезке, то Х=α1Х1 + α4Х4, где α1≥0, α2≥0, α1+α4=1.

Точка Х4 лежит на отрезке Х2Х3, следовательно, Х4= α2Х2+ α3Х3, где α2≥0, α3≥0, α2+α3=1. Подставив значение Х4 в выражение для Х, получим Х= α1Х1 + α4(α2Х2+ α3Х3)= α1Х1 + α2 α4Х2 + α3α4Х3.

Обозначив t1= α1, t2= α2α4, t3= α3α4, получим окончательно X=t1X1+t2X2+t3X3, где t1≥0, t2≥0, t3≥0 и t1+t2+t3=1.

Таким образом, точка Х есть выпуклая линейная комбинация угловых точек треугольника Х1Х2Х3.


^ 9. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.

Доказательство. Пусть Х1=(х1(1), х2(1),…,xn(1)) и X2=(x1(2), x2(2),…,xn(2) – два допустимых решения задачи, заданной в матричной форме. Тогда АХ1=В и АХ2=В. Рассмотрим выпуклую линейную комбинацию решений Х1 и Х2, т.е. Х=α1Х1 + α2Х2 при α1≥0, α2≥0 и α1 + α2 =1, и покажем, что она также является решением системы. В самом деле, АХ = А(α1Х1 + α2Х2) = α1АХ1 + (1- α1)АХ2 = α1В + (1- α1)В=В, т.е. решение Х удовлетворяет системе. Но так как Х1≥0, Х1≥0, α1≥0, α2≥0, то и Х ≥0, т.е решение Х удовлетворяет и условию.
^ 10. Теорема об экстремальном значении целевой функции.

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

Доказательство. Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х1, Х2, …, Хр, а оптимальное решение – через Х*. Тогда F(X*)≥F(X) для всех точек Х многогранника решений. Если Х* - угловая точка, то первая часть теоремы доказана. Предположим, что Х* не является угловой точкой , тогда на основании теоремы о выпуклом многоугольнике, являющемся выпуклой линейной комбинацией своих угловых точек, Х* можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е. Х*= α1Х1 + α2Х2 +…+ αрХр, αj≥0, j=1,p; j=1Σn αj=1.

Так как F(X) линейная функция, получаем F(X*)=F(α1Х1 + α2Х2 +…+ αрХр)= α1F(X1) + α2F(X2) + … + αpF(Xp). (1)

В этом разложении среди значений F(xj) (j=1,p) выберем максимальное. Пусть оно соответствует угловой точке Xk (1≤k≤p); обозначим его черех М, т.е. F(Xk)=M. Заменим в выражении (1) каждое значение этим максимальным значением М. Тогда, учитывая, что αj≥0, j=1Σp αj=1, найдем F(X*)≤α1M + α2M + … + αpM= M j=1 Σp αj=M. По предположению Х* - оптимальное решение, поэтому, с одной стороны, F(X*)≥F(Xk)=М, но, с другой стороны, доказано, что F(X*)≤М, следовательно, F(X*)=М=F(Xk), где Xk – угловая точка. Итак, существует угловая точка Xk, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(X) принимает максимальное значение более чем в одной угловой точке, например, в точках X1, X2, … Xq, где 1≤q≤p; тогда F(X1)=F(X2)=…=F(Xq)=M.

Пусть Х – выпуклая комбинация этих угловых точек, т.е Х= α1Х1 + α2Х2 +…+ αqХq, aj≥0 (j=1,q), j=1Σq aj=1. В этом случае, учитывая, что функция F(X) – линейная, получим F(X)=А(α1Х1 + α2Х2 +…+ αqХq)= α1F(X1) + α2F(X2) + … + αqF(Xq) = α1M + α2M +…+ αqM = M j=1Σq aj=M, т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек X1, X2,…., Xq.
  1   2   3   4

Похожие:

Решение задачи одним из математических методов icon2. Решение задачи на построение графика функции в среде электронной таблицы
Решение расчетной задачи с использованием математических функций (среднее арифметическое, минимум, максимум и др.) в среде электронной...
Решение задачи одним из математических методов iconРешение одной задачи распределения с помощью методов транспортной...
Алексеев Н. С. Компьютерное моделирование простых форм кристаллов
Решение задачи одним из математических методов iconНаука о веществах, их строении, свойствах и превращениях. В широком...
Ни одно серьезное химическое исследование не обходится без использования физических методов для установления структуры веществ и...
Решение задачи одним из математических методов iconNm-review | Моделирование \ Прикладные вопросы Математическое моделирование...
Проект ориентирован на решение локальной задачи – развитие и применение методов моделирования в востребованных секторах рынка. Ставит...
Решение задачи одним из математических методов iconВ настоящее время, задачи решаемые рэу все более усложняются, это...
Риближения его истинного значения к номинальному, при отклонении первичных параметров, соответствующих производственным погрешностям....
Решение задачи одним из математических методов iconБалтийский государственный технический университет "военмех" им. Д. Ф. Устинова
В нашем случае n Однако, после моделирование было принято решение построить фильтр 10-го порядка. Одним их методов построения полосового...
Решение задачи одним из математических методов iconПрограмма
В настоящее время к числу актуальных вопросов физического образования относится умение решать физические задачи. Решение физических...
Решение задачи одним из математических методов iconВ какую Российскую энергетическую компанию внедерена система ifs applications?
Применение технических средств и математических методов, создание на их основе машинных систем
Решение задачи одним из математических методов iconЛабораторная работа №1 решение математических задач средствами ms excel
Для решения задачи необходимо разместить элементы матрицы в ячейках листа электронной таблицы, например в диапазоне. Затем в любую...
Решение задачи одним из математических методов iconУчебно-методический комплекс рабочая программа для студентов по специальности...
Рассмотрено на заседании кафедры математических методов, экономики и информационных технологий в экономике, 20. 04. 2011, №9
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
dopoln.ru
Главная страница