84342 (Линейное программирование: постановка задач и графическое решение), страница 2
Описание файла
Документ из архива "Линейное программирование: постановка задач и графическое решение", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "84342"
Текст 2 страницы из документа "84342"
Задача использования сырья. Для изготовления двух видов продукции Р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. Для определения ее координат решим систему уравнений
8 x1 + 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; в противном случае x1 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.
-
Обобщение графического метода решения задач линейного программирования.
Вообще, с помощью графического метода может быть ре-шена задача линейного программирования, система ограниче-ний которой содержит 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.