Размещено на http://www.allbest.ru/

1. Раздел ЛЕКЦИОННЫЙ КОМПЛЕКС

1.1 Задачи линейного программирования

Глоссарий

Программирование - в широком смысле - процесс подготовки и составления программы деятельности, выполнение которой должно привести к определенным целям.

Оптимальное решение - это выбранное по какому-либо критерию оптимизации наиболее эффективное из всех альтернативных вариантов решение.

Математические модели - основное средство решения задач оптимизации любой деятельности.

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

Задачи записанные на языке формул, уравнений представляет собой математическое моделирование

Лекция -1. Тема лекции: Введение в математическое программирование

линейный программирование неравенство симплекс

Цель лекции: Знакомствос целями и задачами курса, с задача математического программирования.

Вопросы к теме:

1 Понятие математического программирования

2 История развития математического программирования

3 Виды задач математического программирования

Тезисы лекции: Развитие относится к 30-ым годам. Математик - Толстой . Бурное развитие после войны. Всюду, где возникает необходимость выбора среди множества вариантов, решения какой либо проблемы (получения максимальной прибыли, минимальный расходы и.т.д) , выбор наилучшего в каком-то смысле - там и возникают задачи математического программирования.

Задачи записанные на языке формул, уравнений представляет собой математическое моделирование

Найти max или min функции Z=f() , где ц()bi , где (i=1,k); ц()=bi , где (i=1,k) (i=k+1, L);

- управляемый параметр. - неуправляемый параметр. (не учитывается)

Чтобы решить задачу имея математическую модель нужно знать математические метод (Гауса, Крамера, матричный и.т.д) Зная метод => нужно знать алгоритм.

В зависимости от того какими являются функции f и цi , задачи делятся на два класса :

1) Если функции f и цi линейны относительно параметров Х и У , то имеем задачу линейного программирования. (Л.П.)

2) Если хотя бы одна из функций f и цi нелинейная относительно параметров и , то имеем нелинейную задачу. (Н.П.)

Для Л.П. существует универсальный способ. Симплекс - метод Основ. разработку дал Дансон.

В Н.П. самым изученным является выпуклое программирование - это когда находится минимум выпуклой функции на выпуклом множестве или максимум вогнутой функции на выпуклом множестве. Существуют так же :1) Д.П. - динамическое программирование , вся задача разбивается на n-этапов. 2) Стохастическое программирование - случайные параметры. 3) Э.П. - эвристическое программирование , где оптимальное решение найти сложно из-за большого количества вариантов. 4) Ц.П. - целочисленное программирование.

Задания для самоконтроля

1. Что представляет собой математическое программирование?

2. В чем заключается математическая модель задачи.

3. Виды задач математического программирования

Лекция -2. Тема лекции: Линейное программирование. Общая и основная задачи ЛП

Цель лекции: Усвоение основных понятий ЛП.

Вопросы к теме:

1 Задачи ЛП

2 Преобразование задач ЛП

Тезисы лекции:

В зависимости от системы ограничения различают в Л.П. три формы модели 1) каноническая 2) стандартная форма 3) общая форма. Эти три формы эквиваленты между собой в том смысле , что от одной формы можно перейти к другой с помощью элементарных преобразований.

Стандартная форма модели З.Л.П. . Система задачи формируется : Найти вектор х, удовлетворяющий системе ограничений и условию не отрицательности.

а11х1+а12х2+…+а1nxn<=b1

a21x1+a22x2+…+a2nxn<=b2

….

am1x1+am2x2+…+amnxn<=bn

xj>=0 j=1,4; Z=c1x1+c2x2+..+cnxn->max

A-матрица (m*n) Z=cx->max Ax<=b x>=0 ; C=(C1 C2 …Cn) b(b1 b2..bm)

Каноническая тоже самое только в системе ограничений = и Ax=b.

Общая форма. Найти вектор Х, удовлетворяющий системе ограничений

a11x1+a12x2+...+a1nxn=b1

am1x1+amnxn=bm

Xj>=0 (j=1,l) l<n Для которого Z=с1х1+cnxn -> max

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

Переход от стандартной формы к канонической форме.

ai1x1+ai2x2+…+ainxn<=bi (2)

ai1x1+ai2x2+..+ainxn+ainxi+n=b xn+i>=0 , i=1,m - балансовые переменные. (1)

Можно доказать, что все решения системы 1 равны решениям неравенства 2 и в этом сысле они эквивалентны. Функцию цели эти переменные(xn+i) могут быть введены с коэффициентами =0 => z=c1x1+..+cnxn+oXn+1+..+oxn+m->max

Переход от канонической к стандартной.

Осуществляется двумя способами.

1. а=b (a>=b a<=b) -> a1x1+a2x2=b a1x1+a2x2>=b

a1x1+a2x2<=b

2. Z=c1x1+…+cnxn->max

a11x1+…+a1nxn=b1

a21x1+…+a2nxn=b2

am1x1+…+amnxn=bm (m<n - бесконечно много решений)

Приводим к единичному базису методом гауса. Приравняем все свободные переменные к 0, т.е. xm+1=xm+2=0 то получим первоначальное базисное решение.

Выражаем все базисные переменные через свободные.

Х1=b1-a1,m+1xm+1-..-a1,nxn>=0

Xm=bm-am,m+1-…-amnxn>=0

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

Z=c1(b1-..-a1nxn)+c2(b2-..-a2nxn)+cm(bm-..-amnxn)+cm+1xm+1+…+cnxn->max/

Переход от задачи max к min и наоборот.

Во всех формах моделях все сводится к max, но иногда необходимо найти min/

Z=f(x)

min

z1max

z1=f(x)

Чтобы перейти от задачи min к max достаточно поменять знак и ввести новое значение функции.

Задания для самоконтроля

1. Общая задача ЛП

2. Симметричная задача ЛП.

3. Основная задача ЛП.

4. Правила преобразования ЗЛП.

Лекция -3. Тема лекции: Свойства основной задачи ЛП. Геометрическая интерпретация ЗЛП

Цель лекции: Знакомство с основными свойствами ЛП.

Вопросы к теме:

1 Свойства ОЗЛП

2 Геометричекая интерпретация ЗЛП

Тезисы лекции:

Графический метод решения Л.П.

Понятие: допустимого, оптимального, опорного решений, понятие области допустимых решений.

Вектор Х называется допустимым решением , если он удовлетворяет системе ограничений и условиям не отрицательности если они есть.

Вектор Х называется оптимальным решением если он является допустимым , а функция цели в этом решении достигает своего оптимального значения. (max or min)

Опорным решением называется не отрицательное базисное решение системы ограничений.

x1+x3 -x4=1

x2+2x3+4x4=-2

x1 и х2 -базисные неизвестные. Х3,х4 - неизвестные .

Приравняем свободные к 0. , тогда базисные неизвестные получают значения равные х1=1 х2=-2 и получаем базисное решение. Оно является не опорным , т.к. х=-2. Данное решение допустимое , базисное, не опорное.

Областью допустимых решений называется - совокупность всех допустимых решений системы.

Геометрическая интерпретация линейного неравенства.

n=2 a1x1+a2x2<=b (n-кол-во переменных , m число неравенств )

Из математики знаем что геометрическим образом уравнение а1х1+а2х2=b - прямая на плоскости х1 х2 Прямая разбивает плоскость на две полуплоскости . а1х1+а2х2<=b и >= , т.е. одно из плоскостей является решением. Чтобы определить какая четверть является решением данного неравенства нужно взять любую точку M и подставить в данное неравенство. И если не равенство удовлетворяется, то точка эта принадлежит той полуплоскости в которая является решением . И наоборот.

Геометрическая интерпретация системы линейных неравенств.

n=2 . a1x1+a1x2<=b1 ГИСЛН - является пересечение всех полуплоскостей соответству

a2x1+a2x2<=b2 ющих каждому неравенству системы , таким образом нашли ОДР.

am1x1+am2x2<=bm

Возможные случаи ОДР.

ОДР является точка.

ОДР выпуклый многоугольник.

ОДР выпуклая многоугольная область.

ОДР - пустая область

Свойства допустимых планов.

Выпуклая линейная комбинация точек . х1 х2 …хk сумма вида б1х1+ б2х2+ ...+ бkxk , где бi =1 (бi>=0 бi - коэффициент линейной комбинации).

Выпуклым множеством называется такое множество т. Д на плоскости , когда вместе с любыми двумя точками Х1є Д ; Х2 є Д принадлежащим множеству Д. Ему принадлежит и их выпуклая Л.К. х=tx1+(1-t)x2 є Д 0<=t<=1

Крайняя точка - т.Х выпуклого множества называется крайней если она не может быть представлена в виде выпуклой Л.К. любых двух точек этого множества (n=2)

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

Свойства допустимых планов.

Теорема №1

Множество допустимых планов З.Л.П. выпукла если оно не пусто.

Дано: Д- не является пустым множеством - ОДР

Доказать Ж Д- выпуклое множество.

Док-во :

Х1 єД; Х2 єД,то оно удовлетворяет системе ограничений в З.Л.П. Z=cx->max Ax=b X>=0

Ax1=b 0<=t<=1

Ax2=b (1-t) => tAx1+(1-t)Ax2=bt+b(1-t) = A[tx1+(1-t)x2]=b

t>=0

x1; x2>=0 => x>=0

1-t>=0

Ax=b X- решение задачи.

Х = tx1+(1-t)x2 0<=t<=1, согласно опр. Имеем выпуклое множество - Д, т.к. с любыми двумя точками ему принадлежит и их выпуклая Л.К.

Теорема № 2

Если целевая функция имеет максимум на выпуклом многограннике решений, то это максимум достигается в вершине многогранника..

Дано: Zmax->X0 Док-ть X0- вершина.

Zmax=C X0

Док-во: Дан многогранник. А,В,С,Д,Е - вершины. (Док-во проведем от противного)

X0 - не вершина , тогда согласно опр. Крайней точки , X0 - не крайняя точка , и может быть представлена в виде выпуклой Л.К. точек хi є ОДР

C X0>Cxi (т.к. С X0 ->max)

X0 = бiXi бi=1 бi>=0

Найдем значение функции

Z=C X0=CбiXi=бiCXi<бiCX0=CX0бi=CX0

В каждом слагаемом сменим Xi на Х0

СХ0<CX0 - противоречие.

Теорема №3

Об альтернативном оптимуме.

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

Дано : Док-ть: х= бiXi

Xi , i:=1,k бi=1 бi>=0 CX=d

Zmax=C{i=d

Док-во

Найдем

Z=СХ=CбiXi=бiCXi=бid=dбi=d

Теорема № 4

Вектор Х является опорным решением тогда и только тогда , если он является вершиной многогранника.

Если переменных n>3 то говорят гиперплоскость, положение точек в т - мерном пространстве.

Задания для самоконтроля

1. Основные определения

2. графический метод решения ЗЛП

Литература /1-4/

Лекция -4. Тема лекции: Нахождения решения ЗЛП. Симплекс-метод

Цель лекции: Рассмотрение метода решения ЗЛП.

Вопросы к теме:

1 Симплекс-метод

2 Правила заполнения Симплекс-таблицы

Тезисы лекции:

Симплекс метод является универсальным.

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

Находятся первоначальное, опорное решение. А)система ограничений должна быть записана в виде равенств (каноническая форма)

Б)Преобразовать что бы bi >=0 i=1,m

С)Привести систему к единичному базисному виду с неотрицательной правой частью.

Поэтому за разрешающий элемент выбирается строго положительный элемент.

Д)Приравниваем свободные к 0 , получаем первоначальное базисное неотрицательное решение, которое является опорным решением данной задачи и соответствует вершине.

Рассматривая функцию цели выясняем является ли полученное решение оптимальным.

Если полученное решение не является оптимальным , то необходимо перейти к следующей вершине (опорному решению) Переход осуществляется по определенному правилу по которому : только одна изи базисных переменных должна перейти в свободную и только одна из свободных перейти в базисную.

Алгебра симплекс метода.

Х1	Х2	Х3	Х4	Х5	св.чл
1	0	1	6	2	8
0	1	1	0	3	9
0	0	7	-1	-3	-0
1	-2/3	1/3	6	0	2
0	1/3	1/3	0	1	3
0	1	8	-1	0	9
1/6	-2/18	1/18	1	1/3
			0	1	-9
1/6	8/9	8 1/8	0	0	1/3

Особенность выделенная клетка.

Чтобы решать симплекс методом необходимо Z->min (перейти к min)

В строке Z записываются коэффициенты ф-ии цели, а свободный член записывается в выделенную клетку св.чл. с противоположным знаком.

Сделаем свободные члены неотрицательными.

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

Функция цели должна быть выражена только через свободные неизвестные , чтобы определить оптимален ли полученный опорный план. Для определения опорного плана свободные элементы =0 r=(7;-1;-3} Среди них выбираем самый отрицательный и делаем разрешающий столбец. Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца

Для выбора разрешающей строки находится min-ое из отношений свободных членов системы ограничений к положительным коэффициентам разрешающего столбца.

Альтернативный оптимум.

