Модуль 15. Элементы линейного программирования.

Содержание модуля.

Тема 15. 1. Элементы линейного программирования. Постановка основной задачи линейного программирования и ее геометрическая интерпретация. Сведение основной задачи к канонической форме.

Методические указания по его изучению.

После изучения по учебникам теоретического материала разберите реше-

ние примера 37.

Пример 37. На фабрике для производства двух видов продукции используется три вида сырья. Оно имеется в следующих количествах: 52 единицы сырья первого вида, 30 единиц сырья второго вида и 24 единицы сырья третьего вида. На производство единицы продукции первого вида

нужно израсходовать (2; 0; 2) единиц указанных видов сырья, а для второго вида продукции эти показатели равны (4; 3; 0) (нуль означает, что данное сырье не требуется для изготовления данного вида продукции). Прибыль, получаемая фабрикой от реализации единицы первого вида продукции, равна трем условным единицам, а от реализации единицы второго

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

Решение. Пусть производится х единиц продукции первого вида и у единиц продукции второго вида. Для этого потребуется (2 х + 4 у) единиц сырья первого вида, 3 у единиц сырья второго вида и 2 х единиц сырья третьего вида.

Из условия задачи следует:

или (1)

 

Прибыль, которая будет получена от реализации произведенной продукции, равна Р = 3 х + 5 у. Требуется найти такое решение системы (1), при котором функция Р принимает наибольшее значение. По условию задачи х ³ 0 и у ³ 0.

Решим задачу графическим методом.

y

 

D C

 

 

B

 

l

 

O A x

 

 

Рис. 9

В прямоугольной системе координат хОу построим многоугольник ОАВСD, образованный прямыми х = 0 (ОD), х = 12 (АВ), у = 0

(ОА), у = 10 (СD), х + 2 у =26 (ВС) и прямую 3 х + 5 у = 0 (l)

(рис. 9).

Значения х и у, удовлетворяющие системе неравенств (1), являются координатами точек, лежащих внутри или на границе пятиугольника ОАВСD.

Так как прямые (l) и ВС не параллельны, то для нахождения решения системы (1), для которого функция Р = 3 х + 5 у принимает наибольшее значение, достаточно найти значения этой функции в точках О, А, В, С, D и из полученных чисел выбрать наибольшее.

В нашей задаче эти точки имеют следующие координаты: O (0; 0), A (12; 0), B (12; 7), C (6; 10), D (0; 10). Подставляя координаты этих

точек в правую часть равенства Р = 3 х + 5 у, получим:

Р (А) = Р (12; 0) = 36, Р (В) = Р (12; 7) = 71, Р (С) = Р (6; 10) = 68,

Р (D) = Р (0; 10) = 50, Р (О) = Р (0; 0) =0.

Следовательно, Р_max = Р (12; 7) = 71. Значит, фабрике следует производить 12 единиц продукции первого вида и 7 единиц продукции второго вида. В этом случае прибыль от реализации произведенной продукции составит 71 условную единицу.

Вопросы для самоконтроля.

1. Сформулируйте основную задачу линейного программирования.

2. В чем сущность геометрического метода решения основной задачи линейного программирования.

2. 15. 4. Задания для самостоятельной работы.

1. Найти неотрицательное решение системы неравенств

.

2. Предприятию требуется не более 10 трехтонных автомобилей и не более 8 пятитонных. Отпускная цена трехтонного автомобиля – 3000 у.е., пятитонного – 4000 у. е. Предприятие может выделить для приобретения автомашин 50 тыс. у. е. Сколько нужно приобрести автомашин каждой марки, чтобы их суммарная грузоподъемность была максимальной?

 

 

Раздел 3. ЗАДАНИЯ ДЛЯ КОНТРОЛЬНЫХ РАБОТ И