Понятие о задачах линейного программирования. Графический метод поиска оптимального решения
Общая задача линейного программирования – это поиск максимума или минимума (оптимума) определённой функции при ограничениях, заданных системой линейных неравенств или уравнений.
Функция, оптимум которой исследуется, называется целевой функцией.
Ограничения, связанные с конечным количеством ресурсов, называют ресурсными ограничениями . Кроме них, в задаче могут быть и другие ограничения.
Например:
1. Целевая функция – доход предприятия, для которого нужно найти максимум. Ограничения – ресурсы предприятия (сырьё, оборудования, труд), запас которых конечен.
2. Целевая функция – длина маршрута перевозки грузов, для которой нужно искать минимум. Ограничения – фактическая длина пути от каждого поставщика к потребителю, фактические предложения поставщиков и запросы потребителей.
3. Целевая функция – расходы на питание, для которых нужно искать минимум. Ограничения – необходимая калорийность, сбалансированность, состав по клетчатке, витаминам и минералам.
п.2. Задача о максимальном доходе
Рассмотрим классическую задачу о получении максимального дохода от продаж.
Пусть предприятие производит два вида продукции, А и Б, по цене 10 и 15 руб. за единицу. При этом затрачивается три вида ресурсов: сырьё, оборудование и труд. Затраты каждого из ресурсов (в руб.) на производство единицы продукции представлены в таблице. Там же указан общий запас каждого ресурса (в пересчёте на руб.), т.е. ограничение его расхода сверху.
| Ресурс | Затраты на производство единицы продукции, руб. | Запас, руб. | |
| A | Б | ||
| Сырье | 2 | 5 | 400 |
| Оборудование | 1 | 3 | 210 |
| Труд | 1 | 1 | 100 |
Задача: разработать такой план производства по каждому из видов продукции, чтобы получить максимальный доход от продаж.
Пусть x – количество изделий А, y — количество изделий Б, по нашему плану.
Целевая функция: доход от продаж f(x, y) = 10x + 15y → max
Ресурсные ограничения: \begin \left\< \begin < l >\mathrm <3x+5y\leq 400>& \\ \mathrm
Отмечаем на координатной плоскости все ограничения. Полученное множество – пятиугольник ABCDE — множество допустимых решений нашей задачи.
Коэффициенты целевой функции задают вектор \( \mathrm<\overrightarrow=(10;\ 15).> \)
Все прямые доходов от продаж 10x + 15y = F, где F — какое-то число, будут перпендикулярны вектору \( \mathrm<\overrightarrow.> \)
Наша задача – построить прямую через точку 10$x_0$ + 15$y_0$ = $F_$, перпендикулярную вектору \( \mathrm<\overrightarrow> \), как можно выше, но так чтобы точка ($x_0$, $y_0$) всё ещё входила в множество допустимых решений.
В нашем случае такой точкой является вершина D(50; 50).
Прямая 10x + 15y = 10 · 50 + 15 · 50 = 1250 соответствует решению – максимально возможному доходу.
План производства: x = 50 изделий А, y = 50 изделий Б.
Максимальный доход от продаж: 1250 руб.
п.3. Задача о рациональном питании
Рассмотрим задачу о составлении оптимального рациона питания на неделю.
Пусть наибольшие расходы семейного бюджета идут на мясо и фрукты, в среднем по 600 и 150 рублей за килограмм. Нормы питания на неделю и количество питательных веществ при перерасчёте на кг даны в таблице.
| Питательные вещества | Количество питательных веществ на 1 кг | Норма на неделю | |
| Мясо | Фрукты | ||
| Белки, г | 300 | 50 | 700 |
| Животные жиры, г | 200 | 0 | 700 |
| Витамины, мг | 50 | 150 | 600 |
| Клетчатка, г | 50 | 250 | 1000 |
Задача: необходимо свести расходы к минимуму, но при этом обеспечить нужное количество (не ниже нормы) белков, животных жиров, витаминов и клетчатки.
Пусть x – количество мяса, кг, y — количество фруктов, кг, по нашему плану.
Целевая функция: расходы на покупку f(x, y) = 600x + 150y → min
Ограничения по нормам: \begin \left\< \begin < l >\mathrm <300x+50y\geq 700>& \\ \mathrm <200x\geq 700>& \\ \mathrm <50x+150y\geq 600>& \\ \mathrm <50x+250y\geq 1000>& \end\right.\\ \mathrm
Коэффициенты целевой функции задают вектор \( \mathrm<\overrightarrow=(600;\ 150).> \)
Мы можем его сократить для удобства, т.к. при построении нас интересует направление, а не длина вектора. Пусть \( \mathrm<\overrightarrow=(4;\ 1)> \) ↑↑ \( \mathrm<\overrightarrow.> \)
Все прямые расходов 600x + 150y = F будут перпендикулярны вектору \( \mathrm<\overrightarrow.> \)
Наша задача – построить прямую через точку 600$x_0$ + 150$y_0$ = $F_$, перпендикулярную вектору \( \mathrm<\overrightarrow,> \) как можно ниже, но так чтобы точка ($x_0$, $y_0$) всё ещё входила в множество допустимых решений.
В нашем случае такой точкой является вершина A(3,5; 3,3).
Прямая 600x + 150y = 600 · 3,5 + 150 · 3,3 = 2595 соответствует решению – минимально возможным расходам.
План закупок на неделю: x = 3,5 кг мяса, y = 3,3 кг фруктов.
Минимальная стоимость закупок: 2595 руб.
Научная электронная библиотека
Задачами линейного программирования называются оптимизационные задачи, в которых ограничения, представленные в виде равенств или неравенств, и целевая функция линейна. Разработка модели ЛП включает следующие основные этапы: определение переменных задачи, представление её ограничений в виде линейных уравнений или неравенств, задание линейной целевой функции, подлежащей минимизации или максимизации.
Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид:
максимизировать или минимизировать
Задачи ЛП в стандартной форме можно записать в компактных матричных обозначениях следующим образом:
максимизировать или минимизировать
где A — матрица размерности mxn, x — вектор-столбец размерности nxl, b— вектор-столбец размерности mxl, а c — вектор-строка размерности .1xn.
Обычно A назначается матрицей коэффициентов, x — вектором переменных, b — вектором ресурсов, c — вектором оценок задачи ЛП.
При решении задачи ЛП симплекс-методом требуется, чтобы задача была представлена в стандартной форме. Однако не все практические задачи ее имеют, поэтому для удовлетворения требования алгоритма необходимо следующее.
- 1. При помощи введения дополнительных остаточных или избыточных переменных преобразовать неравенства в равенства.
- 2. Для получения неотрицательных переменных задачи неограниченные по знаку переменные заменить разностью двух неотрицательных.
При решении задач ЛП используются следующие основные понятия. Допустимым решением являются неотрицательные значения переменных, для которых выполняются ограничения, а допустимой областью — совокупность допустимых решений. Оптимальным решением называются такие допустимые значения переменных, при которых ЦФ экстремальна, т.е. имеет оптимальное значение. В ряде случаев, ЦФ имеет одно оптимальное значение при нескольких комбинаций значений переменных, следовательно, задача обладает неединственностью оптимума. Когда в задаче ЛП нет конечного оптимума, то в этом случае существует неограниченный оптимум.
Что такое оптимум задачи линейного программирования
Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.
Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:
математические модели очень большого числа экономических задач линейны относительно искомых переменных;
для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы.
Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).
В общей постановке задача линейного программирования выглядит следующим образом:
Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х1 , х2 , … хn ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:
В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что
а) функция f(x) является линейной функцией переменных х1 , х2 , … хn
б) область G определяется системой линейных равенств или неравенств.
Математическая модель любой задачи линейного программирования включает в себя:
- максимум или минимум целевой функции (критерий оптимальности);
- систему ограничений в форме линейных уравнений и неравенств;
- требование неотрицательности переменных.
В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Поyтому в наиболее общей форме задачу линейного программирования формулируют следующим образом:
Что такое оптимум задачи линейного программирования
МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Общая задача линейного программирования
Выше мы рассмотрели математические модели задачи оптимального использования ресурсов и транспортной задачи. Все рассмотренные модели обладают свойствами, позволяющими включить их в широкий и важный класс — класс задач линейного программирования. Задачи линейного программирования, охватывают самые разнообразные управленческие ситуации, требующие расчета оптимальных решений. Наряду с различными моделями производственных ситуаций, они содержат задачи, возникающие из других экономических проблем. Единый подход к моделированию разнообразных задач позволяет разработать единые методы их решения и анализа, дает возможность увидеть существенные общие черты в проблемах, различных по экономическому содержанию и источникам возникновения. Дадим необходимые определения.
Функция n переменных x 1, x 2, . x n
называется линейной функцией , если она представима в виде линейной комбинации переменных, то есть в виде суммы переменных с постоянными коэффициентами
Иногда линейной называют также функцию вида
отличающуюся от предыдущей постоянным слагаемым d .
а также неравенства
называются линейным равенством и линейными неравенствами , если функция
Задачей линейного программирования называется задача, состоящая в нахождении экстремального (максимального или минимального) значения линейной функции
при условии, что переменные удовлетворяют системе линейных равенств и неравенств:
Функция, экстремальное значение которой требуется отыскать, называется целевой функцией . Система равенств и неравенств называется системой ограничений .
Всякий набор значений переменных, то есть вектор X значений,
называется планом задачи . План называется допустимым планом , если он удовлетворяет системе ограничений. Обычно (но не всегда) множество допустимых планов бесконечно. На разных планах целевая функция принимает различные значения. Задача линейного программирования требует, чтобы среди всех допустимых планов был найден тот план, на котором целевая функция достигает искомого экстремального значения (максимального и минимального, в зависимости от конкретной задачи). Такой план называется оптимальным планом . Значение целевой функции на оптимальном плане называется оптимумом .
Решить задачу линейного программирования — значит найти ее оптимальный план и оптимум.