Балансовый метод планирования

BORDER=1 BORDERCOLOR="#000000" CELLPADDING=8 CELLSPACING=0> № оп.пл. Базис С bi 8 10 12 18 0 0 0 0



х1 х2 х3 х4 х5 х6 х7 х8
х5 0 2110 2 4 6 <8> 1 0 0 0
х6 0 1810 2 2 0 6 0 1 0 0
х7 0 1440 0 1 1 2 0 0 1 0
х8 0 1120 1 0 1 0 0 0 0 1
Fj - Сj 0 -8 -10 -12 -18 0 0 0 0
х4 18 263,75 0,25 0,5 0,75 1 0,125 0 0 0
х6 0 227,5 <0,5> -1 -4,5 0 -0,75 1 0 0
х7 0 912,5 -0,5 0 -0,5 0 -0,25 0 1 0
х8 0 1120 1 0 1 0 0 0 0 1
Fj - Сj 4747,5 -3,5 -1 1,5 0 2,25 0 0 0
х4 18 150 0 1 <3> 1 0,5 -0,5 0 0
х1 8 455 1 -2 -9 0 -1,5 2 0 0
х7 0 1140 0 -1 -5 0 -1 1 1 0
х8 0 665 0 2 10 0 1,5 -2 0 1
Fj - Сj 6340 0 -8 -30 0 0,1667 7 0 0
х3 12 50 0 0,3333 1 0,3333 0,1667 0,1667 0 0
х1 8 905 1 1 0 3 0,5 0,5 0 0
х7 0 1390 0 0,6667 0 1,6667 0,1667 0,1667 1 0
х8 0 165 0 -1,333 0 -3,333 -0,333 -0,333 0 1
Fj - Сj 7840 0 2 0 10 2 2 0 0

Ответ: Fmах = 7840 ед. стоимости; хопт = (905; 0; 50; 0; 0; 0; 1390; 165).

Для получения прибыли равной 7840 ед. стоимости необходимо включить в план продукцию первого и третьего вида в количествах:


В1 = 905 ед.;

В3 = 50 ед.,


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


А3 = 1390 ед.

А4 = 165 ед.


Задача 3


Для откорма группы животных на ферме необходимо наличие в ежедневном рационе не менее как В1, единиц питательных веществ В2 и т.д. – не менее как Вm. Указанные питательные вещества содержатся в n разных кормовых продуктах, которые можно закупить.

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


Питательные вещества Кормовые продукты

Суточная необходимость

Вi = В0 + n1


В1 В2 В3 В4
А1 1 2 2 1 64 + 9
А2 0 3 1 1 39 + 9
А3 2 1 0 3 35 + 9
Стоимость 1 кг кормов 2 1 3 4

Составить математическую модель и решить ЗЛП.

Решение

Введем переменные:

х1 – количество кормового продукта В1

х2 – количество кормового продукта В2

х3 – количество кормового продукта В3

х4 – количество кормового продукта В4

Строим математическую модель:


Fmах = 2х1 + х2 + 3х3 + 4х4


при условиях:

х1 + 2х2 + 2х3 + х4 ≥ 155;

2 + х3 + х4 ≥ 130;

1 + х2 + 3х4 ≥ 126;

хj ≥ 0; j = 1,4.


Приведем систему ограничений к каноническому виду:


х1 + 2х2 + 2х3 + х4 – х5 = 155;

2 + х3 + х4 – х6 = 130;

1 + х2 + 3х4 – х7 = 126;

хj ≥ 0; j = 1,7.


Приведем систему ограничений к виду удобному для решения:


х1 + 2х2 + 2х3 + х4 – х5 + х8 = 155;

2 + х3 + х4 – х6 + х9 = 130;

1 + х2 + 3х4 – х7 + х10 = 126;

хj ≥ 0; j = 1,10.


Переменные х8, х9, х10 являются искусственными и они введены на знак «=», поэтому для корректировки задачи эти переменные вводят в целевую функцию с коэффициентом +М.


