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

Линейное программирование. Теория

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

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

1. Формулировка основных типов задач ЛП, построение их математических моделей
2. Каноническая форма задач линейного программирования
3. Симплексный метод решения задач линейного программирования
4. Поиск первоначального опорного плана
5. Виды записи симплекс-метода
6. Двухфазный симплекс-метод
7. Матричное описание симплекс-метода
8. M-задача
9. Симплекс-метод с естественным базисом
10. Дробно-линейное программирование
11. Построение математической модели для симплекс-задачи

Двойственность в задачах линейного программирования

1. Теоремы двойственности. Двойственность в задачах линейного программирования
2. Экономическая интерпретация двойственной задачи и теории двойственности (Анализ решения задачи линейного программирования с помощью теории двойственности)
3. Симметричные двойственные задачи
4. Несимметричные двойственные задачи

Целочисленное программирование

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

Список рекомендуемой литературы

1. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. Учебное пособие. – М.,Финансы и статистика, 2005
2. Беспалов М.С. Линейное программирование. Владимир: ВлГУ. 1999
3. Галкин А.А. Математическая экономика. Владимир: ВлГУ. 2006
4. Глухов В.В.Математические методы и модели для менеджмента: учебное пособие. – СПБ;М.;Краснодар:Лань,2005
5. Грицюк С.Н.Математические методы и модели в экономике: учебник.- Ростов н/Д:Феникс, 2007
6. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник. – М.,Изд-во «Дело и сервис», 2004.
7. Исследование операций в экономике. Учебное пособие для вузов/Под ред. проф.Н.Ш.Кремера. – М., ЮНИТИ, 2005.
8. Кузнецов Б.Т. Математические методы и модели исследования операций: учебное пособие. М.:ЮНИТИ – ДАНА, 2005
9. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа. 1980.
10. Кундышева Е.С. Математическое моделирование в экономике: Учебное пособие. – М., Издательско-торговая корпорация «Дашков и Ко», 2004.
11. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учеб.- М.:Дело, 2001
12. Орехов А.М. Методы экономических исследований: учебное пособие. – М:ИНФРА – М, 2006
13. Орлова А.М. Экономико-математическое моделирование: практическое пособие по решению задач – М.: Вузовский учебник, 2007
14. Просветов Г.И.Математические методы в экономике: учебно-методическое пособие. М, Изд-во РДЛ, 2007
15. Справочник по математике для экономистов. Под ред. В.И. Ермакова. М.: Высшая школа. 1987.
16. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. — М.: Финансы и статистика, 2005.
17. Шевченко В.Н., Золотых Н.Ю. Линейное и целочисленное линейное программирования. — Нижний Новгород: Изд-во Нижегородского государственного университета им. Н.И. Лобачевского, 2004. — 154 с.
18. Экономико-математическое моделирование: учебник / ред.И.Н. Дрогобыцкий. М.:Экзамен, 2006
19. Экономико-математические методы и модели:учебное пособие / под ред. С.И.Макарова. – М.:КНОРУС, 2007

Источник

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

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу.

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

• Шаг №1
• Шаг №2
• Видеоинструкция
• Оформление Word

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x₁, …, x_m, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x_m+1,…, x_n) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных x_j≥0, что эквивалентно условию неотрицательности b_j≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел b_j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x₁ + 2x₂ — 2x₃ → min при ограничениях:
4x₁ + 3x₂ — x₃≤10
— 2x₂ + 5x₃≥3
x₁ + 2x₃=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x₄; во втором неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.
4x₁ + 3x₂-1x₃ + 1x₄ + 0x₅ = 10
0x₁-2x₂ + 5x₃ + 0x₄-1x₅ = 3
1x₁ + 0x₂ + 2x₃ + 0x₄ + 0x₅ = 9
F(X) = — x₁ — 2x₂ + 2x₃
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₄.
2. В качестве базовой переменной выбираем x₂.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x₂, получена в результате деления всех элементов строки x₂ на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 • 3):-2	3-(-2 • 3):-2	-1-(5 • 3):-2	1-(0 • 3):-2	0-(-1 • 3):-2	10-(3 • 3):-2
0 : -2	-2 : -2	5 : -2	0 : -2	-1 : -2	3 : -2
1-(0 • 0):-2	0-(-2 • 0):-2	2-(5 • 0):-2	0-(0 • 0):-2	0-(-1 • 0):-2	9-(3 • 0):-2

Получаем новую матрицу:

4	0	6 1 /2	1	-1 1 /2	14 1 /2
0	1	-2 1 /2	0	1 /2	-1 1 /2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x₃.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x₃, получена в результате деления всех элементов строки x₃ на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₃ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 • 6 1 /2):2	0-(0 • 6 1 /2):2	6 1 /2-(2 • 6 1 /2):2	1-(0 • 6 1 /2):2	-1 1 /2-(0 • 6 1 /2):2	14 1 /2-(9 • 6 1 /2):2
0-(1 • -2 1 /2):2	1-(0 • -2 1 /2):2	-2 1 /2-(2 • -2 1 /2):2	0-(0 • -2 1 /2):2	1 /2-(0 • -2 1 /2):2	-1 1 /2-(9 • -2 1 /2):2
1 : 2	0 : 2	2 : 2	0 : 2	0 : 2	9 : 2

Получаем новую матрицу:

3 /4	0	0	1	-1 1 /2	-14 3 /4
1 1 /4	1	0	0	1 /2	9 3 /4
1 /2	0	1	0	0	4 1 /2

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

Источник