3 Решение экономических задач графическим способом

Теперь рассмотрим несколько задач линейного программирования и их решение графическим методом.

Задача 1.

max Z = 1+ - ,

.

Решение. Заметим, что полуплоскости, определяемые системой неравенств данной задачи не имеют общих точек (рисунок 2 [14, с. 31, рисунок 3.4]). Задача не имеет решения по причине несовместности условий задачи.

Рисунок 2

Задача 2. Цех выпускает два вида продукции, используя два вида полуфабрикатов. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объёмы полуфабрикатов и прибыль от единицы каждой продукции представлены в таблице 1[13, с. 32, таблица 1.3]. Определить план производства, доставляющий максимум прибыли.

Решение. Пусть х = () - план задачи. Тогда модель задачи примет вид

max Z =10+35

Ограничения на полуфабрикаты:

+2?800,

6+2?2400

Условие комплектности и неотрицательности переменных:

2?

?0, ?0.

Построив соответствующие данным ограничениям-неравенствам граничные прямые +2=800, 6+2=2400, 2-=0, определим полуплоскости, в которых выполняются эти неравенства (рисунок 3 [13, с. 32, рисунок 1.5]). Для этого достаточно взять произвольную точку, не лежащую на граничной прямой, и подставить её координаты в неравенство. Для первых двух неравенств возьмём, например, начало координат О(0; 0). Получим истинные утверждения (0?800, 0?2400). Следовательно, первые два неравенства выполняются в полуплоскостях, содержащих точку О. Граничная прямая, соответствующая третьему неравенству, проходит через начало координат. Значит, нужно взять, например, точку (0; 10). Получаем ложное утверждение (0?10). Следовательно, третьему неравенству удовлетворяют точки полуплоскости, не содержащей пробной точки (0; 10).

Рисунок 3

Поскольку ?0 и ?0, областью допустимых решений является четырёхугольник ОАВС. Далее надо построить вектор с = (). Так как он необходим лишь для выяснения направления возрастания целевой функции, иногда для большей наглядности удобно строить вектор лс (). В нашем примере взято л=10 и построен вектор проводим линию уровня Z=0. Параллельным перемещением прямой Z=0 находим точку А, в которой целевая функция достигает максимума.

Решая совместно уравнения граничных прямых АВ и ОА, находим координаты точки А: =160, =320. При этом = max Z = z (A) =12800.

Итак, по оптимальному плану следует выпускать 160 ед. продукции и 320 ед.продукции , что принесёт прибыль в 12800 р.

Графическим методом можно решить задачу линейного программирования с n>2 переменными, если в ее канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n-m?2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.

Задача 3. Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 230 т., на второй 168 т. Первый погрузчик на первой площадке может погрузить 10 т. в час, на второй - 12 т. Второй - на каждой площадке может погрузить по 13 т. в час. Стоимость работ, связанных с погрузкой 1 т. первым погрузчиком на первой площадке составляет 8 р., на второй площадке - 7 р. Стоимость погрузки вторым погрузчиком на первой площадке составляет 12 р., на второй - 13 р. Нужно составить план работы, т.е. найти, какой объем работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной, учитывая, что по техническим причинам первый погрузчик на второй площадке должен работать не более 16 часов.

Решение. Обозначим через объем работ (в тоннах) i-го погрузчика (i=1,2) на j-ой площадке (j=1,2). Условия задачи перенесем в таблицу 2 [13, с. 34, таблица 1.4].

Построим математическую модель задачи. Целевая функция описывает затраты, связанные с выполнением всех работ:

8+7+12+13

Ограничения на лимиты рабочего времени:

Необходимость выполнить задание:

Условие неотрицательности:

Исключим из модели переменные и . Из ограничений неравенств имеем = 230 - , = 168 - . Подставив выражения для и в ограничения неравенства и целевую функцию, получим задачу линейного программирования с двумя переменными .

min Z = 4944 - 4- 6,

Очевидно, что целевая функция Z = 4944 - 4- 6 достигает минимального значения при условии, что принимает максимальное значение. Имеем задачу

max

Графическое решение задачи представлено на рисунке 4 [13, с. 36, рисунок 1.6].

Рисунок 4

Функция достигает наибольшего значения при

Из выражений для и получим 0.

Итак, по оптимальному плану первый погрузчик должен погрузить 100 т. на первой площадке и 168 т. на второй, второму погрузчику надлежит погрузить 130 т. на первой площадке. Стоимость всех работ составит 3536 р. ().

Таким образом, процедура поиска решения в таких простейших задачах линейного программирования является несложной: нужно каким-либо способом описать многоугольник допустимых точек, найти его вершины и выбрать из них те, координаты которых придают максимальное значение целевой функции. Кроме того, заслуживает рассмотрения и наглядная связь между нормалью к линейной форме, задающей целевую функцию, и нормалями к прямым, пересечение которых определяет решение задачи.

И хотя в случае, когда изучаются задачи линейного программирования в пространстве большого числа переменных с большим числом ограничений, структура допустимого множества становится гораздо менее наглядной, а вычислительные сложности возрастают чрезвычайно, основные идеи поиска решения остаются неизменными.