Математическое программирование

20.8. В суточный рацион включают два продукта питания П1 и П2, причем продукта П1 должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта П1 составляет 2 р., про­дукта П2 — 4р. Содержание питательных веществ в 1 ед. про­дукта, минимальные нормы потребления указаны в табл. 20.2.

Определить оптимальный рацион питания, стоимость ко­торого будет наименьшей.

Провести анализ задач с использованием графического ме­тода.

Решение

Обозначим через х1 и х2 количество единиц продуктов П1 и П2 которое войдёт в дневной рацион.

Известно, что стоимость единицы продукта П1 составляет 2 р. и количество этого продукта - х1. Следовательно, стоимость продукта П1 составит 2х1 р. Аналогично, стоимость продукта П2 составит 4х2 р. Учитывая, стоимость продуктов должна быть минимальной, целевая функция задачи будет иметь вид:

Известно также, количество продукта П1, которое должно войти в дневной рацион ограничено. Это обстоятельство в свою очередь необходимо отразить в модели. Имеем ещё одно ограничение:

Естественно, что потребление продуктов П1 и П2 не должно быть отрицательным. Следовательно, в модели должны присутствовать ограничения неотрицательности переменных:

Так же известны минимальные нормы потребления питательных веществ А и В содержащихся в продуктах П1 и П2

Так как в единице продуктов П1 и П2 содержится питательного вещества А 0,2, то всего питательного вещества будет получено . По условию его количество должно быть больше или равно 120, то есть имеем ещё ограничение: .

Аналогичное используя минимальные нормы потребления вещества В получим ограничение

Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:

Построим область допустимых решений, т. е. решим графически систему неравенств.

В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х1=0 и х2=0 совпадают с осями координат. Полуплоскости x1>0,x2>0 лежат соответственно справа от оси Oх2 и выше оси Oх1. Множество точек, удовлетворяющих одновременно неравенствам представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.

Теперь рассмотрим ограничения задачи. Построим по порядку прямые:

x1=200 (а)

0,2x1+0,2x2=120 (б)

0,4x1+0,2x2=160 (в)

И определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют неравенствам:

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

Рассмотрим целевую функцию задачи . 

Построим прямую, отвечающую значению функции : . Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая Z(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (а) и (б), то ее координаты удовлетворяют уравнениям этих прямых:

X1=200
0,2x1+0,2x2=120

Решив систему уравнений, получим: x1 = 200, x2 = 400

Откуда найдем минимальное значение целевой функции:
Р.

Ответ: Для получения минимальной стоимости рациона необходимо в суточный рацион включить 200 ед. продукта П1 и 400 ед. продукта П2 , при этом стоимость будет наименьшей 2000р.

20.11. Обработка деталей А и В может производиться на трех станках, причем каждая деталь должна последовательно об­рабатываться на каждом из станков. Прибыль от реализации детали А — 100 р., детали В — 160 р. Исходные данные при­ведены в табл. 20.4.

Определить производственную программу, максимизирую­щую прибыль при условии: спрос на деталь А - не менее 300 шт., на деталь В — не более 200 шт.

Решение

Обозначим через х1 и х2 объёмы производства соответственно деталей А и В.

Известно, что прибыль от реализации одной детали А составляет 100р. и количество этих деталей - х1. Следовательно, прибыль от реализации деталей А составляет 100х1 р. Аналогично, прибыль от реализации одной детали В составляет 160р. и количество этих деталей – х2. Следовательно, прибыль от реализации деталей В составляет 160х2 р. Учитывая, то, что прибыль должна быть максимальной, целевая функция задачи будет иметь вид:

Так как спрос на деталь А — не менее 300 шт., на деталь В — не более 200 шт., то получим ещё 2 ограничения: .

Естественно, что количество изготовленных деталей А и В не должно быть отрицательным. Следовательно, в модели должны присутствовать ограничения неотрицательности переменных:

Так же известны нормы времени обработки одной детали каждым станком. Так как на первом станке будет обработано х1 деталей А и х2 деталей В, а время работы станка 100 ч., то получим ограничение на время работы первого станка:

Аналогично, получим ограничения на время работы второго и третьего станков: ,

Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:

Построим область допустимых решений, т. е. решим графически систему неравенств.

В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х1=0 и х2=0 совпадают с осями координат. Полуплоскости x1>0, x2>0 лежат соответственно справа от оси Oх2 и выше оси Oх1. Множество точек, удовлетворяющих одновременно неравенствам представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.

Теперь рассмотрим ограничения задачи. Построим по порядку прямые:

(а)

(б)

(в)

(г)

(д)

и определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют неравенствам:

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

Рассмотрим целевую функцию задачи . 

Построим прямую, отвечающую значению функции : . Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая Z(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (д) и (б), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: x1 = 400, x2 = 200

Откуда найдем максимальное значение целевой функции:
Р.

Ответ: Для получения максимальной прибыли необходимо изготавливать 400 деталей типа А и 200 деталей типа В, при этом прибыль будет наибольшей 72000р.

< Предыдущая		Следующая >