Векторное пространство Решение задач линейного программирования графическим способом (стр. 4 из 5)

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

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

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

Задача 1.

maxZ = 1+

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

Рисунок 2

Задача 2.Цех выпускает два вида продукции, используя два вида полуфабрикатов. Продукция используется при комплектовании изделий, при этом на каждую единицу продукции первого вида требуется не более двух единиц продукции второго вида. Нормы расхода

полуфабрикатов каждого вида на единицу выпускаемой продукции, общие объёмы полуфабрикатов

и прибыль

от единицы каждой продукции представлены в таблице 1[13, с. 32, таблица 1.3]. Определить план производства, доставляющий максимум прибыли.

Решение. Пусть х = (

) – план задачи. Тогда модель задачи примет вид

maxZ =10

+35

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

≤800,

≤2400

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

≥

≥0,

≥0.

Таблица 1

Полуфабрикаты	Нормы затрат на единицу продукции		Объём полуфабриката
Полуфабрикаты			Объём полуфабриката
I II	1 6	2 2	800 2400
Прибыль	10	35

Построив соответствующие данным ограничениям-неравенствам граничные прямые

=800, 6

=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. При этом

= maxZ = 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].

Таблица 2

i j							Лист рабочего времени
I погрузчик	10		8	12		7	24

II погрузчик	13	12		13	13		24

Задание	230			168

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

+12

+13