Материал: Методы моделирования бизнес-процессов предприятия. методические указания по изучению дисциплины и выполнению лабораторных работ. Амелин С.В

при ограничениях

2x1 +4x2 ≤ 700 ; x1 +5x2 ≤800 ;

3x1 +2x2 ≤ 600.

Ограничения-неравенства в задачах линейного программирования замещают равенствами, введя дополнительные переменные. Тогда, получим

2x1 +4x2 + x3 = 700 ; x1 +5x2 + x4 =800 ;

3x1 + 2x2 + x5 = 600 ,

где х3, х4, х5 - дополнительные переменные.

С учетом последнего положения постановка задачи линейного программирования в канонической форме может быть записана в виде:

найти значения n переменных х1, х2, ... , хп, доставляющие экстремум функции

при условиях

(22)

Кроме того, дополнительно вводится условие неотрицательности всех переменных

(23)

Последнее условие требует, чтобы решение задачи было допустимым, т.е. неотрицательным.

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

Допустимое решение (x1, x2, ..., xп), при котором функция (показатель) F

21

принимает оптимальное (наилучшее) значение, называют оптимальным. Частное решение представленной системы уравнений, получаемое при-

равниванием нулю п из (п + т) переменных, называют базисным. При этом переменные, приравненные нулю, принято называть неосновными, или свободными. Оставшиеся переменные называют основными.

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

Экстремум целевой функции является абсолютным и достигается хотя бы в одной крайней точке многогранника, задающего область определения задачи линейного программирования; данная точка соответствует допустимому базисному решению системы - уравнений ограничений.

Для решения задач линейного программирования в зависимости от их специфики применяют различные методы:

геометрический метод; симплекс-метод; распределительный метод и др.

Геометрический подход к решению задач линейного программирования

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

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

В системе координат (х1, 0, х2) строим график линейной зависимости, полученной переходом от первого неравенства к равенству (рис. 5):

Для построения графика прямой линии достаточно определить координаты двух точек, через которые проходит эта линия. Например, приравнивая х1 к нулю,

получим х2= 175, а придав переменной х1 значение 350, получим х2= 175 – 350/2 = 0. Итак, координаты искомых точек (х1 = 0, х2 = 175) и (х1 = 350,х2 = 0).

По аналогии получаем выражения для двух других линейных зависимостей

22

Рис. 5. Графическая интерпретация решения оптимизационной задачи

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

Затем на том же рисунке (рис. 5) изображаем прямую, полученную с использованием целевой функции для случая F = 0.

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

Координаты данной вершины (точка А) и соответствуют оптимальному решению задачи.

В этой точке пересекаются линии (1) и (3). Решая совместно систему из двух уравнений, соответствующих этим линиям, получаем координаты точкиА:

Вычтем из первого уравнения второе и получим:

0 = 125 – x1

отсюда

x1 = 125.

23

Подставляя найденное значение в одно из уравнений, получим

x2 = 175 – ½ 125

отсюда

x2 = 112,5.

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

F = 8·125 + 6·112,5 = 1675.

Выводы: продукции первого вида должно быть произведено 125 единиц, второго вида – 112,5. Максимальная выручка от реализации продукции составит 1675 ден.ед.

Варианты заданий

Вариант 1. Предприятие, располагающее ресурсами сырья четырех видов А, В, С и D, может производить продукцию двух видов Р1, Р2. Затраты ресурсов на изготовление 1 т продукции, объем ресурсов и прибыль, получаемая от продажи 1 т соответствующей продукции указаны в таблице:

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

Вариант 2. Для изготовления двух видов изделий А и В завод использует в качестве сырья алюминий и медь. На изготовление изделий заняты токарные и фрезерные станки. Исходные данные задачи приведены в таблице:

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

24

Вариант 3. Фирма производит два вида продуктов К1 и К2. Для изготовления продуктов применяются машины А, В, С и D. Время необходимое для изготовления продуктов К1 и К2 на разных машинах, допустимое время использования машин, а также прибыль от продажи продуктов приведены в таблице:

Какое количество каждого продукта необходимо произвести, чтобы прибыль была максимальной?

Вариант 4. Для изготовления двух видов изделий А и В завод использует в качестве сырья алюминий и медь. На изготовление изделий заняты токарные и фрезерные станки. Исходные данные задачи приведены в таблице:

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

Вариант 5. Фирма производит два вида продуктов К1 и К2. Для изготовления продуктов применяются машины А, В, С и D. Время необходимое для изготовления продуктов К1 и К2 на разных машинах, допустимое время использования машин, а также прибыль от продажи продуктов приведены в таблице:

Какое количество каждого продукта необходимо произвести, чтобы прибыль была максимальной?

25