 |
|
Виды задач линейного программирования
· Задача оптимального использования ресурсов
задача линейного программирования сводится к отысканию такого решения системы линейных уравнений и (или) неравенств (системы ограничений), при котором функция цели - линейная функция - принимает оптимальное значение (экстремум (максимум или минимум)). Число переменных в системе чаще всего не равно числу уравнений (неравенств).
· Транспортная задача
Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).
· Игра с нулевой суммой
Игра или пари двух и более человек, при которой выигрыш одного равен проигрышу другого, то есть доходы минус убытки дают нуль.
· Задача о смесях
К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.
Геометрический смысл задачи линейного программирования
Если система ограничений задачи линейного программирования представлена в виде системы линейных неравенств с двумя переменными, то такая задача может быть решена геометрически.
Данный метод решения ЗЛП имеет очень узкие рамки применения. Однако метод представляет большой интерес с точки зрения выработки наглядных представлений о сущности задач линейного программирования.
Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.
1. Сформулировать ЗЛП.
2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.
3. Найти полуплоскости, определяемые каждым из ограничений задачи.
4. Найти область допустимых решений.
5. Построить прямую c1x1 + c2x2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.
6. Перемещать найденную прямую параллельно самой себе в направлении увеличения (при поиске максимума) или уменьшения (при поиске минимума) целевой функции. В результате, либо отыщется точка, в которой целевая функция принимает максимальное (минимальное) значение, либо будет установлена неограниченность функции на множестве решений.
7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.