Детерминированные линейные модели с непрерывными переменными презентация

Часть 1
Общая постановка задач и алгоритм их решения

Формальная постановка задачи

Линейное программирование
Дж. Данциг.
Целевая функция
Симплекс

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

Пример 1
Определить оптимальное решение задачи:
где: хi – непрерывная неотрицательная переменная;
Решение – симплекс методом.

Выделение базисных переменных.
Пусть в качестве базисных (не равных нулю) переменных выбраны х1 и х5:
x1 = 8 + x2 – 5x3 + x4 – x5. Отсюда: 5х1 = 40 + 5х2 – 25х3 + 5х4 – 5х5 (2)
Подставляя (2) в первое равенство системы (1), получим:
40 + 5х2 – 25х3 + 5х4 – 5х5 – 4х2 + 13х3 – 2х4 + х5 = 20.
Отсюда следует:
х2 – 12х3 + 3х4 – 4х5 + 20 = 0.
Окончательное равенство, включающее х5, имеет вид:
Подставляя (3) в выражение для х1, получим:
После подстановки х1 и х5 в целевую функцию, получим:

Эквивалентная каноническая форма задачи (1)
х1 и х5 – базисные переменные.
Базисное решение: х1=3; x5=5; x2=x3=x4=0.
Значение целевой функции = 28.

Переход к новому базису
Т.к. коэффициент при х3 в целевой функции отрицателен, то увеличение х3 вызовет уменьшение функционала цели.
Т.о. введению в базис подлежит х3. Теперь следует выбрать переменную, выводимую из базиса:
х1 = 3 – 2х3 из равенства (4)
х5 = 5- 3х3 из равенства (5)
Если :
то х5 станет <0, что недопустимо.
то х1 станет <0, что недопустимо.
из базиса выводится х1.
Новый базис имеет вид:
х3 = 1,5; x5 = 0,5; x1=x2=x4=0; f(x) = -8
Значение целевой функции уменьшилось с 28 до –8.
Новая система имеет вид:
где х3 и х5 – базисные переменные.

Переход к новому базису
Т.к. коэффициент при х2 в целевой функции отрицателен, в базис вводится х2. Для того, чтобы определить, какая переменная выводится из базиса, проанализируем выражения, получаемые из 1-го и 2-го равенств:

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

Настройка пакета Simplexwin 3.1 –ввод числа переменных и ограничений

Ввод исходных данных в пакет Simplexwin 3.1

Вывод результатов пакетом Simplexwin 3.1

Достоинства и недостатки симплекс-метода
1. Достоинства:
Гарантия глобально оптимального решения.
Высокое быстродействие независимо от размерности.
Наличие большого числа программных реализаций.
2. Недостатки:
Решаются только линейные задачи с непрерывными неотрицательными переменными.

Самостоятельно
Решить задачу симплекс-методом, добавив переменные:
S=5x₁+8x₂+3x₃ max;
2x₁+3x₂+4x₃ ≤ 12;
x₁≥0; x₂ ≥0; x₃ ≥0.

Часть 2
Важный частный случай: задача с одним ограничением

Задача с одним видом ресурса
Требуется определить вектор переменных Х, который бы максимизировал финансовые поступления на предприятие:
(1)
где: хi – объем выпускаемой продукции i-го вида (непрерывная неотрицательная переменная); сi – стоимость единицы выпускаемой продукции i-го вида; b – величина имеющегося ресурса (например, человекочасы); аi, – затраты единственного вида ресурса, приходящиеся на единицу i-го вида продукции.

Алгоритм поиска решения задачи (1)
Ганс Христиан Андерсен
Блок-схема алгоритма
Начало, S=0.
Ввод n, b, ci, ai, i=1,2,…n
Все наряд-заказы ранжируются таким образом, что:
j=1
Печать S и
Конец алгоритма
1
2
3
4
6
7
8
9

Достоинства и недостатки алгоритма
1. Достоинства:
Гарантия глобально оптимального решения.
Простота реализации.
Высокое быстродействие.
Низкие требования к ресурсам компьютера.
2. Недостаток:
Узкий диапазон применения.

Пример 2
Решить самостоятельно, пользуясь приведенным выше алгоритмом и симплекс методом:
S=5x₁+9x₂+3x₃ max;
2x₁+3x₂+4x₃ ≤ 12;
x₁≥0; x₂ ≥0; x₃ ≥0.
Ответ: x₁=0; x₂ =4; x₃ =0, Smax=36.

Задача с одним видом ресурса и ограничениями на выпуск каждого вида продукции
Требуется определить вектор переменных Х, который бы максимизировал финансовые поступления на предприятие:
где: хi – объем выпускаемой продукции i-го вида (непрерывная неотрицательная переменная); сi – стоимость единицы выпускаемой продукции i-го вида; b – величина имеющегося ресурса (например, человекочасы); аi, – затраты единственного вида ресурса, приходящиеся на единицу i-го вида продукции, di - верхняя граница выпуска i-го вида продукции.

Алгоритм поиска решения задачи (2)
Начало, S=0.
Ввод n, b, ci, ai, i=1,2,…n
Все наряд-заказы ранжируются таким образом, что:
j=1
b=0
Нет
Конец алгоритма
Да
1
2
3
4
5
6
7
8
9

Пример 3
Решить самостоятельно, пользуясь приведенным выше алгоритмом и симплекс методом:
S=5x₁+9x₂+3x₃ max;
2x₁+3x₂+4x₃ ≤ 12;
4≥x₁≥0; 2≥x₂ ≥0; 3≥x₃ ≥0.
Ответ: x₁=3; x₂ =2; x₃=0; S=33.

Графическая интерпретация задач линейного программирования
Аналитическая Графическая
форма интерпретация
-x1+x2=1
x1+x2=2
x1-2x2=1
Область допустимых решений ограничена.

Достоинства и недостатки алгоритма
1. Достоинства:
Гарантия глобально оптимального решения.
Простота реализации.
Высокое быстродействие.
Низкие требования к ресурсам компьютера.
2. Недостаток:
Узкий диапазон применения.

Графическая интерпретация задач линейного программирования - область допустимых решений не ограничена
Формальная Графическая
постановка интерпретация

Задачи ЛП на графах
Задача о максимальном потоке: На графе G(X,U), множество вершин которого X, а множество дуг U, определить максимальный поток из вершины – источника в вершину – сток, если поток f (i,j) по дуге не может превысить пропускной способности дуги r(i,j).

Графическое представление задачи о максимальном потоке.

Задача о максимальной циркуляции на взвешенном орграфе
Содержательная постановка задачи: на взвешенном орграфе с бикомпонентами требуется распределить замкнутые потоки (циркуляции) в контурах таким образом, чтобы:
Их сумма в одной и той же дуге не превышала пропускной способности этой дуги.
Суммарный вес всех циркуляций должен быть максимальным.

Формальная постановка задачи о максимальной циркуляции
Здесь s(аi ) - циркуляция в i-о контуре; r(p,q) – пропускная способность дуги (p,q) множества U;
A(p,q) – подмножество контуров, которым принадлежит дуга (p,q).

Графовая иллюстрация
1
3
4
2
2 4 3 5
7
9
a1= 1-3-1; a2= 1-2-4-3-1;
a3= 2-4-2.

Решение задачи программой поиска максимальных циркуляций на планарных графах

Прямые и двойственные задачи
Прямая задача

Двойственная задача

Графическое решение двойственной задачи