Fmin = 2х1 + х2 + 3х3 + 4х4 + Мх8 + Мх9 + Мх10.


Задача решается модифицированным симплекс-методом (метод искусственного базиса).


о/п

Ба-

зис

С bi С1=2 С2=1 С3=3 С4=4 С5=0 С6=0 С7=0 С8=М С9=М С10=М




Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8 Х9 Х10

х8 М 155 1 2 2 1 -1 0 0 1 0 0

х9 М 130 0 <3> 1 1 0 -1 0 0 1 0

х10 М 126 2 1 0 3 0 0 -1 0 0 1

Fj - Сj 0 -2 -1 -3 -4 0 0 0 0 0 0

М
411 3 6 3 5 -1 -1 -1 0 0 0

х8 М

1 0 4/3 1/3 -1 2/3 0 1
0

х2 1

0 1 1/3 1/3 0 -1/3 0 0
0

х10 0

<2> 0 -1/3 8/3 0 1/3 -1 0
1

Fj - Сj

-2 0 -8/3

-

0 -1/3 0 0
0

М
151 3 0 1 3 -1 1 -1 0
0

х8 М 27 0 0

<>

-1 -1 1/2 1/2 1


х2 1

0 1 1/3 1/3 0 -1/3 0 0


х1 2

1 0 -1/6 4/3 0 1/6 -1/2 0


Fj - Сj 126 0 0 -3 -1 0 0 -1 0


М
27 0 0 3/2 -1 -1 1/2 1/2 0


х3 3 18 0 0 1 -2/3 -2/3

1/3

<1/3>



х2 1

0 1 0 5/9 2/9 -4/9 -1/9



х1 2

1 0 0 11/9 -1/9 2/9 -4/9



Fj - Сj 180 0 0 0 -3 -2 1 0



х6 0 54 0 0 3 -2 -2 1 1



х2 1

0 1 4/3 -1/3 -2/3 0 1/3



х1 2

1 0 -2/3 5/3 1/3 0 -2/3



Fj - Сj 126 0 0 -3 -1 0 0 -1



Каждый опорный план проверяем на оптимальность.

В 5-м опорном плане в индексной строке все разности Fj - Сj ≤ 0, следовательно этот план является оптимальным (F→min).

Можно записать ответ:


Fmin = 126 ед.стоимости,

Хопт = (97/3 = 32,33; 184/3 = 61,33; 0; 0; 0; 54).


Для получения минимальной себестоимости на изготовление кормовой продукции равной 126 ед. ст. необходимо включить в план кормовые продукты 1-го В1 = 32,33 ед. и второго вида В2 = 61,33 ед. и остались недоиспользованы ресурсы по А3 в количестве 54 ед.


Задача 4


С четырех карьеров к трем керамическим заводам перевозят глину.

Карьеры Керамические заводы

Мощность карьера

Вj = Воj + n


В1 В2 В3
А1 15 6 12 45 + 9
А2 4 6 8 38 + 9
А3 24 21 5 23 + 9
А4 12 9 12 84
Вj + Воj + n 70 + 9 65 + 9 55 + 9 190 + 3*9

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

Решение

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


m n

Smin = Σ Σ Cij Хij,

i=1 j=1


при условиях по ресурсам:

n

Σ хij = Аi,, i = 1,m

j=1

m

Σ хij = Вj, j = 1,n

i=1

хij ≥ 0; i = 1,m; j = 1,n.

Существует два вида моделей:

m n

закрытая Σ Аi = Σ Вj;

i=1 j=1

m n

открытая Σ Аi ≠ Σ Вj.

i=1 j=1

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

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


Σ Аi = 217; Σ Вj = 217.


Строим первый опорный план по правилу минимального элемента:


Поставщики Потребители U

В1 = 79 В2 = 74 В3 = 64
А1 = 54

15

32- ρ

6

22 + ρ

12 U1 = 0
А2 = 47

4

47

6 8 U2 = -11
А3 = 32 24 21

5

32

U3 = -4
А4 = 84

12

9

52-ρ

12

32

