Решить задачу линейного программирования семестр

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

В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).

Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x₁ ≤ 4 , то оно разбивается на два: x₁ ≥ 1 , x₁ ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса.

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.

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

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

Особенности решения задач линейного программирования графическим методом

Переменную x₂ принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x₁ + 6x₃+ 27
x₁ + 3x₃≥6

Далее задача решается графическом способом.

Пример №2
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

• Составить систему математических зависимостей (неравенств) и целевую функцию.
• Изобразить геометрическую интерпретацию задачи.
• Найти оптимальное решение.
• Провести аналитическую проверку.
• Определить существенные и несущественные ресурсы и их избытки.
• Определить значение целевой функции.
• Вычислить объективно обусловленные оценки.
• Составить соотношение устойчивости.

Источник

Линейное программирование. Решение задач

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

Линейное программирование. Решение задач графическим способом

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

1. Метод искусственного базиса
2. Задача оптимального производства продукции
3. Пример решения симлекс-методом
   Решить следующую задачу ЛП в неканонической форме симплекс-методом:
   f(x) = x₁ – x₂ – 3x₃ → min
4. М-метод. Решить задачу М-задачу.
5. Пример нахождения максимума функции симплексным методом
6. Пример нахождения минимума функции симплексным методом
7. Пример решения модифицированным симплекс-методом
8. Пример решения симплекс-методом в столбцовой форме записи
9. Симплекс-метод в строчечной форме записи. Пример решения
10. Пример решения задачи симплексным методом в Excel
11. Линейное программирование в Excel

Решение двойственной задачи линейного программирования

1. Двойственная задача ЛП
   Необходимо выполнить в указанном порядке следующие задания.
   1. Найти оптимальный план прямой задачи:
   а) графическим методом;
   б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
   2. Построить двойственную задачу.
   3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
2. Двойственная задача в Excel
3. Оценка целесообразности выпуска новой продукции

Двойственный симплекс-метод

Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин. Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов (алгоритм), логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика, совмещаются с логически обоснованным пониманием сущности изучаемого явления. Методом линейного программирования решается транспортная задача, т.е. задача рационального прикрепления предприятий-потребителей к предприятиям-производителям.

Источник

Метод ветвей и границ

Инструкция . Укажите количество переменных и число ограничений. Полученное решение сохраняется в формате MS Word с проверкой решения в MS Excel . При этом ограничения типа x_i ≥ 0 не учитывайте.

Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. При использовании метода ветвей и границ область допустимых решений (ОДР) исходной задачи определенным способом разбивается на непересекающиеся подмножества, и решаются подзадачи, т.е. задачи на этих подмножествах с той же ЦФ и без учета условия целочисленности (как задачи ЛП). Если в результате получено оптимальное нецелочисленное решение, ОДР подзадачи снова разбивается на части и этот процесс продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение исходной задачи.
Если в задаче на максимум при решении подзадач получаются оптимальные целочисленные решения, то запоминаются те из них, которым соответствуют возрастающие значения ЦФ. Если полученное «непрерывное» решение подзадачи оказывается не лучше сохраненного целочисленного решения, то такая подзадача исключается из списка задач. Название этого метода объясняется тем, что в процессе решения задача последовательно «ветвится», разбиваясь на более простые подзадачи.

Примечание: метод ветвей и границ используется также и в задаче коммивояжера.

Пример №1 . В задаче методом Гомори (или методом ветвей и границ) найти оптимальные решения задач целочисленного линейного программирования. Дать геометрическую интерпретацию процесса решений задач.
Z=3x₁ + 2x₂ → max
при ограничениях:
x₁ + x₂ ≤ 13
x₁ — x₂ ≤ 6
-3x₁ + x₂ ≤ 9
x₁≥0, x₂ ≥0
x₁, x₂ – целые числа.

Пример №2 .
5x₁ + 2x₂ ≤ 14
2x₁ + 5x₂ ≤ 16
x₁ , x₂ – целые числа
Z = 3x₁ + 5x₂ → max
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Оптимальное значение переменной x₁=1.81 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х₁ ≥ 2, а к задаче 12 — условие х₁ ≤ 1.
Эта процедура называется ветвлением по переменной х₁.
Решим графически задачу 11 как задачу ЛП.
5x₁+2x₂≤14 (1)
2x₁+5x₂≤16 (2)
x₁≥2 (3)
x₁≥0 (4)
x₂≥0 (5)

Область допустимых решений представляет собой треугольник.
Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x₁+2x₂≤14
x₁≥2

Решив систему уравнений, получим: x₁ = 2, x₂ = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи — текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*.

Область допустимых решений представляет собой многоугольник
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
2x₁+5x₂≤16
x₁≤1

Решив систему уравнений, получим: x₁ = 1, x₂ = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17

Оптимальное значение переменной x₂=2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х₂ ≥ 3, а к задаче 122 — условие х₂ ≤ 2.

Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₁=0.5 оказалось нецелочисленным.
Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х₁ ≥ 1, а к задаче 1212 — условие х₁ = 0.

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₂=2.48 оказалось нецелочисленным. Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х₂ ≥ 3, а к задаче 12 — условие х₂ ≤ 2.
Эта процедура называется ветвлением по переменной х₂.

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x₁=0.5 оказалось нецелочисленным. Разбиваем задачу 11 на две подзадачи 111 и 112. В первой из них к условиям задачи 111 добавляется условие х₁ ≥ 1, а к задаче 112 — условие х₁ = 0.

Решим графически задачу 111 как задачу ЛП.
5x₁+2x₂≤14 (1)
2x₁+5x₂≤16 (2)
x₂≥3 (3)
x₁≥1 (4)
x₁≥0 (5)
x₂≥0 (6) Задача не имеет допустимых решений. ОДР представляет собой пустое множество

Источник