|
б), либо ограниченной как снизу, так и сверху (рис. 2.2, в).
2.1. Примеры задач, решаемых графическим методом.
Решим графическим методом задачи использования сырья и составления рациона.
Задача использования сырья. Для изготовления двух видов продукции
Р1 и Р2 используют три вида сырья: S1, S2
, S3. Запасы сырья, количество единиц сырья, затрачиваемых на
изготовление единицы продукци, а так же величина прибыли, получаемая от
реализации единицы продукции, приведены в таблице 2.1.
Таблица 2.1.
| Вид сырья | Запас сырья | Количество единиц сырья, идущих на изготовление единицы продукции | Р1 | Р2 | S1 | 20 | 2 | 5 | S2 | 40 | 8 | 5 | S3 | 30 | 5 | 6 | | Прибыль от единицы продукции, руб. | 50 | 40 |
Необходимо составить такой план выпуска продукции, чтобы при ее реализации
получить максимальную прибыль.
Решение.
Обозначим через х1 количество единиц продукции Р1, а через
х2 – количество единиц продукции Р2. Тогда, учитывая
количество единиц сырья, расходуемое на изготовление продукции, а так же запасы
сырья, получим систему ограничений:
2х1 + 5х2 20
8х1 + 5х2 40
5х1 + 6х2 30
которая показывает, что количество сырья, расходуемое на изготовление продукции,
не может превысит имеющихся запасов. Если продукция Р1 не
выпускается, то х1=0; в противном случае x1 0. То же
самое получаем и для продукции Р2. Таким образом, на неизвестные х
1 и х2 должно быть наложено ограничение неотрицательности: х
1 0, х2 0.
Конечную цель решаемой задачи – получение максимальной прибылипри реализации
продукции – выразим как функцию двух переменных х1 и х2.
Реализация х1 единиц продукции Р1 и х2 единиц
продукции Р2 дает соответственно 50х1 и 40х2
руб. прибыли, суммарная прибыль Z = 50х1 + 40х2 (руб.)
Условиями не оговорена неделимость единица продукции, поэтому х1 и х
2 (план выпуска продукции) могут быть и дробными числами.
Требуется найти такие х1 и х2, при которых функция Z
достинает максимум, т.е. найти максимальное значение линейной функции Z = 50х
1 + 40х2 при ограничениях
2х1 + 5х2 20
8х1 + 5х2 40
5х1 + 6х2 30
х1 0, х2 0.
Построим многоугольник решений (рис. 2.3).
Для этого в системе координат х1Ох2 на плоскости на
плоскости изобразим граничные прямые
2х1 + 5х2 = 20 (L1)
8х1 + 5х2 = 40 (L2)
5х1 + 6х2 = 30 (L3)
х1 = 0, х2 = 0.
Взяв какую-нибудь точку, например, начало координат, установим, какую
полуплоскость определяет соответствующее неравенство (эти полуплоскости на
рис. 2.3 показаны стрелками). Многоугольником решений данной задачи
является ограниченный пятиугольник ОАВСD.
Для построения прямой 50х1 + 40х2 = 0 строим радиус-вектор
N = (50;40) = 10(5;4) и через точку O проводим прямую, перпендикулярную ему.
Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении
вектора N. Из риc. 2.3 следует, что опорной по отношению к многоугольнику
решений эта прямая становится в точке С, где функция Z принимает максимальное
значение. Точка С лежит на пересечении прямых L1 и L2.
Для определения ее координат решим систему уравнений
8x1 + 5х2 = 40
5х1 + 6х2 = 30
Оптимальный план задачи: х1 = 90/23 = 3,9; х2 = 40/23 =
1,7. Подставляя значения х1 и х2 в линейную функцию,
получаем Zmax = 50 3,9 + 40 1,7 = 260,3
Таким образом, для того чтобы получить максимальную прибыль в размере 260,3
руб., необходимо запланировать производство 3,9 ед. продукции Р1 и
1,7 ед. продукции Р2.
Задача составления рациона. При откорме каждое животное ежедневно
должно получать не менее 9 ед. питательного вещества S1, не менее 8
ед. вещества S2 и не менее 12 ед. вещества S3. Для
составления рациона используют два вида корма. Содержание количества елиниц
питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены
в таблице 2.2.
Таблица 2.2.
| Питательные вещества | Количество единиц питательных веществ в 1 кг корма. | | Корм 1 | Корм 2 | S1 | 3 | 1 | S2 | 1 | 2 | S3 | 1 | 6 | | Стоимость 1 кг корма, коп. | 4 | 6 |
Необходимо составить дневной рацион нужной питательности, причем затраты на
него должны быть минимальными.
Решение.
Для составления математической модели обозначим через х1 и х2
соответственно количество килограммов корма 1 и 2 в дневном рационе. Принимая во
внимание значения, приведенные в таблице 2.2, и условие, что дневной рацион
удовлетворяет требуемой питательности только в случае, если количество единиц
питательных веществ не меньше предусмотренного, получаем систему ограничений
3х1 + х2 9
х1 + 2х2 8
х1 + 6х2 12
х1 0, х2 0.
Если корм 1 не используется в рационе, то х1=0; в противном случае x
1 0. Аналогично имеем х2 0. То есть должно выполняться условие
неотрицательности переменных: х1 0, х2 0.
Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому
общую стоимость рациона можно выразить в виде линейной функции Z = 4х1
+ 6х2 (коп.)
Требуется найти такие х1 и х2, при которых функция Z
принимает минимальное. Таким образом, необходимо найти минимальное значение
линейной функции Z = 4х1 + 6х2 при ограничениях
3х1 + х2 9
х1 + 2х2 8
х1 + 6х2 12
х1 0, х2 0.
Построим многоугольник решений (рис. 2.4). Для этого в системе координат х1
Ох2 на плоскости изобразим граничные прямые
3х1 + х2 = 9 (L1)
х1 + 2х2 = 8 (L2)
х1 + 6х2 = 12 (L3)
х1 = 0, х2 = 0.
Взяв какую-нибудь точку, например, начало координат, установим, какую
полуплоскость определяет соответствующее неравенство (эти полуплоскости на
рис. 2.4 показаны стрелками). В результате получим неограниченную
многоугольную область с угловыми точками А, В, С, D.
Для построения прямой 4х1 + 6х2 = 0 строим радиус-вектор N
= (4;6) и через точку O проводим прямую, перпендикулярную ему. Построенную
прямую Z = 0 перемещаем параллельно самой себе в направлении вектора N. Из
риc. 2.4 следует, она впервые коснется многогранника решений и станет опорной
по отношению к нему в угловой точе В. Если прямую перемещать дальше в
направлении вектора N, то значения линейной функции на многограннике решений
возрастут, значит, в точке В линейная функция Z принимает минимальное значение.
Точка В лежит на пересечении прямых L1 и L2. Для
определения ее координат решим систему уравнений
3x1 + х2 = 9
х1 + 2х2 = 8
Имеем: х1 = 2; х2 = 3. Подставляя значения х1 и
х2 в линейную функцию, получаем Zmin = 4 2 + 6 3 = 26.
Таким образом, для того, чтобы обеспечить минимум затрат (26 коп. в день),
необходимо дневной рацион составить из 2 кг корма 1 и 3 кг корма 2.
2.2. Обобщение графического метода решения задач линейного
программирования.
Вообще, с помощью графического метода может быть ре-шена задача линейного
программирования, система ограниче-ний которой содержит n неизвестных и m
линейно независи-мых уравнений, если N и M связаны соотношением N – M = 2.
Действительно, пусть поставлена задача линейного программирования.
Найти минимальное значение линейной функции Z = С1х1+С
2х2+... +СNxN при ограничениях
a11x1 + a22x2 + ... + a1NХN = b1
(2.3) a21x1 + a22x2 + ... + a2NХN = b2
. . . . . . . . . . . . . . .
aМ1x1 + aМ2x2 + ... + aМNХN = bМ
xj 0 (j = 1, 2, ..., N)
где все уравнения линейно независимы и выполняется cоотношение N - M = 2.
Используя метод Жордана-Гаусса, производим M исключений, в результате которых
базисными неизвестными оказались, например, M первых неизвестных х1,
х2, ..., хM, а свободными - два последних: хМ+1
, и хN, т. е. система ограничений приняла вид
x1 + a1,М+1xМ+1 + a1NХN = b1
(2.4) x2 + a2,М+1xМ+1 + a2NХN = b2
. . . . . . . . . . . .
xМ + aМ, М+1x2 + aМNХN = bМ
xj 0 (j = 1, 2, ..., N)
С помощью уравнений преобразованной системы выражаем линейную функцию только
через свободные неизвестные и, учитывая, что все базисные неизвестные -
неотрицательные: хj 0 (j = 1, 2, ..., M), отбрасываем их, переходя к
системе ограничений, выраженных в виде неравенств. Таким образом, окончательно
получаем следующую задачу.
Найти минимальное значение линейной функции Z = СМ+1хМ+1+СNxN при ограничениях
a1,М+1xМ+1 + a1NХN b1
a2,М+1xМ+1 + a2NХN b2
. . . . . . . . . .
aМ,М+1xМ+1 + aМNХN bМ
xМ+1 0, хN 0
Преобразованная задача содержит два неизвестных; решая ее графическим методом,
находим оптимальные значения xМ+1 и хN, а затем,
подставляя их в (2.4), находим оптимальные значения х1, х2
, ..., хM.
Пример.
Графическим методом найти оптимальный план задачи ли-нейного программирования,
при котором линейная функция Z = 2х1 - х2 + х3
- 3х4 + 4х5 достигает максимального значения при
ограничениях
х1 - х2 + 3х3 - 18х4 + 2х5 = -4
2х1 - х2 + 4х3 - 21х4 + 4х5 = 2
3х1 - 2х2 + 8х3 - 43х4 + 11х5 = 38
xj 0 (j = 1, 2, ..., 5)
Решение.
Используя метод Жордана-Гаусса, произведем три полных исключения неизвестных х
1, х2, х3. В результате приходим к системе
х1 + х4 - 3х5 = 6
х2 + 7х4 + 10х5 = 70
х3 - 4х4 + 5х5 = 20
Откуда x1 = 6 – х4 + 3x5, х2 = 70 – 7х4-10х5, х3 = 20 + 4х4 -5х5.
Подставляя эти значения в функцию и отбрасывая в системе базисные переменные,
получаем задачу, выраженную только через свободные переменные х4 и х
5: найти максимальное значение линейной функции Z = 6х4 + 15х
5 – 38 при ограничениях
х4 - х5 6
7х4 + 10х5 70
- 4х4 + 5х5 20
х4 0, х5 0.
Построим многогранник решений и линейную функцию в системе координат х4
Ох5 (рис. 2.5). Из рис. 2.5 заключаем, что линейная функция принимает
максимальное значение в угловой точке В, которая лежит на пересечении прямых 2
и 3. В результате решения системы
7х4 + 10х5 = 70
- 4х4 + 5х5 = 20
-
находим: х4 = 2, х5 = 28/5. Максимальное значение функции
Zmax = -38 + 12 + 84 = 58.
Для отыскания оптимального плана исходной задачи подставляем найденные значения
х4 и х5. Окончательно получаем: х1 = 104/5, х
2 = 0, х3 = 0, х4 = 2, х5 = 28/5.
ЛИТЕРАТУРА
1. Математические методы анализа экономики /под ред. А.Я.Боярского.
М.,Изд-во Моск. Ун-та, 1983
2. А.И.Ларионов, Т.И.Юрченко “Экономико-математические методы в
планировании: Учебник – М.: Высш.школа, 1984
3. Ашманов С.А. “Линейное программирование”,- М.: 1961
Страницы: 1, 2
| 
