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

Август 22, 2022

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

Содержание

2. Excel: Поиск решения Mathcad: блок Given и функции нахождения оптимума Инструменты решения задач ЛП Matlab: функция
3. Решение задачи ЛП в средах Matlab и Mathcad Для решения задачи ЛП в средах Matlab и
4. Целевая функция задачи ЛП : . C=С(x1, x2, …, xn)=c1x1+c2x2+….+cnxn Или: n – число переменных модели.
5. Пример 1. Стандартная (нормальная) форма задачи ЛП 1. ЦФ => максимум. Ограничения–линейные неравенства (≤) + условие
6. Ограничения стандартной формы задачи ЛП в матричном виде Обозначим:
7. Пример 2. Транспортная задача На n станциях отправления A1, …, An имеется, соответственно, a1, …, an
8. Пример 2. Транспортная задача Расположим исходные данные этой задачи в виде таблицы:
9. Пример 2. Транспортная задача Обозначим: xi,k – количество перевезенного груза из пункта Ai в пункт Bk
10. Запись ограничений транспортной задачи в матричном виде Пусть t – вектор-столбец из единиц длины n, q
11. Решение ⋅задачи ЛП (на примере стандартной формы) в среде Mathcad Задание параметров задачи – присваиванием или
12. Ограничение целочисленности х в среде Mathcad Для некоторых версий MathCAD существует пакет расширения SOEP (Solving and
14. Скачать презентацию

Слайд 2

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

ЛП

Matlab: функция linprog

Слайд 3

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

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

Слайд 4

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

модели.
ЦФ в векторном виде:
C=C(x)=cт ⋅x,
где т – транспонирование,
⋅ - матричное произведение.
Или:
C= C(x)= c ⋅x,
где ⋅ - скалярное произведение векторов

Слайд 5

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

неравенства (≤) + условие положительности всех переменных:

Или в сокращенной записи:

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

Слайд 6

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

Слайд 7

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

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

Слайд 8

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

Слайд 9

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

Ai в пункт Bk . Тогда ЦФ (которую нужно минимизировать) равна:

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

Слайд 10

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

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

Обозначим:

Слайд 11

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

задачи – присваиванием или вводом:

Задание начального приближения: x:=0.
Запись ЦФ: C(x):= c ⋅x
Given
Ограничения: Ax≤b
x≥0
Result:=Maximize(C,x) оптимальное решение задачи ЛП
См. https://gigabaza.ru/doc/80570.html и ЛР11.

Слайд 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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

Похожие презентации