Предположим найдено оптимальное решение. r>=0. Признаком альтернативного оптимума в этом случаи является равенство 0, хотя бы одной из компонент вектора r. Покажем что если компонента rj =0 , для найденого оптимального плана (Х*1) то можно найти еще одно оптимальное решение Х*2 , значение в котором будет таким же как и значение в Х*1. Z(Х*2)= Z (Х*1)=Zmin

За разрешающий столбец берем rj =0 Zmin=Z(X*1)=-Q (свободный член в Z) Q1=aij*Q-bi*rj/aij = Q-(bi*rj/aij)=Q bi>0 aij>=0

Сделав шаг метода Гауса , получим новое решение , а значение функции в т Х*2 будет точно таким же как и в Х*2 - т.е. задача Альтернативного оптимума.

Монотонность и конечность алгоритма симплекс метода.

Покажем , что применяя алгоритм симплекс метода к З.Л.П. мы получим , что значение функции монотонно убывает. Предположим, что на кокаком то шаге симплекс метода выбран разрешающий столбец rj<0 , а за разрешающую строку выбрана i строка. Покажем что значение функции не возрастает , если мы применим один шаг симплекс метода. Qнов=aij*Q-bi*rj/aij= Q-bi-rj/aij<=0 (bi>=0 rj<0 aij>=0) Qнов>=Q -Qнов<=-Q

Так как многогранник имеет конечное число вершин , то алгоритм симплекс метода будет конечен.

Проблема выражденности.

Если получено в опорном плане число положительных координат меньше чем m , то решение является выражденным , и если полученный план не является оптимальным , т.е. возникает необходимость к новому опорному плану и при этом за разрешающую строку выбирается строка в которой bi=0 Тогда моежт быть проблема зацикливания, т.е. возврат к прежней вершине , для того чтобы избежать этого нужно «расклеить» точки для чего служит ипсилон метод. На ипсилон величину сдвигают прямые , таким образом чтобы раздвигаются вершины. Находят оптимальное решение новой задачи и учитывая ипсилон переходя к страой задаче.

Если в конце преобразований получена таблица , то столбец соответсвующем столбце нет ни одного положительного элемента то Zmin->- бесконечности ( нет решения)

Если в результате преобразований сстрока превратилась ( 0 0 0 0 = 7), то задача не имеет решения по причине не совместимости систем . Нет ОДР.

Если оптимальное решение и соответствующий ему вектор (r) имеет 0 координату то задача на альтернативный оптимум. Что бы найти второе решение берем за разрешающий столбец 0.

Задания для самоконтроля.

1. Применимость симплекс метода.

2. Формулы жордана-Гаусса.

3. правила заполнения симплекс таблицы.

Литература /1-4/

Лекция -5. Тема лекции: Метод искусственного базиса

Цель лекции: Знакомство с методом искусственного базиса.

Вопросы к теме:

1 Идея метода

2 Правила заполнения симплекс таблицы и нахождения оптимального плана

Тезисы лекции:

Z=CX->min В данной задаче нет естественного базиса. Введем в каждое ограничение

Ax=b искусственную переменную «у»>=0 Z преобразуем в T. М - полож. большое чис

X>=0 -Z задача.

Ах+у=b

Х>=0 у>=0

T=CX+M*y->min (М -задача)

Теорема . Если М задача имеет оптимальное решение , то Z - задача : а) тоже имеет решение , если все искусственные переменные = 0. Б) Z- задача не имеет решения если хотя бы одна из искусственных переменных не равна 0, систем ограничений будет не совместна. Если М задача не имеет решения ,т.е. Tmin ->-бесконечности , то и Z- задача тоже не имеет решения.

Задания для самоконтроля

1. Применимость метода.

2. Расширенная задача? Дополнительные переменные.

3. Оптимальность плана.

Литература /1-4/

Лекция -6. Тема лекции: Двойственные задачи линейного программирования

Цель лекции: Усвоение основных принципов построения двойственных задач

Вопросы к теме:

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

2 Связь между прямой и двойственной задачами.

Тезисы лекции:

ТЕОРИЯ ДВОЙСТВЕННОСТИ .

Каждой задаче Л.П. можно поставить в соответствие двойственную задачу , решения которой дает немедленное решение прямой задачи.

Стандартная форма.

Z=CX->max

Ax<=b

x>=0 1)

Двойственной задачей к данной З.Л.П. называется задача вида

w=yb->min

YA>=C

Y>=0 2)

Задача 1) и 2) называется пара двойственных задач.

Если по этим правилам построить двойственную задачу к 2) то получим 1) . И в этом смысле задачи называются взаимозаменяемыми или сопряженными.

(y- строка)

(y1,y2..ym) a11

a21

am1

Экономический смысл : Экономически двойственную и прямую задачу можно интерпретировать прямая на max прибыль. , при выпуске х1 х2 х3 , а двойственную min -> расходов на ресурсы.

b - сырье ; у1 у2 - оценка ресурсов.

Правило построения двойственных задач к общей З.Л.П.

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

Количество ограничений двойственной задачи равно числу переменных в прямой задачи.

Вектор свободных элементов прямой задачи b является вектором коэффициентов двойственной задачи.

Вектор коэффициентов функции цели C=(C1…Cn) прямой задачи служит вектором свободных членов системы ограничений двойственной задачи.

Если прямой Z->max то в Д.З. W->min/

Каждому ограничению - неравенству ai1x1+a12x2+..+ainxm , i=1,m Соответствует неотрицательная переменная yi>=0 ; i=1,m Д.З.

Каждой неотрицательной переменной (xj>=0) j=1,n прямой задачи соответствует ограничения неравенства Д.З. a1jy1+a2jy2+…+amjym>=Cj (j=1,n)

Матрица системы ограничений Д.З. служит транспонированная матрица прямой задачи.

Каждом ограничению равенству прямой задачи ai1x1+ai2x2+…+ainxn=bi (i=1,m) соответствует свободная переменная yi><0

Каждой свободной переменной xj><0 (j=1,n) соответствует ограничение равенства a1j+a2j+…+amjym=Cj

ТЕОРЕМА ДВОЙСТВЕННОСТИ.

1. Если прямая и двойственная задача имеют допустимые решения Х и У , то они имеют оптимальное решение Х* и У* и причем значение функции в этих точках совпадают. Zmax=Wmin CX*=Y*b

Лемма №1

Для любых двух допустимых решений Х и У пары Д.З. справедливо СХ<=Уb

Док-во:

Z=CX->max W=yb->min

Ax<=b YA>=C

x>=0 y>=0

Допустим что X1 - любое допустимое решение П.З. , а Y1 - для Д.З.

Тогда Х1 удовлетворяет системе ограничений , т.е. АХ1<=b ¦ y1>=0 Y1A>=C¦x1>=0

Первое ограничение умножим на y1

Y1Ax1<=y1b

Y1Ax1>=Cx1

Cx1<=T<=y1b => Cx1<=y1b

Лемма № 2

Если для допустимых решений X* и У * , выполняется условие равенства СХ* =У*b , то Х* и У* являются оптимальными решениями пары двойственных задач.

Док-во : Дана пара Д.З. Х* и У* допустимые решения. СХ*=У*b , док-ть Х* и У* оптим. решение

Предположим что Х- ОДР (любое) , тогда по первой лемме СХ<=У*b , но У*b=Cx* => Cx=Cx* отсюда следует , что Х* т. максимума => у* т. минимума.

На основании графического анализа Д.З. исследовать разрешимость данной задачи в случаи разрешимости - найти экстремальные значение целевой функции.

1 часть теоремы.

Если одна из задач не разрешима из-за не ограниченности функции , то и вторая задача не имеет решения по причине не совместимости систем ограничений.

Док-во :

Согласно первой лемме СХ<=уb , если прямая задача не имеет решения zmax->бесконечности , то, очевидно, что нет такого допустимого решения (у) в котором значение функции было бы больше бесконечности.

ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ И СВОЙСТВА ДВОЙСТВЕННЫХ ОЦЕНОК.

Z=CX->max W=yb->min

Ax>=b ¦ y1 A- матрица коэффициентов

x>=0 ¦ y>=0 y1>=c

теорема : Для того что бы допустимое решение Х* и У* пары двойственных задач были оптимальными , необходимо и достаточно , что бы для них выполнялись условия «дополнительное не жесткости»

Z=Cx->max W=yb->min

Ax<=b ¦y YA>=C ¦x

x>=0 y>=0

Y*(Ax*-b)=0 (тогда оптимальное решение)

(У*А-С)Х*=0

необходимость :

Х* У* - оптимальное решение.

Док-ть: 1 и 2

Док-во: т.к. Х* является оптимальным решением , то и я является допустимым решением => Ах*<=b¦y*>=0 Y*Ax*<=y*b; y* в ходит ОДР => Y*A>=C¦x*>=0 y*Ax*>=Cx* =>

