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

Задачи линейного программирования и их решение в современных вычислительных средах
Задачи линейного программирования и их решение в современных вычислительных
Решение задачи ЛП в средах Matlab и Mathcad
Целевая функция задачи ЛП
Задачи линейного программирования и их решение в современных вычислительных
Ограничения стандартной формы задачи ЛП в матричном виде
Пример 2. Транспортная задача
Пример 2. Транспортная задача
Пример 2. Транспортная задача
Запись ограничений транспортной задачи в матричном виде
Решение  задачи ЛП ( на примере стандартной формы) в среде Mathcad
Ограничение целочисленности х в среде Mathcad
Решение задачи ЛП в среде Matlab – функция linprog
1/13
Средняя оценка: 4.6/5 (всего оценок: 18)
Код скопирован в буфер обмена
Скачать (102 Кб)
1

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

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

Изображение слайда
2

Слайд 2

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

Изображение слайда
3

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

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

Изображение слайда
4

Слайд 4: Целевая функция задачи ЛП

: . C= С ( x 1, x 2, …, x n )= c 1 x 1 + c 2 x 2 +….+ c n x n Или: n – число переменных модели. ЦФ в векторном виде: C = C ( x )= c т  x, где т – транспонирование,  - матричное произведение. Или: C = C ( x )= c   x, где  - скалярное произведение векторов

Изображение слайда
5

Слайд 5

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

Изображение слайда
6

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

Обозначим: Тогда ограничения в матричном виде запишутся так: Ax ≤ b x ≥0

Изображение слайда
7

Слайд 7: Пример 2. Транспортная задача

На n станциях отправления  A 1, …, A n имеется, соответственно, a 1, …,   a n  единиц некоторого груза. Этот груз следует доставить в m пунктов назначения  B 1,  …,  B m,  и в каждый из них должно быть завезено, соответственно, b 1,   …, b m единиц этого груза. Стоимость перевозки одной единицы груза из пункта  A i  в пункт  B k  равна  c i,k. Составить такой план перевозок, чтобы суммарная стоимость перевозок была минимальной. Считать, что количество всего груза на двух пунктах отправления равно потребности в грузе на всех трех пунктах назначения, то есть: a 1   + …   + a n = b 1 +   … + b m.

Изображение слайда
8

Слайд 8: Пример 2. Транспортная задача

Расположим исходные данные этой задачи в виде таблицы: Пункт отправления Пункт назначения Запас груза B 1 … B m A 1 с 1, 1 … с 1, m a 1 … … … … … A n с n,1 … с n, m a n Потребность в грузе b 1 … b m

Изображение слайда
9

Слайд 9: Пример 2. Транспортная задача

Обозначим: x i, k – количество перевезенного груза из пункта A i в пункт B k. Тогда ЦФ (которую нужно минимизировать) равна: Ограничения:

Изображение слайда
10

Слайд 10: Запись ограничений транспортной задачи в матричном виде

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

Изображение слайда
11

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

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

Изображение слайда
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, который требует дополнительной установки.

Изображение слайда