Меню

Ремонтный завод хоперский выпускает насосы двух типов

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

Лабораторная работа № 1.

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

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

Представить условие задачи в виде таблицы. Составить математическую модель задачи. Привести математическую модель задачи к каноническому виду.

Вариант 1.Предприятие производит совковые и штыковые лопаты. Для их изготовления требуется листовой металл и древесина. Для изготовления одной совковой лопаты требуется 0,04 листа металла и 0,004 м 3 древесины, для изготовления одной штыковой лопаты — 0,02 листа металла и 0,004 м 3 древесины. Розничная цена одной совковой лопаты 60 руб., а штыковой — 50 руб. Изучение рынка сбыта показало, что спрос на штыковые лопаты превышает спрос на совковые не более чем на 3 тыс. штук в месяц. Кроме того, спрос на совковые лопаты не превышает 15 тыс. штук в месяц. Сколько лопат каждого вида должно изготовлять предприятие в месяц, если оно располагает 300 листами металла и 60 м 3 древесины и хочет получить максимальный доход от реализации своей продукции?

Вариант 2.Предприятие выпускает 4,5-тонные прицепы и кормораздатчики по цене 40,3 и 74,3 тыс. руб. соответственно. По результатам маркетинговых исследований спрос на изделия первого вида составляет не менее 1 200 ед. в год. Для производства прицепов используются сталь и чугун, запасы которых на предприятии составляют 25 000 и 4 500 т соответственно. Для изготовления 1 тыс. прицепов норма расхода стали составляет 1 615 т, а чугуна — 385 т. Для изготовления 1 тыс. кормораздатчиков расходуется: стали — 2 022 т, чугуна — 478 т. Найти оптимальное решение по производству прицепов и кормораздатчиков, чтобы выручка от выпускаемых изделий была максимальной.

Вариант 3.Ремонтный завод выпускает насосы двух типов: топливные и водяные. В комплектацию этих изделий входят четыре основных вида деталей: корпус, платик, манжета, шестерня. Для изготовления топливного насоса требуется один корпус, четыре платика, четыре манжеты и одна шестерня, для изготовления водяного насоса — 1, 2, 4 и 3 комплектующих деталей соответственно. От реализации одного топливного насоса завод имеет прибыль 50 руб., а от одного водяного — 200 руб. На складе завода имеется следующий запас комплектующих: корпусов — 6 штук, платиков — 8 штук, манжет — 12 штук, шестерней — 9 штук. Составить план производства, обеспечивающий заводу наибольший доход.

Вариант 4. Для производства двух видов кормовых биодобавок можно использовать витамины трех групп. При этом на изготовление биодобавки № 1 расходуется 16 кг витамина А, 8 кг витамина В1 и 5 кг витамина Е. На изготовление биодобавки № 2 расходуется 4 кг витамина А, 7 кг витамина В1 и 9 кг витамина Е. На складе фирмы имеется всего 784 кг витамина А, 552 кг витамина В1 и 567 кг витамина Е. От реализации добавки № 1 фирма имеет прибыль 4 тыс. руб., а от добавки № 2 — 7,2 тыс. руб. Определить максимальную прибыль от реализации обеих биодобавок.

Вариант 5.Фирма выпускает два набора удобрений «Купрум-I» и «Купрум-II». В «Купрум-I» входит 3 кг азотных, 1 кг калийных и 1 кг медных удобрений. В «Купрум-II» — 1 кг азотных, 2 кг калийных и 6 кг медных удобрений. После осушения торфяных болот для внесения в почву потребовалось по меньшей мере 9 кг азотных, 8 кг калийных и 12 кг медных удобрений. «Купрум-I» стоит 4 усл. ден. ед., а «Купрум-II» — 6 усл. ден. ед. Какие и сколько наборов удобрений необходимо внести, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Лабораторная работа № 2.

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

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

Номер варианта
Задание
Номер варианта
Задание

Задание 2.Графическим методом найти решение задачи линейного программирования.

Источник статьи: http://poisk-ru.ru/s2525t11.html

Практическая работа по математическим методам в экономике для СДО Прометей

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

Предприятие может приобрести не более 15 трехтонных автомашин и не более 10 пятитонных. Отпускная цена трехтонного грузовика — 4000 тыс. руб., пятитонного – 5000 тыс. руб. Предприятие может выделить для приобретения автомашин 100000 тысяч рублей.

  1. Построить экономико-математическую модель задачи линейного программирования.
  2. С помощью графического метода решения определить, сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной.

Предприятие выпускает два вида продукции. На изготовление единицы первого изделия требуется затратить 2 кг сырья первого типа, 3 кг сырья второго типа и 5 кг сырья третьего типа. На изготовление единицы второго изделия требуется затратить 7 кг сырья первого типа, 3 кг сырья второго типа и 1 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве 560 кг, 300 кг и 332 кг соответственно. Рыночная стоимость единицы продукции первого вида составляет 55 тыс. руб., а единицы продукции второго вида – 35 тыс. руб.

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

На предприятии имеются запасы сырья для производства деталей двух видов ДI и Д2, содержащие материалы трех типов В1, В2, и В3. Потребности каждого типа материала на одну деталь представлены в таблице:

Стоимость 1 ед. детали Д1 равна 12 руб., стоимость 1 ед. детали Д2 равна 15 руб.

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

Ремонтный завод выпускает насосы двух типов: топливные и водяные. В комплектацию этих изделий входят четыре основных вида деталей: корпус, платик, манжета, шестерня. Для изготовления топливного насоса требуется один корпус, четыре платика, четыре манжеты и одна шестерня, для изготовления водяного насоса — 1, 2, 4 и 3 комплектующих деталей, соответственно.

От реализации одного топливного насоса завод имеет прибыль 500 руб., а от одного водяного — 2000 руб. На складе завода имеется следующий запас комплектующих: корпусов — 6 шт; платиков — 8 шт; манжет — 12 шт; шестерней — 9 шт.

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

Источник статьи: http://the-distance.ru/prakticheskaya-rabota-po-matematicheskim-metodam-v-ekonomike-dlya-sdo-prometej/

Введение в линейное программирование

Формулировка общего задания линейного программирования. Особенность применения графического метода при решении транспортной задачи. Реализация алгоритма симплекс-метода на языке паскаль. Сущность модульно-рейтинговой системы контроля успеваемости.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

найдем координаты указанной точки — (6,625; 9,625). Следовательно,

Пример 2. Найти значения переменных, при которых целевая функция L(X) = 5x2 принимает экстремальные значения при условии, что:

Введем на плоскости прямоугольную систему координат Ox1x2.

1. Начнем с нахождения значения переменных х1 и х2, при которых целевая функция принимает максимальное значение.

Построим граничные прямые

7x1 + 12x2 = 84, 35x1 — 12x2 = 0, 7x1 — 62 = 42.

Первую прямую построим по точкам пересечения с осями: (12; 0) и (0; 7). Вторую — по точкам (0; 0) и (3; 8). Третью прямую построим по точкам (6; 0) и, например, (10; 4).

Теперь определим соответствующие полуплоскости. Для определения полуплоскости, задаваемой неравенством 7x1 + 12x284, подставляем координаты точки (0; 0) в данное неравенство. Они ему удовлетворяют: 7·0 + 12·084. Следовательно, геометрическим местом точек, координаты которых удовлетворяют данному неравенству, является полу-плоскость, содержащая точку (0; 0). Для определения полуплоскости, задаваемой неравенством 35x1 — 12x20, подставляем координаты, например, точки (-1; 0) в данное неравенство. Они ему не удовлетворяют: 35 ·(-1) — 2·0 0. Следовательно, геометрическим местом точек, координаты которых удовлетворяют данному неравенству, является полуплоскость, не содержащая точку (-1; 0). Аналогично определяем полуплоскость, задаваемую неравенством 7x1 — 6242.

С учетом условий x10, x20 находим пересечение полученных полуплоскостей. Им является изображенный на рис. 10 четырехугольник OABD. Этот четырехугольник и есть искомая ОДР. Вершина A(2; 5) определяется как пересечение граничных прямых 7x1 + 12x2 = 84 и 35x1 — 12x2 = 0, B(8; 2) — как пересечение 7x1 + 12x2 = 84 и 7x1 — 6x2 = 42, D(6; 0) — пересечение прямой 7x1 — 62 = 42 и оси Ox1.

Шаг 3. Проводим линию уровня L0 .

Линия уровня задается уравнением 5x2 = const. На рис. 10 построена линия уровня, соответствующая значению 15.

Шаг 4. Перемещаем L0 по направлению вектора . Результатом такого перемещения является прямая L0+. На ней находится точка A. Следовательно, она и является точкой максимума.

2. Теперь найдем значения переменных x1, x2, при которых целевая функция минимизируется. Шаги 1—3 те же, что и в максимизационной задаче. Поэтому начинаем с шага 4.

Шаг 4. Перемещаем линию уровня в направлении, противоположном вектору . Из Рис. 10 видно, что наименьшее значение L(X ) на ОДР достигается на отрезке OD.

Шаг 5. Поэтому (0; 0), (6; 0) — оптимальные решения соответственно в угловых точках O и D области допустимых решений. Тогда общее решение опт=(1 — л)(0; 0) + + л(6; 0) = (0; 0) + (6л; 0) = (6л; 0), где 0л1. При этом Lmin= 0.

Пример 3. Найти значения переменных, при которых функция L(X) = 5,2x1 — x2 принимает экстремальные значения при условии, что:

Введем на плоскости прямоугольную систему координат Ox1x2.

1. Начнем с решения с максимизационной задачи.

Сначала построим граничные прямые (по точкам их пересечения с координатными осями):

2x1 + 5x2 = 10 по точкам (5; 0),(0; 2),

x1 — 3x2 = 3 по точкам (3; 0),(0; -1),

x1 + x2 = 1 по точкам (-1; 0),(0; 1).

Затем, используя точку О(0; 0), определим соответствующие полуплоскости (Рис. 11). Пересечением полученных полуплоскостей является неограниченная многогранная область, изображенная на рис. 11. Это и есть искомая ОДР, так как полученная область располагается в первой четверти плоскости Ox1x2.

Шаг 3. Проводим линию уровня L0 таким образом, чтобы она имела с ОДР общие точки.

Шаг 4—5. Перемещаем L0 по направлению вектора до линии уровня, которая являлась бы границей полуплоскости, целиком содержащей ОДР. Однако закончить указанное перемещение невозможно. Из рис. 11 видно, что какую бы линию уровня в направлении вектора нормали ни провести (штрихованные прямые на чертеже), любая из них пересекает ОДР. Следовательно, Lmax= +?. Это означает, что задача на максимум неразрешима.

2. Теперь найдем значения переменных, при которых целевая функция минимизируется. Шаги 1—3 точно те же, что и при решении максимизационной задачи.

Шаг 4. Перемещаем линию уровня L0 в направлении, противоположном вектору , до линии, являющейся границей полуплоскости, целиком содержащей ОДР. Такой линией является прямая L0-, проходящая через точку В. Следовательно, Lmin = L(B).

Шаг 5. Координаты точки В определяются как пересечение прямых 2x1 + 5x2 = 10 и —x1 + x2 = 1. Решая соответствующую систему уравнений, найдем координаты точки В: x1=5/7 и x2=12/7. Таким образом, Lmin = 5,2 · 5/7 — — 12/7 = 2.

3. Применение графического метода при решении транспортной задачи

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

Пример 4. а) Найти значения переменных, при которых функция L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 принимает экстремальные значения при условии, что:

б) Интерпретируя переменные и константы, входящие в указанные математические модели, в соответствии с вариантами примера 1 из § 1, дать экономическую характеристику полученных решений.

Решение. а) Введем новые переменные u1, u2, положив u1 = x11, u2 = x12, и выразим через них остальные. Получим x13 = — u1 — u2 + 110, x21 = — u1 + 60, x22 = — u2 + 80, x23 = 70 — x13 = 70 — (- u1 — u2 + 110) = u1 + u2 — 40. Соответственно L(X) = L(U) = 4u1 + 8u2 + 9(- u1-u2 +110) + 7(- u1 + 60) + 3(- u2 + 80) + 5(u1 + u2 — 40) = -7u1 + u2 + 1 450.

Тогда с учетом неотрицательности переменных xij для i, j= 1, 2, 3, формулировка исходной задачи приобретает следующий вид:

Для решения задачи с такой формулировкой применим графический метод. Введем на плоскости прямоугольную систему координат Ou1u2 и построим ОДР данной задачи аналогично тому, как это было сделано в примере 1. Ограничительные условия определяют на плоскости многоугольник ABDEFG (Рис. 12), вершины которого имеют соответственно координаты: (0; 40), (0; 80), (30; 80), (60; 50), (60; 0), (40; 0). Строим вектор (-7; 1). Проводим линию уровня L0. Она задается уравнением 7u1 + u2 + 1 450=const. На Рис. 12 построена линия уровня, соответствующая значению 1 450. Сначала найдем значения переменных u1, u2, при которых целевая функция принимает минимальное значение. Поэтому перемещаем L0 в направлении, противоположном вектору . Точкой выхода из ABDEFG является точка F. Следовательно, наименьшее значение функции L(U) на ОДР достигается при u1 = 60, u2 = 0. Поэтому Lmin= -7·60 + + 0 + 1 450 = 1 030. Теперь найдем значения переменных u1, u2, при которых функция L(U) принимает максимальное значение. Перемещаем L0 по направлению вектора . При таком перемещении точкой выхода из шестиугольника ABDEFG является точка B(0; 80). Следовательно, Lmax=

L(B) = = -7·0 + 80 + 1 450 = 1 530.

б) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины.

Полученный в п.(а) ответ соответствует для варианта 1 оптимальному плану перевозок. Запишем его в виде матрицы

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

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

Полученный в подпункте а ответ соответствует для варианта 2 оптимальному плану временнуй загрузки станков по выполнению каждой операции. Его также (как и для варианта 1) удобно записать в виде матрицы

Экономическая интерпретация полученной матрицы такова:

на первом станке имеет смысл выполнять вторую и третью операции продолжительностью 80 и 30 часов соответственно;

на втором — первую и третью операции продолжительностью 60
и 40 часов соответственно.

При таком плане будет обработано наибольшее количество деталей,
а именно 1 530.

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

При указанной временнуй загрузке станков будет обработано минимальное количество деталей, а именно, 1 030 (разница с оптимальным планом в 500(!) деталей). (Проведите аналогичное исследование для варианта 1, а именно, укажите такой план перевозок, при котором транспортные расходы будут наибольшими.)

4. Решение ЗЛП с тремя переменными

Применение графического метода возможно и при решении ЗЛП, система ограничений которых содержит три переменные. В этом случае описанный выше алгоритм остается в силе, только линии уровня следует заменить на поверхности уровня и учесть, что, если в случае двух переменных экстремальные значения (конечно, при условии их существования) целевой функции достигались в вершинах многоугольника решений в двумерном пространстве, то в случае трех переменных они достигаются в вершинах многогранника решений в трехмерном пространстве.

Напомним, что поверхностью уровня функции f(x1, x2, x3) называется множество всех точек пространства R3, в которых функция принимает некоторое постоянное значение. Согласно этому определению, для целевой функции L(X) = c1x1 + c2x2 + c3x3 + c произвольная поверхность уровня L0 — это плоскость с вектором нормали (c1, c2, c3).

Рассмотрим применение алгоритма на конкретном примере.

Пример 5. Найти значения переменных x1, x2, x3, при которых функция L(X) = 3x1 — x2 + 2x3 принимает экстремальные значения при условии, что:

Решение. Введем в пространстве прямоугольную систему координат Ox1x2x3.

1. Начнем с решения максимизационной задачи.

Построим граничные плоскости x3 = 4 и x1 + 2x2 + x3 = 5. Первая плоскость проходит через точку (0; 0; 4) параллельно плоскости Ox1x2. Уравнение второй плоскости представим уравнением в отрезках: + (это возможно сделать в силу того, что плоскость не проходит через начало координат). Следовательно, означенная плоскость пересекает оси координат в точках (5; 0; 0), (0; ; 0) и (0; 0; 5).

Теперь определим соответствующие полупространства. Подставляем координаты точки (0; 0; 0) в неравенство x3 Они ему удовлетворяют. Следовательно, выбираем полупространство, содержащее указанную точку. Для определения полупространства, задаваемого неравенством x1 + 2x2 + x3, подставляем координаты той же самой точки. Они удовлетворяют и ему. Следовательно, выбираем полупространство, также содержащее начало координат.

С учетом условий x1 ? 0, x2 ? 0, x3 ? 0 находим пересечение полупространств. Им является изображенный на рис. 13 многогранник AOBA1O1B1. Полученный многогранник и есть искомая ОДР.

Шаг 2. Строим вектор (3; -1; 2).

Шаг 3. Проводим поверхность уровня L0. Поверхность уровня задается уравнением 3x1 — x2 + 2x3 = с (с = const). Положим с = 6 и запишем для данного значения с уравнение поверхности уровня в отрезках: +. Следовательно, L0 пересекает оси координат в точках (2; 0; 0), (0; -6; 0) и (0; 0; 3). По этим точкам и построим выбранную поверхность уровня (Рис. 13).

Шаги 4, 5. Перемещаем L0 по направлению вектора . Точкой выхода из ОДР является точка A.

Следовательно, целевая функция имеет максимальное значение в этой точке: Lmax = L(A) = 3 · 5 — 0 + 2 · 0 = 15.

2. Решим минимизационноу задачу. Шаги 1—3 те же, что и при решении соответствующей максимизационной задачи.

Шаги 4, 5. Перемещаем L0 в направлении, противоположном вектору . В этом случае точкой выхода из ОДР является точка B (Рис. 14).

5. Следовательно, Lmin= L(B) = 3 · 0 — + 2 · 0 = -.

5. Применение графического метода при решении экономических задач

Задача 1 (Выбор оптимального рациона питания). Детская молочная кухня в суточный рацион питания для одного трехмесячного ребенка включает два продукта питания: смесь № 5 и В-рис, причем смеси № 5 должно войти в дневной рацион не более 400 г. Стоимость 100 г смеси № 5 составляет 0,7 руб., В-риса — 0,9 руб. Содержание питательных веществ в 100 г продукта, минимальные нормы потребления указаны в таблице 3. Определить оптимальный рацион питания, стоимость которого будет наименьшей.

Решение. Обозначим x1 — суточный объем потребления смеси № 5, кг; x2 суточный объем потребления В-риса, кг.

Составим математическую модель задачи.

Целевая функция будет иметь вид:

ABDE — область допустимых решений (рис. 15). Строим вектор (7; 9). Линия уровня задается уравнением

Перемещаем линию уровня в направлении, противоположном вектору . Точкой выхода L0 из области допустимых решений является точка B, ее координаты определяются как пересечение прямых, заданных уравнениями

Решая систему, получим приближенно координаты точки B(0, 133; 0,321), в которой и будет оптимальное решение, то есть

Таким образом, детская молочная кухня должна в суточный рацион питания для одного трехмесячного ребенка включать 0,133 кг смеси № 5 и 0,321 кг В-риса, при этом стоимость такого рациона составит 3,82 руб.

Задача 2. Фирма, занимающаяся грузовыми перевозками, получила следующий заказ. На двух товарных складах находится сахар в количестве 110 и 100 т, который должен быть доставлен трем оптовым покупателям в количестве 60, 80 и 70 т соответственно. Как следует организовать доставку сахара оптовым покупателям, чтобы суммарный доход от перевозок был максимальным, если доход в условных денежных единицах от каждой перевозки 1 т сахара задан матрицей

Решение. Общий объем запасов на складах совпадает с общим объемом запросов покупателей:

Следовательно, данная задача является закрытой транспортной задачей. Обозначим xij количество сахара (т), поставляемого с i-го (i = 1, 2) склада к j-му (j = 1, 2, 3) покупателю. Тогда соответствующая транспортная задача может быть сформулирована следующим образом.

Максимизировать суммарный доход от перевозок:

Введем новые переменные u1, u2, положив u1 = x11, u2 = x12, и выразим через них остальные. Заметим, что получили транспортную задачу, ограничительные условия которой совпадают с ограничительными условиями примера 4 из п. 3. Поэтому, обратившись к решению этого примера, получим

Ограничительные условия определяют на плоскости многоугольник ABDEFG (рис. 16), вершины которого имеют соответственно координаты: (0; 40), (0; 80), (30; 80), (60; 50), (60; 0), (40; 0). Строим вектор (5; 5). Проводим линию уровня L0. Находим значения переменных u1, u2, при которых целевая функция принимает максимальное значение. Перемещаем L0 в направлении вектора . Из Рис. 16 видно, что максимального значения L(U) достигает в любой точке отрезка DE. Поэтому Lmax= L(D) =
= 5 · 30 + 5 · 80 + 1 240 = 1 790. Задача имеет альтернативный оптимум и ее общее решение находится по формуле:

Полученный ответ запишем в виде матрицы

При таком плане перевозок суммарный доход будет максимальным, а именно Lmax=1?790.

Таким образом, фирма может различными способами организовать доставку сахара покупателям, при которых ее суммарный доход будет максимальным. Укажем некоторые из этих способов:

Первый из этих способов получен при л = 0, второй — при л = 1/3, третий — при л = 0,5, четвертый — при л = 1.

Задача 3. АООТ «Прицеп» выпускает дачный инвентарь, а именно грабли, мотыги и лопаты. При этом для изготовления одного изделия используется сталь-65Г в количестве 1,7, 0,8 и 1,5 кг соответственно. Запасы стали-65Г на складе составляют 1,3 т на месяц. Анализ рынка сбыта показал, что за год АООТ «Прицеп» реализует не более 20 тыс. грабель, 15 тыс. мотыг и 1 тыс. лопат, причем выпуск одного изделия приносит доход 36, 24 и 40 руб. соответственно. Требуется составить план производства, обеспечивающий АООТ «Прицеп» наибольший доход.

Решение. Обозначим через x1, x2 и x3 соответственно количество грабель, мотыг и лопат (шт.), выпускаемых АООТ «Прицеп» в месяц. Составим математическую модель задачи, выразив ограничения сверху по ежемесячному выпуску продукции в целых числах. Для этого поделим 20 000, 15 000 и 1 000 на 12 и округлим до ближайшего целого числа.

Целевая функция имеет вид:

Введем в пространстве прямоугольную систему координат Ox1x2x3. Геометрическое место точек, координаты которых удовлетворяют системе ограничений, т. е. ОДР, образует выпуклый многогранник. Грани этого многогранника расположены на плоскостях, уравнения которых получаются при замене неравенств системы точными равенствами. На рис. 17 изобразим многогранник решений, получающийся в результате как пересечение полупространств, на которые делит пространство каждая из указанных плоскостей. Самой ближней к началу координат пунктиром показана поверхность (линия) уровня L0 = 12 000, и вектор 10, перпендикулярный ей. Вектор 10 изображен вместо вектора для удобства, так как вектор на этом чертеже будет слишком мал. Будем перемещать эту линию уровня в сторону возрастания целевой функции, т. е. по направлению вектора 10. Из взаимного расположения ОДР и линий уровня ясно, что наибольшего значения целевая функция будет достигать в наиболее «выступающих», т. е. удаленных от начала координат точках ОДР: A, B, C или D. Найдем их координаты и значения целевой функции в этих точках. Точка А имеет координаты x1, x2 и x3, удовлетворяющие системе

откуда получаем (в целых числах) x1 = 765 и L1 = 36x1 + 24x2 + 40x3 = 27 540. Аналогично, координаты точки В удовлетворяют системе

откуда x1 = 691 и L2 = 36x1 + 24x2 + 40x3 = 28?196. Координаты точки С удовлетворяют системе

откуда x1 = 103 и L3 = 36x1 + 24x2 + 40x3 = 37 028. Координаты точки D удовлетворяют системе

откуда x1 = 176 и L4 = 36x1 + 24x2 + 40x3 = 36 336. Следовательно, наибольшего значения целевая функция достигает в точке С. Оптимальным будет выпуск (в целых числах) 103 грабель, 1 250 мотыг и 83 лопат в месяц. При этом прибыль составит 37 028 руб. На Рис. 17 изображены поверхности уровня L1 и L3. Поверхности L2 и L4 находятся очень близко к указанным и не изображены, чтобы не загромождать чертеж.

6. Применение графического метода при проведении экономического анализа ЗЛП (на примере задачи регионального уровня)

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

Задача 4. АООТ «Прицеп» выпускает изделия двух типов: задвижки и тиски слесарные. При этом используется сырье четырех видов. Расход сырья задан в таблице 4.

Суточные запасы стали-45 составляют 322 кг, чугуна — 70 кг, бронзы — 180 кг, стали-3 — 100 кг. Розничная цена одной задвижки равна 60 руб., тисков — 100 руб.

По этим исходным данным требуется: составить план производства, обеспечивающий АООТ «Прицеп» наибольшую выручку; выяснить, как влияет на оптимальное решение изменение запасов исходного сырья; а также провести анализ предложенной ситуации по диапазону розничных цен на изделия, при котором не происходит изменения оптимального решения.

Решение. Обозначим через x1 и x2 суточные объемы выпуска задвижек (шт.) и слесарных тисков (шт.) соответственно. Составим математическую модель задачи.

Целевая функция имеет вид:

С учетом этих ограничений сочетание объемов выпуска задвижек и слесарных тисков должно находиться внутри области допустимых решений OABDE (рис. 18), являющейся «плацдармом» для дальнейших действий руководителей АООТ «Прицеп». Для отыскания точки, в которой находится оптимальное решение, строим вектор, показывающий направление самого быстрого изменения целевой функции (это вектор с координатами (60; 100)), и линию уровня L0, перпендикулярную указанному вектору. Перемещая прямую L0 по направлению вектора , найдем точку выхода линии уровня из области допустимых решений. Ею является точка B, координаты которой — (61; 34,75) — определяются как пересечение прямых, заданных уравнениями 3x1 + 4x2 = 322 и 0,5x1 + 3x2 = 100.

Следовательно, Lmax= L(B) = 60 • 61 + 100 • 34,75 = 7 135. Таким образом, АООТ «Прицеп» должно выпускать в сутки 61 задвижку и 34,75 слесарных тисков. С этими данными по выпуску выручка от реализации составит 7 135 руб. Если выпускать в сутки 34,75 тисков нельзя, то этот результат можно интерпретировать так: оптимальным является выпуск 34,75 • 4 = 139 тисков за 4 суток.

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

Рассмотрим увеличение ресурса правой части ограничения 3x1 + 4x2322 по стали-45 (рис. 19).

При перемещении прямой 3x1 + 4x2 = 322 параллельно самой себе до точки F(90; 27,5) — точки пересечения прямых 0,5x1 + 3x2 = 100 и 2x1 = 180 — ограничение x1 + 4x2322 будет оставаться активным, при этом, если АООТ «Прицеп» будет выпускать в сутки 90 задвижек и 27,5 слесарных тисков, величина выручки составит L(90; 27,5) = 8 150 (руб.), что на 1 015 руб. выше реальной выручки. Это может произойти за счет изменения запасов стали-45 (см. описанное выше перемещение прямой 3x1 + 4x2 = 322 до точки F). Для такой выручки предельно допустимый запас стали-45 нужно увеличить до 3 · 90 + 4 · 27,5 = 380 (кг).

Рассмотрим увеличение ресурса правой части ограничения 0,5x1+2x2100 по стали-3 (рис. 20).

При перемещении прямой 0,5x1 + 2x2 = 100 параллельно самой себе до точки G(14; 70) — точки пересечения прямых 3x1 + 4x2 = 322 и x2 = 70 — ограничение 0,5x1 + 2x2100 будет оставаться активным. При этом величина выручки составит L(14; 70) = 7 840 (руб.), что на 705 руб. выше реальной. Это может произойти за счет изменения запасов стали-3 (см. перемещение прямой 0,5x1 + 2x2 = 100 параллельно самой себе до точки G). Для такой выручки предельно допустимый запас стали-3 нужно увеличить до величины 0,5 · 14 + 2 · 70 = 147 (кг).

Рассмотрим возможность изменения правой части пассивного ограничения 2x1 180 по бронзе (Рис. 1). Прямую 2x1 = 180 можно перемещать параллельно самой себе влево, не изменяя величины реального дохода, до точки B(61; 34,75). При этом предельно допустимый суточный запас бронзы можно уменьшить до значения 2 · 61 = 122 (кг).

Теперь рассмотрим возможность изменения правой части пассивного ограничения x2 70 по чугуну (рис. 21). Не изменяя оптимального решения, прямую x2 = 70 можно перемещать параллельно самой себе до точки B(61; 34,75). Это означает, что предельно допустимый суточный запас чугуна можно уменьшать до 34,75 кг.

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

Изменение коэффициентов целевой функции оказывает влияние на наклон линии уровня, уравнение которой записывается в общем виде как c1x1 + c2x2 = const. Оптимальное решение будет оставаться неизменным, если угловой коэффициент k линии уровня, проходящей через точку B, не будет выходить за границы отрезка [k1; k2], где k1 и k2 — угловые коэффициенты прямых BD и AB соответственно.

Рассмотрим изменение коэффициента целевой функции у переменной x1 (коэффициент у x2 оставим без изменения). Имеем -3/4 ? —c1/100 ? -1/4 или 25 ? c1 ? 75.

Таким образом, оптимальное решение не изменится, если розничная цена одной задвижки будет лежать в диапазоне от 25 до 75 руб., в этом случае выручка предприятия составит от 5 000 до 8 050 руб.

Теперь рассмотрим изменение коэффициента целевой функции у переменной x2, оставляя коэффициент у x1 неизменным. В этом случае -3/4 ? -60/c2 ? -1/4, или 80 ? c2 ? 240. Следовательно, оптимальное решение не изменится, если розничная цена одних слесарных тисков будет лежать в диапазоне от 80 до 240 руб. В этом случае выручка АООТ «Прицеп» может составить от 6 440 до 12 000 руб.

7. Упражнения


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


11. АООТ «Прицеп» производит совковые и штыковые лопаты. Для их изготовления требуется листовой металл и древесина. Для изготовления одной совковой лопаты требуется 0,04 листа металла и 0,004 м3 древесины, для изготовления одной штыковой лопаты — 0,02 листа металла
и 0,004 м3 древесины. Розничная цена одной совковой лопаты 60 руб., а штыковой — 50 руб. Изучение рынка сбыта показало, что спрос на штыковые лопаты превышает спрос на совковые не более чем на 3 тыс. штук в месяц. Кроме того, спрос на совковые лопаты не превышает 15 тыс. штук в месяц. Сколько лопат каждого вида должно изготовлять АООТ «Прицеп» в месяц, если оно располагает 300 листами металла и 60 м3 древесины и хочет получить максимальный доход от реализации своей продукции?

12. АООТ «Прицеп» выпускает 4,5-тонные прицепы и кормораздатчики «Ванюша» по цене 40,3 и 74,3 тыс. руб. соответственно. По результатам маркетинговых исследований спрос на изделия первого вида составляет не менее 1 200 ед. в год. Для производства прицепов используются сталь и чугун, запасы которых на предприятии составляют 25 000 и 4 500 т соответственно. Для изготовления 1 тыс. прицепов норма расхода стали составляет 1 615 т, а чугуна — 385 т. Для изготовления 1 тыс. кормораздатчиков расходуется: стали — 2 022 т, чугуна — 478 т. Себестоимость прицепов — 34,66, а кормораздатчиков — 63,9 тыс. руб. Найти оптимальное решение по производству прицепов и кормораздатчиков, чтобы: а) количество выпускаемых изделий было максимальным; б) выручка от выпускаемых изделий была максимальной; в) себестоимость выпускаемых изделий была минимальной.

13. Ремонтный завод «Хоперский» выпускает насосы двух типов: топливные и водяные. В комплектацию этих изделий входят четыре основных вида деталей: корпус, платик, манжета, шестерня. Для изготовления топливного насоса требуется один корпус, четыре платика, четыре манжеты и одна шестерня, для изготовления водяного насоса — 1, 2, 4 и 3 комплектующих деталей соответственно. От реализации одного топливного насоса завод имеет прибыль 50 руб., а от одного водяного — 200 руб. На складе завода имеется следующий запас комплектующих: корпусов — 6 штук, платиков — 8 штук, манжет — 12 штук, шестерней — 9 штук. Составить план производства, обеспечивающий заводу наибольший доход.

14. Провести экономический анализ задач 11—13.

15. Для производства двух видов кормовых биодобавок можно использовать витамины трех групп. При этом на изготовление биодобавки «Телец» расходуется 16 кг витамина А, 8 кг витамина В1 и 5 кг витамина Е. На изготовление биодобавки «Овен» расходуется 4 кг витамина А, 7 кг витамина В1 и 9 кг витамина Е. На складе фирмы имеется всего 784 кг витамина А, 552 кг витамина В1 и 567 кг витамина Е. От реализации добавки «Телец» фирма имеет прибыль 4 тыс. руб., а от добавки «Овен» — 7,2 тыс. руб. Определить максимальную прибыль от реализации обеих биодобавок.

16. Фирма выпускает два набора удобрений «Купрум-I» и «Купрум-II». В «Купрум-I» входит 3 кг азотных, 1 кг калийных и 1 кг медных удобрений. В «Купрум-II» — 1 кг азотных, 2 кг калийных и 6 кг медных удобрений. После осушения торфяных болот для внесения в почву потребовалось по меньшей мере 9 кг азотных, 8 кг калийных и 12 кг медных удобрений. «Купрум-I» стоит 4 усл. ден. ед., а «Купрум-II» — 6 усл. ден. ед. Какие и сколько наборов удобрений необходимо внести, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

17. На участке производства зубчатых колес имеются два станка — зубофрезерный и зубодолбежный. Требуется изготовить три вида зубчатых колес в следующих количествах: первого вида — 80 штук, второго
и третьего — 110 и 140 штук соответственно. Каждое зубчатое колесо может быть изготовлено на любом из станков. Для выпуска одного колеса первого вида на зубофрезерном станке требуется затратить 20 мин, а на зубодолбежном — 34 мин. Для выпуска одного колеса второго вида на зубофрезерном станке требуется затратить 12 мин, а на зубодолбежном — 14 мин. Для выпуска одного колеса третьего вида требуется затратить 10 и 8 мин соответственно. Ресурс работы зубофрезерного станка без смены инструмента (фрезы) позволяет выпустить всего 180 колес, а ресурс работы зубодолбежного станка без смены инструмента (долбяка) позволяет выпустить всего 150 зубчатых колес. Определить оптимальную загрузку станков, обеспечивающую минимальное общее время их работы без смены инструмента.

18. Автотранспортное предприятие получило заказ на укомплектование трех строящихся объектов стройматериалами, производимыми на двух заводах. На первом заводе подготовлено к отправке 120 т стройматериалов, на втором — 180 т. На первый объект необходимо доставить 70 т строительных материалов. Второй и третий объекты нуждаются в получении 140 и 90 т указанного материала. Матрицей задано:

а) доход от перевозки одной тонны стройматериалов с каждого завода к каждому строящемуся объекту;

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

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

б) минимизирующий стоимость.

В ответах на задачи 1—10 приведено только оптимальное значение целевой функции, этого достаточно для проверки.

11.= (4 000; 7 000), Lmax = 590?000 (руб.). 12. а) = (11,688; 0), Lmax= 11,688 (шт.); б) = (1,2; 8,448), Lmax = 676 046,4 (тыс. руб.);

в) = (1,2; 0), Lmin = 41?592 (тыс. руб.). 13. = (0; 3),

Lmax= 600 (руб.). 15. = (27 — 27; 48 + 15), ,

Lmax = 453 600 (руб.). 16. = (2; 3), Lmin = 26 (усл. ден. ед.).

17. На зубофрезерном станке надо выпустить 80 колес первого вида и 100 колес второго вида, а на зубодолбежном — 10 колес второго вида и 140 колес третьего вида, Lmin = 4 060 (мин).

3. Симплексный метод


1. Каноническая задача линейного программирования

Графический метод решения задачи линейного программирования применяется только в случае двух или трех переменных. Симплексный метод (или симплекс-метод) в отличие от него является универсальным, так как позволяет решить общую задачу линейного программирования (ОЗЛП) практически с любым количеством переменных. Но для этого она должна быть приведена к каноническому виду или к канонической задаче линейного программирования (КЗЛП). Множество канонических задач является подмножеством всех задач линейного программирования. Перечислим отличительные черты КЗЛП:

Все ограничения в системе ограничений являются равенствами.

Требование неотрицательности наложено на все переменные, входящие в систему ограничений.

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

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

Всякое условие вида , где s = 1 или 2, или …, или n заменяется условием

Всякое условие вида , где s = 1 или 2, или …, или n заменяется условием

Все переменные xp, на которые не наложены требования неотрицательности, подставляются в равенства, полученные на двух предыдущих шагах, и в целевую функцию в виде xp = wp vp, wp ? 0, vp ? 0.

После преобразований 1—3 все новые переменные удобно обозначить буквой x, пронумеровав их по порядку введения, начиная с номера m + 1. Причем на шаге 3 переменную wp удобно обозначить xp, а vp — буквой x с первым свободным номером. Возможно, за счет введения новых переменных на шаге 3 изменится и целевая функция. Новую целевую функцию обозначим L1(X).

В случае оптимизации вида L1(X)>max воспользуемся равенством max L1(X) = -min(-L1(X)). Поэтому введем новую целевую функцию
(X) = —L1(X), решим задачу при условии (X)>min, после чего сделаем замену max L1(X) = -min(-(X)).

Пример 1. Общая задача линейного программирования

приводится к каноническому виду согласно шагам 1—4.

Теперь обозначим y1 как x4, y2 — x5, w2 — x2, v2 — x6, w3 — x3, v3 — x7. Задача оптимизации при этом примет вид:

Пример 2. Из общей задачи линейного программирования

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

Ясно, что новые переменные можно сразу обозначать буквой x.

Легко показать, что в результате преобразований 1—4 из общей задачи линейного программирования получается каноническая задача, решение которой тесно связано с решением исходной задачи. Действительно, пусть количество переменных при переходе к КЗЛП с n увеличилось до n + t и пусть Z = () — какое-нибудь решение КЗЛП. Ясно, что после отбрасывания из Z последних t компонент, согласно правилу их введения, получается решение исходной задачи линейного программирования. Поскольку в целевую функцию отброшенные компоненты не входят вообще или разность двух из них в точности равна значению некоторой исходной переменной, то значения () и L() равны по модулю. И наоборот, располагая каким-нибудь решением () исходной задачи, можно вычислить и соответствующее решение КЗЛП (), посчитав, согласно правилам ввода, значения недостающих t компонент. Так как выполняется равенство || = |L|, то оптимальное решение Z* КЗЛП Z*= () после отбрасывания последних t компонент даст оптимальное решение исходной задачи: X*= ().

Таким образом, преобразования (1)—(4) приводят к КЗЛП, которую в общем виде можно записать:

Пусть ранг системы линейных уравнений (1) в этой задаче равен r. Это означает, что r переменных этой системы, называемых базисными, могут быть выражены через остальные n + t r переменных, называемых свободными. Напомним, что решение, в котором все свободные переменные равны нулю, а базисные принимают соответствующие неотрицательные значения, называется опорным планом.

В теории линейного программирования доказано, что оптимальное значение целевая функция (3) принимает на множестве опорных планов (решений) КЗЛП, которое конечно. Таким образом, перебрав все опорные решения, можно указать то из них, на котором целевая функция оптимальна. Но даже при небольшом числе переменных, количество опорных планов может быть очень велико, и полный их перебор займет много времени. Идея же симплексного метода, или метода последовательного улучшения плана, заключается в том, что начиная с некоторого исходного опорного решения (плана) осуществляется последовательное целенаправленное перемещение по опорным планам в сторону оптимального значения целевой функции. Не излагая теории симплексного метода, укажем его алгоритм. Сначала рассмотрим алгоритм, применяющийся для расчетов вручную.

2. Жордановы исключения

Поскольку переход от одного опорного плана к другому означает перевод некоторой базисной переменной в свободные, а соответствующей свободной переменной в базисные, рассмотрим отдельно эту процедуру в общем виде и запишем ее алгоритм. Для понимания сути преобразований возьмем систему двух линейных алгебраических уравнений с пятью переменными, имеющую ранг 2. Это означает, что две базисные переменные могут быть выражены через три свободные. Для того, чтобы удобно было следить за перемещением базисной переменной в свободную и наоборот, обозначим свободные переменные x1, x2, x3, а базисные — y1, y2:

Переведем базисную переменную y1 в свободные, а свободную переменную x2 — в базисные, то есть выразим x2, y2 через x1, y1, x3. При этом новую базисную переменную будем писать на месте старой, то есть в первой строке системы, и новую свободную — на месте старой, то есть во втором столбце. Пусть коэффициент a12 при свободной переменной x2 отличен от нуля.

1. Все независимые (свободные) переменные запишем со знаком «-»:

2. Для удобства обозначим —aij = бij:

3. Поделим первую строчку на б12:

4. Выразим из этого уравнения x2:

5. Сделаем преобразования во втором уравнении, заменив в нем x2 на указанное выше выражение:

В результате проделанных шагов 1—5 мы выразили x2, y2 через x1, x3, y1. Причем новые свободные переменные записаны со знаком «-», то есть полученная система

снова готова к описанным преобразованиям типа 3—5. Проделанная процедура называется жордановыми преобразованиями, или исключениями.

Жордановы исключения очень удобно проводить с помощью специальных таблиц. Количество строк в таблице равно количеству базисных переменных (т. е. рангу системы), а количество столбцов — числу свободных переменных. Если справа от знака равенства имеются свободные члены, то появляется еще один столбец и для них. Преобразуются они, очевидно, по тем же правилам, что и остальные коэффициенты. Все клетки исходной таблицы, содержащие числовые величины, делятся по диагонали.

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

В алгоритме жордановых исключений запишем последовательность преобразований коэффициентов системы на шагах 3—5.

Преобразование исходной таблицы (таблица 5):

Разрешающий элемент заменяется обратной величиной и записывается внизу.

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

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

Обозначим буквой в — верхний элемент, буквой н — нижний элемент, буквой k — номер разрешающей строки, буквой s — номер разрешающего столбца. В остальных, не заполненных внизу, клетках таблицы с номерами i,j рассчитывается величина нij = вkjнis. Например, н21 = в11 • н22 =.

Ниже приведена таблица 6 — исходная таблица, для которой выполнены преобразования (1)—(4):

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

Нижние элементы разрешающей строки записываются вверху.

Остальные элементы разрешающего столбца записываются вверху.

В остальных клетках верхние и нижние элементы складываются и записываются вверху.

Выше приведена таблица 7 — новая таблица, в которой выполнены преобразования (1)—(3). Она готова к дальнейшим преобразованиям, то есть снова можно менять местами какие-нибудь базисную и свободную переменные при условии, что соответствующий числовой коэффициент при свободной переменной отличен от нуля. К тому же, если вести заполнение исходной таблицы карандашом, стирая величины, в которых уже нет необходимости, то для всех расчетов можно использовать один и тот же табличный шаблон. Это свойство симплекс-таблиц очень удобно при программировании: все расчеты идут в пределах одного двумерного массива, верхние элементы исходной таблицы представляют собой старые значения коэффициентов (элементов массива), а верхние значения преобразованной таблицы — новые значения коэффициентов с теми же номерами. К этому вопросу мы еще вернемся при рассмотрении программы симплекс-метода.

3. Алгоритм симплекс-метода для расчетов вручную

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

Начало. Общая задача линейного программирования приводится к каноническому виду (1)—(3), то есть путем введения новых дополнительных неотрицательных переменных все неравенства, входящие в математическую модель, превращаются в равенства, а все переменные, на которые не наложены требования неотрицательности, представляются
в виде разности новых неотрицательных переменных. Целевая функция при этом минимизируется. Алгоритм такого перехода изложен выше.

Определяется ранг матрицы A системы уравнений канонической задачи: пусть rank A = k. После этого базисные переменные выражаются через свободные. Как правило, базис образуют вновь введенные переменные, но это не обязательно. Допустим, базис образуют первые k переменных. Выразим их через свободные, записывая, как и при реализации алгоритма жордановых исключений, свободные переменные со знаком «-». Получим систему:

Подставим выражения для базисных переменных в целевую функцию. После этого в ней будут только свободные переменные с некоторыми коэффициентами перед ними. В целевой функции также запишем свободные переменные со знаком «-»:

Для полученной системы и целевой функции составляется таблица для жордановых исключений, т. н. симплекс-таблица (таблица 8):

Источник статьи: http://otherreferats.allbest.ru/programming/00608120_1.html

Читайте также:  Как проверить вакуумный насос ниссан патфайндер
Adblock
detector