 |
Алгоритм решения задачи графическим методом
|
|
|
|
Решение задач ЛП графическим методом осуществляется по следующему алгоритму.
1. Находим область допустимых решений (ОДР) по каждому ограничению и общую ОДР.
2. Находим координаты угловых точек и значение F(x) в каждой точке. max F(x) определяет точку оптимального решения.
3. Строим вектор-градиент grad F(x)= 
F(x) по координатам (0,0; c1,c2), который показывает направление наискорейшего возрастания целевой функции.
4. Проводим линию уровня (линию прибыли), которая перпендикулярна вектору-градиенту.
5. Линию уровня перемещаем по направлению вектора 
F для задач на максимум и в направлении, противоположном F, для задач на минимум.
Перемещение линии уровня производится до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений (ОДР). Эта точка определяет единственное решение задачи ЛП и будет точкой экстремума.
Если окажется, что линия уровня параллельна одной из сторон ОДР, то задача ЛП будет иметь бесчисленное множество решений.
Если ОДР представляет неограниченную область, то целевая функция может быть неограниченна.
Задача ЛП может быть неразрешима, когда определяющие ее ограничения окажутся противоречивыми.
6. Находим координаты точки экстремума и значение целевой функции в ней.
Рассмотрим нахождение оптимального плана выпуска изделий предприятия на следующем примере.
Пример 1. Фирма выпускает два вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются два исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы исходных продуктов даны в таблице.
| Исходный продукт | Расход исходных продуктов на 1 кг мороженого | Запас, кг. | |
| Сливочное | Шоколадное | ||
| Молоко | 0,8 | 0,5 | |
| Наполнители | 0,4 | 0,8 |
|
|
|
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг.
Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 руб. ед., шоколадного – 14 руб.
Требуется определить, какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?
Решение.Обозначим: x1 – суточный объем выпуска сливочного мороженого, кг; x2 – суточный объем выпуска шоколадного мороженого, кг.
Составим математическую модель задачи.
Целевая функция будет иметь вид:
F(x) =16x1+14x2 àmax
при ограничениях:
0,8x1 + 0,5x2 < 400,
0,4x1 + 0,8x2 < 365, (3.1)
x1 – x2 < 100,
x2 < 350,
x1 > 0, x2 > 0.
Модель (3.1), представленная такой записью ограничений, граничных условий и целевой функции, относится к типу задач линейного программирования. Термин «линейное программирование» объясняется тем, что при подсчете расходов ресурсов на программу выпуска и расчете ожидаемой выручки после реализации всей выпущенной по этой программе продукции используются только линейные функции.
Этап 1. Под допустимым решением задачи ЛП понимается такой числовой набор значений искомых переменных, который при подстановке во все ограничения и граничные условия задачи обращает их в истинные числовые неравенства и равенства. Под областью допустимых решений (ОДР) задачи ЛП понимается геометрическое место точек, координаты которых являются допустимыми решениями.
Прежде всего, укажем в декартовой системе координат на рис.3.1 область допустимых решений для первого ограничения задачи (3.1). Для этого проведем в системе координат прямую, соответствующую первому ограничению. Уравнение этой прямой будет получено, если первое ограничение будет записано как равенство
|
|
|
0,8 x1 + 0,5 x2 = 400
Рис.3.1ОДР по молоку
Задавая произвольно значение одной из координат точки, лежащей на этой прямой, можно через полученное уравнение вычислить значение другой координаты этой же точки. Если данная прямая имеет точки пересечения с обеими осями в пределах создаваемого рисунка, то лучше присваивать нулевое значение сначала первой переменной, затем второй переменной, находя соответствующее значение другой переменной.
Результаты этих вычислений:
x1 = 0; x2 = 800;
x2 = 0; x1 = 500.
Отметим эти точки на осях рис.3.1 и проведем через них прямую, соответствующую первому ограничению. Если взять координаты любой точки, лежащей на этой прямой, то они обратят первое ограничение в равенство. Для выявления точек, координаты которых строго удовлетворяют данному ограничению, нужно указать на одну из образовавшихся полуплоскостей.
Для определения полуплоскости, координаты точек которой являются строгими решениями данного неравенства, необходимо выбрать пробную точку, явно принадлежащую какой-либо из двух полуплоскостей, полученных после проведения прямой, соответствующей этому неравенству.
Если координаты пробной точки обращают неравенство в истинное числовое неравенство, то полуплоскость, которой она принадлежит, является искомой. На рисунке 3.1 искомая полуплоскость выделена штриховкой.
Таким образом, с помощью одной пробы графически выявляется область допустимых решений для любого из ограничений и граничных условий анализируемой задачи ЛП.
Подобным образом следует поступить с каждым ограничением и граничным условием задачи ЛП (рис. 3.2).
Рис.3.2. ОДР по ограничениям задачи
Следующим шагом нужно выделить общую часть обозначенных штриховкой полуплоскостей или, другими словами, найти их пересечение. На рисунке 3.3 заштрихованный многоугольник представляет собой все множество точек, координаты которых обращают в истинные утверждения все ограничения и граничные условия модели. Это означает, что область допустимых решений задачи ЛП построена.
Рис.3.3 Нахождение общей ОДР задачи
Этап 2. Под оптимальным решением задачи ЛП понимается такое допустимое решение, при котором целевая функция задачи принимает экстремальное значение (максимальное или минимальное). Доказано, что среди множества оптимальных решений задачи ЛП, если они есть у этой задачи, обязательно существуют координаты вершины или угловой точки многоугольной области допустимых решений задачи ЛП (ограниченной или неограниченной). Набор числовых значений координат угловой точки ОДР называется опорным решением задачи ЛП. Другими словами, среди множества решений задачи ЛП всегда существует подмножество опорных решений.
|
|
|
Выделенному многоугольнику (рис. 3.4) области допустимых решений соответствуют шесть опорных решений – шесть угловых точек: О (0;0); А(0;350); В (212,5;350); Д (312,5;300); Е (346,15;246,15); F (100;0).
Координаты точки Д (312,5;300) можно найти, вычислив координаты точки пересечения прямых по молоку и наполнителю, для чего нужно решить систему уравнений:
0,8x1 + 0,5x2 =400
0,4x1 + 0,8x2 =365
откуда x1 = 312,5; x2 = 300.
Далее подставляем координаты каждой угловой точки в целевую функцию и определяем доход: А-4900; В-8300; Д-9200; Е-8984,5; F-1600.
Максимальный доход будет в точке Д, т.е. оптимальное решение состоит в выпуске 312,5 кг словочного мороженого и 300 кг шоколадного, при этом молоко и наполнитель использованы полностью, выполняются ограничения по спросу и достигается максимальный доход в 9200 руб.
Очевидно, что нахождение оптимального решения путем прямого набора их точек трудоемко, особенно когда много ограничений. Поэтому воспользуемся другим способом нахождения оптимума.
Рис.3.4 Нахождение оптимального решения
Этап 3-4. Для визуального выявления оптимального решения среди этих опорных решений используем следующие теоретические понятия.
Под линией уровня целевой функции понимается геометрическое место точек, для координат которых целевая функция имеет постоянное числовое значение (рис. 3.5).
Например, уравнение линии уровня 1600 будет иметь вид: 16x1+142=1600 или уравнение линии уровня 4900 - 16x1+14x2=4900 (соответственно: прямая 1и 2,рис.3.5) и т.д.
Очевидно, что для всех возможных числовых значений линии уровня целевой функции являются прямыми, которые будут параллельные между собой и покрывать всю плоскость.
|
|
|
Под градиентом целевой функции понимается вектор с началом в текущей точки плоскости x=(x1, x2), координаты которого рассчитываются, как значение частных производных целевой функции F (х) в этой точке:
grad F(x)= 
, 
Градиент целевой функции обладает двумя характерными свойствами:
1) Перпендикулярен линиям уровня целевой функции;
|
|
|