Cx*<=Y*Ax*<=y*b, т.к. х* и у* - оптимальное решение , то Сх*=уb* , по первой теореме => Сх*=у*Ах*=у*b. Ч.т.д

(С-у*А)х*=0

2) (у*А-С)х*=0

1) у*(Ах*-b)=0

достаточность

Дано

1) 2)

Док-ть

Х* и У* - оптим. решение.

Док-во: у*Ах*-у*b=0

Y*Ax*=y*b

y*Ax*-Cx=0

yAx*=Cx*

Cx*=T=y*b=> Cx*=y*b

Вывод для практики : Если в оптимальном решении исходной задачи х*j ><0 , то соответствующее ограничение Д.З. превращается в оптимальное решение равенства. Если какое либо из ограничений исходной задачи в оптимальном решении превращается в строгое не равенство , то соответствующая переменная Д.З=0

Свойства двойственных оценок.

В экономике вектор у, называется вектором двойственных оценок или «теневыми ценами». Двойственные оценки сырья и т.д.

Свойства:

y*i - является покупателем дефицитности i-го ресурса (i=1,m) Оценка не дефицитного ресурса -0 (y*=0) , если аijxj<bi Чем выше yi (оценка ресурса), тем ресурс дефицитнее.

Y*i=dzmax/dbi y*i=lim ^Zmax/^bi (bi->0) => y*i?^Zmax/^bi => Zmax=y*i*^bi

Вектор y*i - является показателем необходимости введения в производство j- технологии Х*j(aijy*i-Cj)=0 , если aijy*i>Cj, то выгодно (Cj- цена ед. продукции) =>Х*j=0 , то не надо выпускать продукцию Х*j>0 , то затраты совпадают с доходами .

Вектор У является показателем сопоставимости затрат на ресурсы (у*1b1+y*2b2..) со стоимостью продукции.

Задания для самоконтроля

1. Что представляет собой двойственная задача?

2. Чем характеризуется связь между прямой и двойственной задачами?

Литература /1-4/

Лекция -7. Тема лекции: Двойственный симплекс-метод

Цель лекции: Освоение двойственного симплекс-метода

Вопросы к теме:

1 Группы задач, решаемых двойственным симплекс методом.

2 Идея двойственного симплекс метода.

Тезисы лекции:

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

Размещено на http://www.allbest.ru/

Обе двойственные задачи линейного программирования обладают следующими свойствами:

1) в одной задаче ищут максимум целевой функции, в другой ? минимум;

2) обе задачи являются стандартными задачами линейного программирования, причем в задаче о максимуме все неравенства вида "?", а в задаче о минимуме ? вида "?" ;

3) матрица системы ограничений одной задачи является транспонированной к матрице системы ограничений другой;

4) коэффициенты при переменных целевой функции одной задачи являются свободными членами ограничений другой;

5) число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче;

6) условия неотрицательности имеются в обеих задачах.

Свойствами двойственных задач следует руководствоваться при их составлении.

Задания для самоконтроля.

1. Сущность двойственного симплекс метода

2. Определение оптимального плана прямой и двойственной задач.

Литература /1-4/

Специальные задачи математического программирования

Глоссарий

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

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

Динамическое программирование - раздел математического программирования? Занимающийся рассмотрением и решением многоэтапных задач.

Лекция -8. Тема лекции: Целочисленное программирование

Цель лекции: Знакомство с методами решения целочисленных задач.

Вопросы к теме:

1 Задачи целочисленного программирования

2 Метод Гомори.

Тезисы лекции:

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

Задания для самоконтроля

1. Целочисленные задачи

2. Методы решения целочисленных задач.

Литература /1-4/

Лекция -9,10. Тема лекции: Динамическое программирование

Цель лекции: Знакомство с задачами динамического программирования.

Вопросы к теме:

1 Динамическое программирование

2 Принцип оптимальности Беллмана.

Тезисы лекции:

Задания для самоконтроля

1. Понятие динамического программирования.

2. Принцип Беллмана

Литература /1-4/

Лекция - 11. Тема лекции: Экономические задачи, решаемые методом динамического программирования

Цель лекции: Усвоение технологии решения задач динамического программирования

Вопросы к теме:

1 Задача о загрузке самолета

2 Задача об инвестициях.

3 Задача о замене оборудования.

Тезисы лекции:



Задания для самоконтроля

1. Методы решения многоэтапных задач.

2. Построение рекурентных соотношений

Литература /1-4/

Размещено на Allbest.ru