U4 = 3
V V1 = 15 V2 = 6 V3 = 9 Smin = 1812

Далее делается проверка системы ограничений:

n m =

Σ хij = Аi,, Σ хij = Вj,

j=1 i=1

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

Проверяем план на вырожденность: количество заполненных клеток должно быть равно: m + n – 1 = 4 + 3 – 1 = 6.

Считаем стоимость перевозок:


Smin = 15*32 + 6*22 + 4*47 + 5*92 + 9*52 + 12*32 = 1812.


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


Сij = Ui + Vj, хij > 0.


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


Sij = Сij – (Ui + Vj) ≥ 0.


Оказалось, что одна клетка не оптимальна S41 = -6.

Ставим в эту клетку +ρ – это величина для перераспределения ресурсов. От этой клетки строим цикл пересчета – это многоугольник любой конфигурации с прямыми циклами, расположенными в заполненных клетках. По углам этого цикла (прямоугольника) ставим +ρ и –ρ, чтобы был баланс по строкам и столбцам.

Определяем величину перераспределения груза (ресурсов):


ρ = min {32;52} = 32.


Строим новый опорный план:

Поставщики Потребители U

В1 = 79 В2 = 74 В3 = 64
А1 = 54

15


6

54

12 U1 = 0
А2 = 47

4

47

6 8 U2 = -5
А3 = 32 24 21

5

32

U3 = -4
А4 = 84

12

32

9

20

12

32

U4 = 3
V V1 = 9 V2 = 6 V3 = 9 Smin = 1620

и весь алгоритм повторяется снова:


Smin 2 = 6*54 + 4*47 + 5*32 + 12*32 + 9*20 + 12*32 = 324 + 188 + 160 + 384 +180+ + 384 = 1620.


Все Sij ≥ 0, следовательно 2-й опорный план является оптимальным.

Ответ: минимальная стоимость перевозок равна 1620 ед. стоимости.

Поставки глины: х12 = 54 т; х21 = 47 т; х33 = 32 т; х41 = 32 т; х42 = 20 т; х43 = 32 т.


Список литературы


1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986.

2. Архангельский Ю.С., Коваленко И.И. Межотраслевой баланс. – К.: Выща шк. Головное изд-во, 1988.

3. Ашманов С.А. Введение в математическую экономику. – М.: Наука, 1984.

4. Вентцель Е.С. Исследование операций: Задачи, принципы, методология. – М.: Наука, 1980

5. Вивальнюк Л.М. Елементи лінійного програмування. – К.: Вища школа, 1975.

6. Гейл Д. Теория линейных экономических моделей. – М.: ИЛ, 1963.

7. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование (теория, методы и приложения). – М.: Наука, 1969.

8. Данциг Дж. Линейное программирование, его обобщения и приложения. – М.: Прогресс, 1966.

9. Деордица Ю.С., Нефедов Ю.М. Исследование операцій в планировании и управлении. – К.: Вища школа, 1991.

10. Ефимов Н.В. Квадратичные формы и матрицы. – М.: Наука, 1972.

11. Зайченко Ю.П. Исследование операций. – К.: Вища школа, 1979.

12. Исследование операций. / Под ред. Н.С. Кремера. – М.: Бизнес и банки, ЮНИТИ, 1997.

13. Кузнецов Ю.Н. и др. Математическое программирование. – М.: Высшая школа, 1980.

14. Карпелевич Ф.М., Садовский Л.Е. Математическое программми-рование. – И.: Наука, 1967.

15. Лотов А.В. Введение в экономико-математическое моделирование. – М.: Наука, 1984.

16. Математика в экономике: Учебник: в 2-х ч. Ч.1/ А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандра. – 2-е изд., перераб. и доп. – М.: Финансы и статистика, 2006.

17. Математические методы и модели в планировании и управлении. Сборник задач. К.: Вища школа, 1985.

18. Терехов Л.Л., Куценко В.А.Ж, Сиднев С.П. Экономико-математические методы и модели в планировании и управлении. – К.: Вища школа, 1984.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: