Линейное программирование

Размещено на http://www.allbest.ru/

Цель работы: Освоение графического метода решение задач ЛП. Освоение понятий ЛП и идей целочисленного программирования. Экономическая интерпретация понятий ЛП.

Задача максимизации целевой функции

Задача 1

Таблица 1

Фирма производит изделия двух видов 1 и 2. На производство изделия 1 требуется а11 = 7,2 чел.-час, изделия 2 а21 = 5,6 чел.-час. Издержки производства составляют а12 = 5,6 тыс. руб и а22 = 3,5 тыс. руб, прибыль -- с1 = 1,95 тыс. руб и с2 = 1,65 тыс. руб соответственно.

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

Составим область ограничений

7,2x1 + 5,6x2 < 290;

5,6x1 + 3,5x2 < 210;

x1 > 12;

x2 > 14;

x1,2 > 0;

Составим целевую функцию.

Недельная прибыль фирмы L= 1,95x1 + 1,65x2 > max

Построим график оптимизационной задачи (Рис. 1.):

7,2x1 + 5,6x2 = 290 5,6x1 + 3,5x2 = 210

Координаты вектора-градиента q (1,95; 1,65)

Рассчитаем координаты вершин полученного четырёхугольника:

Вершина А (12;36,3)

7,2x1 + 5,6x2 = 290; 5,6x2 = 290 - 86,4; x2 = 36,3.

x1 = 12; x2 = 203,6/5,6;

Вершина B (26,1; 18,2)

7,2x1 + 5,6x2 = 290; x1 = 26,1;

5,6x1 + 3,5x2 = 210; x2 = 18,2.

Вершина C (28,7; 14)

5,6x1 + 3,5x2 = 210; 5,6x1 = 210 - 49; x1 = 28,7;

X2 = 14; 5,6x1 = 161;

Вершина D (12; 14)

Дробные значения округляем в меньшую сторону.

Подставим координаты вершин в целевую функцию и составим таблицу:

L= 1,95x1 + 1,65x2 > max

LA= 1,95*12 + 1,65*36 = 23,4 + 59,4 = 82,8.

LB= 1,95*26 + 1,65*18 = 50,7 + 29,7 = 80,4.

LC= 1,95*28 + 1,65*14 = 54,6 + 23,1 = 77,7.

LD= 1,95*12 + 1,65*14 = 23,4 + 23,1 = 46,5.

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

Таблица 2

Сравнивая значения целевой функции в последней колонке табл. 2, можно сделать вывод, что оптимальным является план 1 (вершина А многоугольника допустимых решений), предполагающий производство 12 изделий 1 и 36 изделий 2. Ему отвечает наибольшая прогнозируемая прибыль 82,8 тыс. руб. План (программа) производства 2 обладает несколько худшими характеристиками: при его реализации прибыль составит 80,4 тыс. руб.

Другим способом выбора оптимального решения является графический метод. На том же рис. 1 строим прямую, отвечающую нулевому значению целевой функции Ц = 0. Приравнивая нулю выражение для целевой функции Ц = 1,95х1 + 1,65х2, получаем:

х2 = 1,18

Это прямая, проходящая через начало координат и имеющая отрицательный наклон к оси Ох1. Другим значениям целевой функции также соответствуют прямые, параллельные прямой Ц = 0, причем по мере их “смещения” относительно исходной прямой Ц = 0 в направлении стрелки значения целевой функции будут увеличиваться. Крайняя прямая, касающаяся многоугольника допустимых решений в вершине А, соответствует значению целевой функции Ц = 82,8 тыс. руб.

Дальнейшие вычисления сводятся к расчету координат вершины А, отвечающей оптимальному плану производства, т.е. к решению системы уравнений

7,2x1 + 5,6x2 = 290

x2 = 12

Координаты вершины. А: х1 = 12; х2 = 36 интерпретируются как план производства изделий 1 и 2.

Ответ. Оптимальным является план производства 12 изделий вида 1 и 36,3изделий вида 2. Ему отвечает наибольшая прогнозируемая прибыль 82,8 тыс. руб.

Задача минимизации целевой функции

На три стройки (W1, W2, W3) необходимо поставить кирпич, причем имеется возможность поставок с двух заводов (F1, F2). Потребности строек в кирпиче wj, возможности поставок с каждого завода fi и издержки перевозок кирпича автомашинами c i-го завода на j-ю стройку cij указаны в табл. 3.

Исходные данные задачи (издержки перевозок cij, потребности wj, мощности поставок fi)

Таблица 3

Составим таблицу перевозок

Обозначим через y1 количество автомашин кирпича, доставляемого с завода F1 на стройку W1, а через y2 количество автомашин кирпича, доставляемого с завода F1 на стройку W2. Поскольку общая потребность строек в кирпиче задана, а также задано количество автомашин кирпича, которые может отгрузить каждый завод, то можно от трехмерной задачи перейти к двумерной, выразив количество автомашин кирпича, отгружаемого с завода F1 на третью стройку W3, а также количество автомашин кирпича, отгружаемого с завода F2 на все три стройки, через введенные переменные y1 и y2. Тогда таблица перевозок будет выглядеть следующим образом (табл. 4).

Таблица 4.

Таблица перевозок

Обозначим через nij число автомашин, перевозящих кирпич с i-го завода на j-ю стройку. Тогда целевая функция D транспортные издержки выразится формулой

D =

Подставив вместо сij и nij их значения из табл. 3, 4, получаем:

D = 5,5y1 + 4,2y2 + 3[11 (y1 + y2)] + 3(6 y1) + 2,5(10 y2) + 4{10 [11 (y1 + y2)]} = =5,5y1+ 4,2y2+33-3y1-3y2+ 18-3y1+ 25-2,5y2+ 40-44+4y1+4y2= =3,5 y1+2,7 y2+72

Ограничения следуют из того, что все числа в ячейках таблицы перевозок (табл. 4) не должны быть меньше нуля, т. е. имеем следующие шесть неравенств:

y1 0;

y2 0;

11 (y1 + y2) 0;

6 y1 0;

10 y2 0;

10 [11 (y1 + y2)] 0.

Преобразовав неравенства-ограничения, получаем:

y1 0;

y2 0;

y1 + y2 11;

y1 6;

y2 10;

y1 + y2 1.

Теперь задача сводится к двумерной и формулируется следующим образом: найти вершину (или точку) области допустимых решений, заданной системой неравенств-ограничений

6 y1 0;

10 y2 0;

y1 + y2 11;

y1 + y2 1,

для которой целевая функция D = 3,5 y1+2,7 y2+72

достигает минимального значения.

Построим график задачи оптимизации перевозок (рис. 2)

y1 + y2 = 11 y1 + y2 = 1

Из выражения для целевой функции D = 3,5 y1+2,7 y2+72 получаем координаты вектора-градиента:

q (1,95; 1,65)

Это прямая, проходящая через начало координат и совпадающая с осью Оу2. Другим значениям целевой функции также соответствуют прямые, параллельные вектору q, причем по мере их “смещения” относительно исходного вектора q в направлении стрелки значения целевой функции будут увеличиваться. Крайняя прямая, касающаяся многоугольника допустимых решений в вершине А с координатами у1 = 0; у2 = 1, соответствует минимальному значению целевой функции D = 74,7 тыс. руб.

Вершина А (0; 1)

ZA = 3.5* 0 + 2.7*1 + 72 = 74,7 (тыс. руб.)

1) Подставляя значения у1 = 0; у2 = 1 в ячейки табл. 4, получаем оптимальный план перевозок (табл. 5).

Таблица 5

Оптимальный план перевозок

Ответ. Оптимальным является план перевозок, указанные в табл. 5. Ему отвечают наименьшие транспортные издержки 74,7тыс. руб.

Список используемой литературы:

1. Исследование операций в экономике: Учебн. пособие для вузов / Н.Ш. Кремер и др.; Под ред. Н.Ш. Кремер. -- М.: Банки и биржи, ЮНИТИ, 1999. -- 407 с.

2. Экономико-математические методы и прикладные модели: Учебн. пособие для вузов / В.В. Федосеев и др.; Под ред. В.В. Федосеева. -- М.: ЮНИТИ, 1999. -- 391 с.

3. Багриновский К.А., Матюшок В.М. Экономико-математические методы и модели (микроэкономика): Учебн. пособие. -- М.: Изд-во РУДН, 1999. -- 183 с.

4. Плис А.И., Сливина Н.А. Mathcad: Математический практикум для экономистов и инженеров: Учеб. пособие. М.: Финансы и статистика, 1999. 656 с.

5. Тернер Д. Вероятность, статистика и исследование операций. М.: Статистика, 1976. 431 с.

6. Томас Р. Количественные методы анализа хозяйственной деятельности. -- М.: "Дело и Сервис", 1999. -- 432 с.

7. Хазанова Л.Э. Математическое моделирование в экономике: Учебн. пособие. -- М.: Изд-во "Бек", 1998. -- 141 с.

линейное программирование прибыль производство

Размещено на Allbest.ru