Решение задач линейного программирования
Назначение сервиса. Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП. При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функцииF*(X) = -F(X). Также имеется возможность составить двойственную задачу.
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b, ax ≥ b, ax = b (F(X) → extr) сводится к виду ax = b, F(X) → max;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b, F(X) → max;
- Решение симплексным методом;
Как привести задачу линейного программирования к канонической форме
Как привести каноническую задачу линейного программирования к стандартной форме
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции:F*(X) = -F(X). Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)).
Проиллюстрируем этот факт графически:
F(x) → min |
F(x) → max |
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.
Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.
Пример №1. Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x1 + 2x2 - 2x3 → min при ограничениях:
4x1 + 3x2 - x3≤10
- 2x2 + 5x3≥3
x1 + 2x3=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x4; во втором неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
4x1 + 3x2-1x3 + 1x4 + 0x5 = 10
0x1-2x2 + 5x3 + 0x4-1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = - x1 - 2x2 + 2x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 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 | 61/2 | 1 | -11/2 | 141/2 |
| 0 | 1 | -21/2 | 0 | 1/2 | -11/2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 • 61/2):2 | 0-(0 • 61/2):2 | 61/2-(2 • 61/2):2 | 1-(0 • 61/2):2 | -11/2-(0 • 61/2):2 | 141/2-(9 • 61/2):2 |
| 0-(1 • -21/2):2 | 1-(0 • -21/2):2 | -21/2-(2 • -21/2):2 | 0-(0 • -21/2):2 | 1/2-(0 • -21/2):2 | -11/2-(9 • -21/2):2 |
| 1 : 2 | 0 : 2 | 2 : 2 | 0 : 2 | 0 : 2 | 9 : 2 |
Получаем новую матрицу:
| 3/4 | 0 | 0 | 1 | -11/2 | -143/4 |
| 11/4 | 1 | 0 | 0 | 1/2 | 93/4 |
| 1/2 | 0 | 1 | 0 | 0 | 41/2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3/4x1 + x4 - 11/2x5 = -143/4
11/4x1 + x2 + 1/2x5 = 93/4
1/2x1 + x3 = 41/2
Выразим базисные переменные через остальные:
x4 = - 3/4x1 + 11/2x5-143/4
x2 = - 11/4x1 - 1/2x5+93/4
x3 = - 1/2x1+41/2
Подставим их в целевую функцию:
F(X) = - x1 - 2(- 11/4x1 - 1/2x5+93/4) + 2(- 1/2x1+41/2)
или
F(X) = 1/2x1 + x5-101/2 → max
Система неравенств:
- 3/4x1 + 11/2x5-143/4 ≥ 0
- 11/4x1 - 1/2x5+93/4 ≥ 0
- 1/2x1+41/2 ≥ 0
Приводим систему неравенств к следующему виду:
3/4x1 - 11/2x5 ≤ -143/4
11/4x1 + 1/2x5 ≤ 93/4
1/2x1 ≤ 41/2
F(X) = 1/2x1 + x5-101/2 → max
Упростим систему.
3/4x1 - 11/2x2 ≤ -143/4
11/4x1 + 1/2x2 ≤ 93/4
1/2x1 ≤ 41/2
F(X) = 1/2x1 + x2-101/2 → max
Пример №2. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x1 + x2 - x3 + x5+15 → max (min) при ограничениях:
-3x1 + x2 + x3=3
4x1 + 2x2 - x4=12
2x1 - x2 + x5=2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0
Модель оптимизации рекламной кампании
С проблемой размещения рекламы в средствах массовой информации сталкиваются фирмы и рекламные агентства, перед которыми стоит задача увеличения сбыта рекламируемых товаров и услуг в стране или регионе.
Как правило, вопрос заключается в том, какие средства массовой информации следует выбрать (радио, телевидение, газеты, журналы, Интернет, реклама на световых табло и т. д.), сколько рекламных блоков нужно дать в каждом из средств массовой информации.
Ограничения, с которыми приходится считаться при принятии решения, могут быть связаны с величиной бюджетных средств, выделенных на рекламу, условиями рекламодателей (например, ограничение на число рекламных блоков). При размещении рекламы следует учитывать также и закон снижения отдачи от рекламы (при увеличении любого из ресурсов предельная эффективность является убывающей функцией). Хорошо известно, что десятый показ рекламного ролика оказывается менее эффективным, чем первый или второй показы.
Для того чтобы оптимизировать рекламную кампанию, следует правильно выбрать целевую функцию.
Естественно, что задачей рекламной кампании является стимулирование спроса на рекламируемый продукт. Заранее не известно, какая реклама и на сколько увеличит спрос на рекламируемый продукт или услугу. По этой причине должны быть заранее проведены дополнительные статистические исследования, позволяющие собрать нужную информацию.
Обычно используется следующий подход: отдача от рекламы в определенных СМИ оценивается по специальной шкале в так называемых единицах воздействия (частный случай экономической функции полезности потребителя).
Для дальнейшего знакомства с моделью рекламной кампании рассмотрим пример.
Пример. Компания, производящая стиральный порошок, хочет выпустить на рынок новый продукт. На рекламную кампанию в первый месяц продвижения продукта на рынок выделено 72 000 долларов. Компания обратилась за помощью в рекламное агентство, которое предоставило следующие данные о воздействии рекламы на целевую аудиторию:
| Размещение рекламы | Число единиц товара, купленных благодаря рекламе | Стоимость одного рекламного объявления, долл. |
Дневное радио | 30 000 | 1 700 |
Вечернее ТВ | 60 000 | 2 800 |
Ежедневная газета | 45 000 | 1 200 |
Рекламное агентство располагает информацией о снижении степени воздействии рекламы при ее многократном повторении. В частности, в агентстве считают, что на дневном радио эффективность первых 10 рекламных объявлений можно оценить 60 баллами, а всех последующих – 40 баллами. Таблица эффективности рекламных объявлений в различных СМИ приведена ниже.
| Размещение рекламы | Первые 10 объявлений | Последующие объявления |
Дневное радио (1) | 60 | 40 |
Вечернее ТВ (2) | 80 | 55 |
Ежедневная газета (3) | 70 | 35 |
Фирма-производитель стирального порошка сформулировала и некоторые дополнительные условия: а) в каждом СМИ должно быть размещено не более 25 объявлений; б) общими усилиями всех СМИ объем продаж должен возрасти на 1 800 000 единиц товара; в) не мене четверти всех рекламных объявлений должно быть сделано на вечернем ТВ.
Решение
Сформулированная задача является типичной задачей линейного программирования. Для ее решения введем шесть переменных xi, yi, i = 1,2,3. Переменные xi описывают число рекламных объявлений на радио (i=1), телевидении (i=2) и в газете (i=3), если их число не превышает 10, величины yi– число рекламных объявлений на радио (i=1), телевидении (i=2) и в газете (i=3), если их число превышает 10.
В этих обозначениях задача оптимизации рекламной кампании состоит в том, чтобы добиться максимума эффективности рекламных объявлений:
60x1 + 40y1 + 80x2 + 55y2 +70x3 + 35y3 → max
Ограничения на количество объявлений запишутся в виде
x1 + y1 ≤ 25
x2 + y2 ≤ 25
x3 + y3 ≤ 25
поскольку в каждом из СМИ не может появиться более 25 объявлений.
Объем средств, затраченных на рекламную кампанию, подсчитать достаточно легко, поскольку известна стоимость одного объявления в различных СМИ. Выполняя подсчеты, получаем бюджетное ограничение
1700(x1 + y1) + 2800(x2 + y2) + 1200(x3 + y3) ≤ 72 000
В соответствии с требованием заказчика число продаж в результате рекламной кампании должно возрасти на 1 800 000 единиц. Поэтому имеем еще одно ограничение :
30 000(x1 + y1) + 60 00(x2 + y2) + 45 000(x3 + y3) ≤ 1 800 000
Требование размещения не менее четверти рекламных объявлений на вечернем ТВ, приводит нас к ограничению
x2 + y2 ≥ 0,25 (x1 + y1 + x2 + y2 + x3 + y3)
Количество рекламных объявлений должно быть целым числом. Поэтому при введении данных в программу Поиск решения нужно добавить еще и это ограничение.
Следует помнить, что если переменные задачи являются целыми величинами, то программа Поиск решения Excel не генерирует отчет по устойчивости.