- •Раздел 1. Линейное программирование
- •1.1. Математическая постановка задачи
- •Формализация задачи
- •1.2. Графическое решение задачи
- •1.3. Каноническая форма задачи
- •1.4. Базис и базисное решение
- •1.5. Табличный симплекс-метод (симплекс-алгоритм)
- •Шаг 7. Симплексные преобразования таблицы.
- •Анализ ситуации
- •Анализ ситуации:
- •1.6. Двойственная задача лп
- •Задание
- •1.7. Транспортная задача
- •1.8. Целочисленная задача лп
- •1.9. Задачи и вопросы для практических работ
Раздел 1. Линейное программирование
1.1. Математическая постановка задачи
В наиболее общей форме математическая постановка задачи линейного программирования (ЛП) имеет вид
(D, f) : , (1.1)
i=1,…,m
xj ≥ 0
или в матричной форме
(D,f) : , (1.2)
Ax ≤ b
xj ≥ 0
где х = (х1, …, хп)Т – вектор переменных задачи, f(x) целевая функция, D – множество допустимых решений. Целью задачи является нахождение такого вектора х* из D, который либо максимизирует, либо минимизирует целевую функцию, т. е. f(x* ) f(x) х D (в случае максимума) или f(x* ) f(x) х D (в случае минимума). Такие решения называются оптимальными.
Отметим ряд характерных особенностей (или свойств) задачи линейного программирования, которые лежат в основе алгоритма ее решения.
а) Множество допустимых решений D, если оно не пусто, то обязательно выпукло и либо ограничено (по расстоянию), либо не ограничено;
б) Множество D представляет собой многогранное множество (или выпуклый многогранник), имеющее вершины (их число ограничено – см. раздел 3), боковые ребра и боковые грани;
в) Линии уровня целевой функции представляют собой параллельные плоскости (или гиперплоскости), перпендикулярные направлению вектора коэффициентов с; направление вектора с определяет направление возрастания значения целевой функции f(x), а его обратное направление – направление убывания значения f(x);
г) Если множество D ограничено, то целевая функция достигает на нем и своего максимального значения, и минимального значения как следствие центральной теоремы математического анализа – теоремы Вейерштрасса.
е) Если задача имеет оптимальное решение, то оно находится по крайней мере в одной из вершин множества D; задача может не иметь оптимальное решение из-за неограниченности множества D, когда целевая функция на нем неограниченно возрастает или убывает;
ж) Алгоритм решения задачи представляет собой последовательность действий, связанных с генерацией вершин множества D и проверкой правила оптимальности (правила завершения работы).
Пример 1. Планирование многопродуктового производства. По данным маркетинговых исследований рынка фирма решила производить п видов товаров. Известны рыночные цены на производимые товары и услуги, а также объемы необходимых для производства ресурсов (производственные факторы). Необходимо определить такие объемы производимых товаров (уровни или интенсивности производства), которые отвечают ограничениям задачи по ресурсам и максимизируют суммарный доход фирмы от реализации продукции.
Для построения математической модели задачи введем следующие обозначения:
а) переменные задачи - xj, j = 1,…, n, - искомые объемы производимых товаров;
б) ограничения задачи –
, i = 1,…, m,
xj ≥ 0, j=1,…, n,
где bi, i = 1,…, m, - имеющиеся в распоряжении фирмы ресурсы (основные фонды, трудовые ресурсы и т.д.), аij, i = 1, …, m, j = 1, …, n, - технологические нормы расходования единиц ресурсов i – го типа на производство одной единицы продукции j – го типа;
в) целевая функция – функция дохода
.
Цель задачи заключается в нахождении такого вектора х* = (х1* , …, хп*)Т, который удовлетворяет ограничениям задачи и максимизирует функцию f(x).
Ниже мы рассмотрим решение этой задачи при конкретных числовых данных.
Пример 2. Фирма производит определенный вид продукции, рыночная цена которой равна 20 ден. ед. Имеется 3 способа изготовления продукции (3 технологии), каждый из которых характеризуется своим уровнем затрат рабочего и машинного времени, а также сырья на единицу продукции. Эти удельные затраты представлены в следующей таблице
Таблица исходных данных
Способ изготовления |
Затрат рабочего времени |
Затрат машинного времени |
Затрат сырья |
Т1 |
2 |
4 |
2 |
Т2 |
2 |
3 |
3 |
Т3 |
4 |
2 |
1 |
Рабочее время оплачивается в размере 3 ден.ед./ч., сырье стоит 4 ден.ед./кг, стоимость машинного времени несущественна. Имеются следующие ограничения на ресурсы в расчете на сутки: рабочее время – 24 часа, машинное время – 12 часов, сырье –18 кг. Необходимо определить, сколько продукции следует произвести каждым из способов (технологий), чтобы максимизировать прибыль?
Формализация задачи
а) переменными задачи являются x1, x2, x3 ≥ 0 - число единиц продукции, изготовленной первым, вторым и третьим способами соответственно;
б) ограничения на ресурсы:
2x1 + 2x2 + 4x3 ≤ 24 (рабочее время),
4x1 + 3x2 + 2x3 ≤ 12 (машинное время),
2x1 + 3x2 + x3 ≤ 18 (сырье);
в) функция прибыли:
прибыль на единицу продукции, произведенной первым способом (технологией) составляет по условию 20 – (2*3+2*4) = 6 ден.ед., вторым способом (технологией) 20 – (2*3+3*4) = 2 ден.ед., третьим способом (технологией) 20 – (4*3+1*4) = 4 ден.ед., так что
.
Математическая постановка задачи имеет вид
.
(x1, x2, x3)
2x1 + 2x2 + 4x3 ≤ 24
4x1 + 3x2 + 2x3 ≤ 12
2x1 + 3x2 + x3 ≤ 18
Пример 3. Фирма производит два вида краски для внутренних и наружных работ из сырья двух типов: М1 и М2. Расход сырья (в тоннах) на тонну краски каждого типа представлены в следующей таблице:
Таблица исходных данных
З атраты Сырье |
Для наружных работ |
Для внутренних работ |
Максимальный ежедневный расход |
М1 |
6 |
4 |
24 |
М2 |
1 |
2 |
6 |
Максимально возможный ежедневный расход сырья составляет 24 и 6 тонн каждого.
Определить оптимальные объемы выпускаемой продукции для максимизации общего ежедневного дохода, если доход каждой тонны наружной и внутренней краски составляет 5000 и 4000 ден.ед.