Разделы презентаций


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

Содержание

Excel: Поиск решенияMathcad: блок Given и функции нахождения оптимумаИнструменты решения задач ЛПMatlab: функция linprog

Слайды и текст этой презентации

Слайд 1Задачи линейного программирования и их решение в современных вычислительных средах


Лекция №12. Продолжение

Задачи линейного программирования и их решение в современных вычислительных средах Лекция №12. Продолжение

Слайд 2Excel: Поиск решения
Mathcad: блок Given и функции нахождения оптимума
Инструменты решения

задач ЛП
Matlab: функция linprog

Excel: Поиск решенияMathcad: блок Given и функции нахождения оптимумаИнструменты решения задач ЛПMatlab: функция linprog

Слайд 3Решение задачи ЛП в средах Matlab и Mathcad
Для решения задачи

ЛП в средах Matlab и Mathcad целевую функцию и ограничения

удобнее записать в матричном виде.
Далее мы рассмотрим запись в матричном виде для двух типов задач ЛП.
Решение задачи ЛП в средах Matlab и MathcadДля решения задачи ЛП в средах Matlab и Mathcad целевую

Слайд 4Целевая функция задачи ЛП
:
.
C=С(x1, x2, …, xn)=c1x1+c2x2+….+cnxn

Или:
n – число

переменных модели.

ЦФ в векторном виде:
C=C(x)=cтx,
где т – транспонирование,

- матричное произведение.
Или:
C= C(x)= cx,
где  - скалярное произведение векторов
Целевая функция задачи ЛП: .C=С(x1, x2, …, xn)=c1x1+c2x2+….+cnxnИли:n – число переменных модели.ЦФ в векторном виде:C=C(x)=cтx, где т

Слайд 5Пример 1. Стандартная (нормальная) форма задачи ЛП
1. ЦФ =>

максимум.
Ограничения–линейные неравенства (≤) + условие положительности всех переменных:
Или в сокращенной

записи:

i=1, 2, …, m,
J=1, 2, …, n.

Пример 1. Стандартная (нормальная) форма задачи ЛП 1. ЦФ => максимум.Ограничения–линейные неравенства (≤) + условие положительности всех

Слайд 6Ограничения стандартной формы задачи ЛП в матричном виде
Обозначим:

Ограничения стандартной формы задачи ЛП в матричном видеОбозначим:

Слайд 7Пример 2. Транспортная задача 
На n станциях отправления  A1, …, An

имеется, соответственно, a1, …,  an  единиц некоторого груза. Этот груз

следует доставить в m пунктов назначения  B1, …, Bm,  и в каждый из них должно быть завезено, соответственно, b1,  …, bm единиц этого груза. Стоимость перевозки одной единицы груза из пункта  Ai  в пункт  Bk  равна  ci,k. Составить такой план перевозок, чтобы суммарная стоимость перевозок была минимальной.
Считать, что количество всего груза на двух пунктах отправления равно потребности в грузе на всех трех пунктах назначения, то есть:
a1  + … + an = b1 +  … + bm.

Пример 2. Транспортная задача На n станциях отправления  A1, …, An имеется, соответственно, a1, …,  an  единиц некоторого

Слайд 8Пример 2. Транспортная задача 
Расположим исходные данные этой задачи в виде

таблицы:

Пример 2. Транспортная задача Расположим исходные данные этой задачи в виде таблицы:

Слайд 9Пример 2. Транспортная задача 
Обозначим: xi,k – количество перевезенного груза из

пункта Ai в пункт Bk . Тогда ЦФ (которую нужно

минимизировать) равна:

Ограничения:

Пример 2. Транспортная задача Обозначим: xi,k – количество перевезенного груза из пункта Ai в пункт Bk . Тогда

Слайд 10Запись ограничений транспортной задачи в матричном виде
Пусть t – вектор-столбец

из единиц длины n,
q

– вектор-столбец из единиц длины m. Тогда ограничения имею вид:
Xq=a
tт X=b
X≥0

Обозначим:

Запись ограничений транспортной задачи в матричном видеПусть t – вектор-столбец из единиц длины n,

Слайд 11Решение задачи ЛП (на примере стандартной формы) в среде Mathcad
Задание

параметров задачи – присваиванием или вводом:
Задание начального приближения: x:=0.
Запись ЦФ:

C(x):= cx
Given
Ограничения: Ax≤b
x≥0
Result:=Maximize(C,x) оптимальное решение задачи ЛП

См. https://gigabaza.ru/doc/80570.html и ЛР11.
Решение задачи ЛП (на примере стандартной формы) в среде MathcadЗадание параметров задачи – присваиванием или вводом:Задание начального

Слайд 12Ограничение целочисленности х в среде Mathcad
Для некоторых версий MathCAD существует

пакет расширения SOEP (Solving and Optimization Extension Pack), в котором

имеется возможность уточнить тип результата - просто в завершающих функциях блока Given последним параметром ставится строка, указывающая тип переменной в системе уравнений. Местоположение целой переменной обозначается I, бинарной - В, и т.д.:
f(x1,x2)=5*x2-3*x1 Given 2x1+3x2≤5 x1≥0 x2≥0 Minimize (f,x1,x2,"II")

В базовой комплектации MathCAD нет инструментов для установления целочисленных ограничений.
НО можно самостоятельно разработать такой алгоритм!
См., например, http://blog.kislenko.net/show.php?id=974
Ограничение целочисленности х в среде MathcadДля некоторых версий MathCAD существует пакет расширения SOEP (Solving and Optimization Extension

Слайд 13Решение задачи ЛП в среде Matlab – функция linprog
x = linprog(C,A,b) решает

min cтx таким образом,
что Ax ≤ b.

x = linprog(C,A,b,Aeq,beq) включает ограничения
равенства   Aeqx = beq. Установите   A =

[] и   b = [] если
никакие неравенства не существуют.

x = linprog(f,A,b,Aeq,beq,lb,ub) задает набор нижних
и верхних границ на переменных проекта, x, так, чтобы
решением всегда был в области значений     lb ≤ x ≤ ub.
Установите   Aeq = [] и   beq = [] если никакие равенства
не существуют.

Функция linprog принадлежит пакету Optimization Toolbox, который требует дополнительной установки.
Решение задачи ЛП в среде Matlab – функция linprogx = linprog(C,A,b) решает min cтx таким образом, что Ax ≤ b.x = linprog(C,A,b,Aeq,beq) включает ограничения равенства   Aeqx =

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика