Экономико-математические методы и модели

 

Экономико-математические методы и модели

Содержание

Задача №1

Задача №2

Задача №3

Задача №4

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

решение модель выпуск прибыль транспорт

Задача №1

Предприятие выпускает два вида продукции используя три вида ресурсов. Приняты обозначения:

А - матрица норм затрат сырья;

В - запасы ресурсов;

С - прибыль на единицу продукции

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

Решение задачи.

Обозначим через х1 количество единиц продукции первого вида, а через x2 - количество единиц продукции второго. Тогда, учитывая количество единиц сырья, расходуемое на изготовление продукции, а так же запасы сырья, получим систему ограничений:

1*x1+3*x2<=90

*x1+2*x2<=120

*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

Конечную цель решаемой задачи - получение максимальной прибыли при реализации продукции - выразим как функцию двух переменных х1 и x2. Реализация х1 единиц продукции первого вида и x2 единиц продукции второго дает соответственно 5х1 и 2x2 ден. ед. прибыли, суммарная прибыль С = 5х1 + 2x2. Условиями не оговорена неделимость единицы продукции, поэтому х1 и x2 (план выпуска продукции) могут быть и дробными числами. Требуется найти такие х1 и x2, при которых функция С достигает максимум, т.е. найти максимальное значение линейной функции С = 5х1 + 2x2 при ограничениях.

Математическая модель задачи:

Сmax = 5х1 + 2x2

Система ограничений:

1*x1+3*x2<=90

*x1+2*x2<=120

*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

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

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

Неравенствоx11x21x12x221*x1+3*x2<=909000304*x1+2*x2<=1203000601*x1+1*x2<=40400040Построим вектор целевой функции C(5;2). Система координат с областью допустимых решений OABCD и вектором целевой функции C приведена на рис.

Рис. График области допустимых решений.

Построим линию уровня 5x1+2x2 = 0, проходящую через начало координат и перпендикулярную вектору C (5;2). Будем передвигать ее в направлении вектора С, в результате чего находим точку, в которой функция принимает максимальное значение - точку D. При дальнейшем перемещении она уже не будет иметь общих точек с областью допустимых решений OABCD. Точка D имеет координаты (30;0). Сmax = 5*30+2*0=150

Ответ: Для того чтобы получить максимальную прибыль в размере 150 ден. ед., необходимо запланировать производство 30 ед. продукции первого вида, а продукцию второго вида не выпускать совсем.

Задача №2

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

Решение задачи.

Математическая модель задачи:

Сmax = 5х1 + 2x2

Система ограничений:

1*x1+3*x2<=90

*x1+2*x2<=120

*x1+1*x2<=40

x1,x2 >=0; - условие неотрицательности переменных.

Решение задачи с использованием метода симплекс-таблиц.

Приведем математическую модель задачи к каноническому виду, избавившись от неравенств посредством ввода дополнительных переменных:

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

С max = 5*x1+2*x2+0*x3+0*x4+0*x5

Система ограничений:

1*x1+3*x2+x3=90

*x1+2*x2+x4=120

*x1+1*x2+x5=40

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

Расширенная целевая функция:

С max = 5*x1+2*x2+0*x3+0*x4+0*x5

Вектора:

P0P1(x1)P2(x2)P3(x3)P4(x4)P5(x5)9013100120420104011001

Базисными могут быть только единичные вектора. Базис:

Базисный вектор №1: P3(x3)

Базисный вектор №2: P4(x4)

Базисный вектор №3: P5(x5)

Заполним первую таблицу:

№БазисКоэффициенты при базисеP052000P1P2P3P4P51P3090131002P40120420103P504011001С max =0-5-2000

При просмотре последней (индексной) строки среди коэффициентов этой строки (исключая столбец свободных членов) находим наименьшее отрицательное число: -5 (первый столбец - ключевой).

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

Замещаемый базисный вектор: P4 (2-я строка)

Новый базисный вектор: P1 (1-й столбец)

Заменяем базисный вектор P4 на P1.

Строим новую таблицу, содержащую новые названия базисных переменных, для этого:

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

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

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

В результате получили новую симплекс-таблицу, отвечающую новому базисному решению:

№БазисКоэффициенты при базисеP052000P1P2P3P4P51P306002.51-0.2502P153010.500.2503P501000.50-0.251С max =15000.501.250

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

Из таблицы получим значения переменных целевой функции:

x1x2x3x4x530060010

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

C max = 5*30+2*0

И в результате: Ответ: Для того чтобы получить максимальную прибыль в размере 150 ден. ед., необходимо запланировать производство 30 ед. продукции первого вида, а продукцию второго вида не выпускать совсем (ответ совпадает с ответом, полученным графическим методом).

Задача №3

Транспортная задача открытого типа.

В регионе расположено несколько НГДУ, обеспечивающих определённые объёмы добычи нефти, которая поступает в НПЗ, расположенные в различных регионах страны и имеющие различные производственные мощности. В силу разноудалённости потребителей от НГДУ затраты на транспортировку нефти различаются.

В задаче необходимо составить план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты на транспортировку нефти.

Введены условные обозначения:

i - индекс НГДУ, i=1,m

m - общее число НГДУ в регионе

j - индекс НПЗ, j=1,n

n - общее число НПЗ.

Известно:

- объёмы добычи нефти в i-ом НГДУ, тыс.т.;

- потребность j-го НПЗ в нефти, тыс.т.;

- издержки на транспортировку 1000 т. нефти, тыс. руб.

180190110210200120490578469270725867380547698

Модель задачи. В качестве неизвестных задачи принимаются переменные , означающие объём перевозок нефти i-го НГДУ к j-му НПЗ. В качестве коэффициентов целевой функции выступают издержки на перевозку 1000 т. нефти. Целевая функция минимизируется. Модель задачи записывается в общем виде, при этом необходимо учесть, что по исходным данным задача является открытой.

Имеем транспортную задачу с избытком запасов:

å аi > å bj ( где i=1..m ; j=1..n ).

490+270+380>180+190+110+210+200+120

>1010

C max = 150;

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно, при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые - остаются равенствами.

n

å Xi,j ? ai (i=1, ... , m);

j=1

m

å Xi,j = bj (j=1, ... , n).

i=1

Мы получаем следующую задачу:

х11+х12+х13+х14+х15+х16 ? 490

х21+х22+х23+х24+х25+х26 ? 270

х31+х32+х33+х34+х35+х36 ? 380

х11+х21+х31 = 180

х13+х23+х33 = 190

х14+х24+х34 = 110

х12+х22+х32 = 210

х15+х25+х35 = 200

х16+х26+х36 = 120

хij 0 для i = 1,2,3; j = 1,2,3,4,5,6;

Кmin=5х11+7х12+8х13+4х14+6х15+9х16+7х21+2х22+5х23+8х24+6х25+7х26+5х31+4х32+7х33+ +6х34+9х35+8х36;

Решение задачи.

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

Для этого, сверх имеющихся n пунктов назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

ит+1 = å аш - å и ( где ш=1бюююбь ж о=1бюююбт ) б

b7 = 1140 - 1010= 130,

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

назначения Bn+1 с его заявкой bn+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Первоначальный опорный план поставок построим на основе метода северо-западного угла:

bjai1801901102102001201304905 7 8 4 6 9 0 18019011010 2707 2 5 8 6 7 0 20070 3805 4 7 6 9 8 0 130120130

Стоимость перевозок по данному плану составляет: 7300 тыс. руб.

Решим задачу с применением метода потенциалов.

Для этого плана можно определить платежи (ai и bj ), так, чтобы в каждой базисной клетке выполнялось условие :

ai + bj = сi,j (*)

Уравнений (*) всего m + n - 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n - 1 уравнений (*) можно найти остальные платежи ai , bj , а по ним вычислить псевдостоимости: ui,j= ai + bj для каждой свободной клетки.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей ui,j ? сi,j ,

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

bjai180190110210200120130ai4905 7 8 4 6 9 0 05180719081104102 1 -7 2707 2 5 8 6 7 0 49 11 12 82006705 -3 3805 4 7 6 9 8 0 712 14 15 11 913081200130?i578421-7

Мы получили в семи клетках иi,j ? сi,j , теперь можно построить цикл в любой из этих клеток. Выгоднее всего строить цикл в той клетке, в которой разность иi,j ? сi,j максимальна. В нашем случае для построения цикла берем клетку (3,2):

bjai180190110210200120130ai4905 7-1308 4+1306 9 0 05180719081104102 1 -7 2707 2 5 8-1306+1307 0 49 11 12 82006705 -3 3805 4+1307 6 9-1308 0 712 14 15 11 913081200130?i578421-7

Теперь будем перемещать по циклу число 130, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком -. При перемещении мы будем вычитать 130 из клеток со знаком - и прибавлять к клеткам со знаком + .

После этого необходимо подсчитать потенциалы ai и bj и цикл расчетов повторяется:

Стоимость перевозок по данному плану составляет: 6000 тыс. руб.

bjai180190110210200120130ai4905 7-608 4+606 9 0 05180760811041402 11 3 2707 2+605 8-606 7 0 49 11 12 870620015 7 3805 4 7 6 9 8 0 -32 41305 1 -1 81200130?i57842113

bjai180190110210200120130ai4905 7 8-104+106 9 0 05180-2 811042002 2 -6 2707 2 5+108-106 7 0 49 26012 81062006 -2 3805 4 7 6 9 8 0 611 413014 10 8 81200130?i5-28422-6

Стоимость перевозок по данному плану составляет: 5460 тыс. руб.

bjai180190110210200120130ai4905 7 8-1004 6+1009 0 051805 810042109 9 1 2707 2 5+1008 6-1007 0 -32 2605101 62006 -2 3805 4 7 6 9 8 0 -14 41307 3 8 81200130?i5584991

Стоимость перевозок по данному плану составляет: 5390 тыс. руб.

bjai180190110210200120130ai4905-1007 8 4 6+1009 0 051802 5 421061006 -2 2707 2+1005 8 6-1007 0 05 26051104 61006 -2 3805+1004-1007 6 9 8 0 27 41307 6 8 81200130?i525466-2

Стоимость перевозок по данному плану составляет: 5090 тыс. руб.

bjai180190110210200120130ai4905 7 8 4 6 9 0 05804 7 421062008 0 2707 2 5 8 6 7 0 -23 216051102 4 6 -2 3805 4 7 6 9 8 0 051004307 4 6 81200130?i5474680

Стоимость перевозок по данному плану составляет: 4890 тыс. руб. Псевдостоимости ui,j = ai + bj для всех свободных клеток не превышают стоимостей, план оптимален.

Кmin=4890

Ответ: план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты на транспортировку нефти представлен ниже (Стоимость перевозок по данному плану составляет 4890 тыс. руб.):

bjai1801901102102001201304905 7 8 4 6 9 0 80 210200 2707 2 5 8 6 7 0 160110 3805 4 7 6 9 8 0 10030 120130

Задача №4

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

Решение задачи.

Первоначальный опорный план поставок построим на основе метода минимальной стоимости.

bjai1801901102102001201304905 7 8 4 6 9 0 2101501302707 2 5 8 6 7 0 190803805 4 7 6 9 8 0 1803050120

Стоимость перевозок по данному плану составляет: 5040 тыс. руб.

Применяем метод потенциалов.

bjai180190110210200120130ai4905 7 8 4 6+509 0-5002 1 4 421061505 01302707 2 5 8 6 7 0 13 21905805 7 6 1 3805 4 7 6 9-508 0+50351804 7307 95081203 ?i2144650

bjai180190110210200120130ai4905 7 8 4 6 9 0 05 4 7 421062008 0802707 2 5 8 6 7 0 -23 21905802 4 6 -2 3805 4 7 6 9 8 0 051804 7304 6 8120050?i5474680

Стоимость перевозок по данному плану составляет: 4890 тыс. руб. Псевдостоимости

ui,j = ai + bj для всех свободных клеток не превышают стоимостей, план оптимален (стоимость совпадает с полученной стоимостью задачи №3, но план перевозок альтернативен).

Ответ: план закрепления поставщиков за потребителями, который учитывает, по возможности, наиболее полное удовлетворение потребителей НПЗ и при этом обеспечивает минимальные затраты на транспортировку нефти представлен ниже (Стоимость перевозок по данному плану составляет 4890 тыс. руб.):

bjai1801901102102001201304905 7 8 4 6 9 0 210200802707 2 5 8 6 7 0 190803805 4 7 6 9 8 0 180 3012050

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

1. Ашманов С.А. Линейное программирование. - М.: Наука, 1981.

. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 2006

. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1967.

. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: Высшая школа, 1980.

. Нит И.В. Линейное программирование. - М.: Изд-во МГУ, 1978.

. Тарасенко Н.В. Математика-2. Линейное программирование: курс лекций. - Иркутск: изд-во БГУЭП, 2003.

. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы. - М.: Физматиз, 1963.

Экономико-математические методы и модели Содержание Задача №1 Задача №2 Задача №3

Больше работ по теме: