Контрольная работа - Моделированию социально экономических систем: Построение моделей одноиндексных задач линейного программирования - файл n1.docx

Контрольная работа - Моделированию социально экономических систем: Построение моделей одноиндексных задач линейного программирования
Скачать все файлы (96 kb.)

Доступные файлы (1):
n1.docx96kb.31.01.2014 23:25скачать

n1.docx

  1   2
ФГБОУ ВПО «Курганская государственная сельскохозяйственная академия имени Т.С. Мальцева»

Факультет: Экономический

Отделение: Бухгалтерский учет, анализ и аудит

Контрольная работа

по дисциплине: «Моделирование социально экономических систем»

Выполнила: студентка 6 курса (ускор.)

заочного отделения

Цибирева А.С.

Шифр: 09503

Проверил:
Лесниково 2013

Содержание

Задание 1

Задание 2

Задание 3

ЗАДАНИЕ 1

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

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. Ед., а улучшенный – 4 ден. Ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Решение:

Сформулируем прямую оптимизационную задачу.

Пусть х1 – количество обычных наборов удобрений;

х2 – количество улучшенных наборов удобрений.

Содержание в двух данных наборах азотных удобрений: 3х1 + 2х2

А для некоторого газона требуется по крайней мере 10 кг азотных удобрений, следовательно:

3х1 + 2х2 ? 10

Содержание в двух данных наборах фосфорных удобрений должно быть не менее 20 кг, т. е.:

4х1 + 6х2 ? 20

И содержание в двух данных наборах калийных удобрений должно быть не менее 7 кг, т. е.:

1х1 + 3х2 ? 7

Стоимость необходимых наборов удобрений составит:

3х1 + 4х2.

Таким образом, получим следующую экономико-математическую модель задачи:

F(х) = 3х1 + 4х2? min

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

х1 + 3х2 ? 7

х1 і 0, х2 і 0

Построим область решений системы ограничений. Для этого рассмотрим равенства и построим их графики – прямые.

1) 3х1 + 2х2 ? 10

3х1 + 2х2 = 10

х1

х2

0

5

4

-1

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

Возьмем точку О(0;0):

3*0 + 2*0 ? 10

0 ? 10

Неравенство не выполняется, значит, исходному неравенству соответствует та полуплоскость, которая не содержит точку (0;0).

2) 4х1 + 6х2 ? 20

4х1 + 6х2 = 20

х1

х2

-1

4

5

0

4*0 + 6*0 ? 20

0 ? 20

Неравенство не выполняется, значит, исходному неравенству соответствует полуплоскость, не содержащая точку О(0;0).

3) х1 + 3х2 ? 7

х1 + 3х2 = 7

х1

х2

-2

3

7

0

1*0 + 3*0 ? 7

0 ? 7

Неравенство не выполняется, значит, исходному неравенству соответствует полуплоскость, не содержащая точку О(0;0).

4) х1 ? 0

х1 = 0 – ось ОХ2.

5) х2 ? 0

х2 = 0 – ось ОХ1.

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

wpid-image00211

Рис.1. Графическое решение

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

Для нахождения оптимального решения задачи изобразим графически функцию цели:

(х) = d1x1 + d2x2

(х) = 3х1 + 4х2

Для этого строим вектор d, начало которого в точке (0;0), а конец в точке (d1;d2).

d = (3; 4).

И строим одну из линий уровня функции цели (это линия, на которой функция цели принимает постоянное значение).

Для определения минимума данной функции, передвигаем линию уровня в направлении, противоположном вектору d, и видим, что она последний раз соприкасается с областью решений в точке В, где и будет достигнут min(х).

Определим координаты точки В:

3х1 + 2х2 = 10 *(-3)

4х1 + 6х2 = 20

-9х1 – 6х2 = -30

4х1 + 6х2 = 20

Складываем почленно уравнения и получаем:

-5х1 = -10

х1 = 2

wpid-image00414

В(2; 2)

max (х) = 3*2 + 4*2 = 14 (ден. ед.)

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

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


ЗАДАНИЕ 2

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

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

Тарифы на перевозку продукции и объёмы запасов на складе и заказов в таблице.

Магазин

Склад

“Всё для дома”

“Здоровый сон”

“Фея”

“Ночное царство”

“Мех”

Запасы на складе (ед. прод.)

“Вороново”

1

3

4

5

2

20

“Фили”

2

1

1

4

5

15

“Беляево”

1

3

3

2

1

40

“Выхино”

3

1

4

2

3

15

Объём заказа (ед. прод)

15

10

25

5

35




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

Обозначим Xij – количество груза, которое необходимо перевезти от i – го поставщика (склада) к j – му потребителю (магазину)

i = 1,2,3,4

j = 1,2,3,4,5

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

Переменные:

X11 – объем груза, перевозимого cо склада “Вороново” в магазин “Всё для дома”, ед. прод.;

Х12 - объем груза, перевозимого cо склада“Вороново” в магазин “Здоровый сон”, ед. прод.;

Х13 - объем груза, перевозимого cо склада “Вороново”в магазин “Фея”, ед. прод.;

Х14 - объем груза, перевозимого cо склада “Вороново”в магазин “Ночное царство”, ед. прод.;

Х15 - объем груза, перевозимого cо склада “Вороново”в магазин “Мех”, ед. прод.;

Х21 - объем груза, перевозимого cо склада “Фили”в магазин “Всё для дома”, ед. прод;

Х22 - объем груза, перевозимого cо склада “Фили” в магазин “Здоровый сон”, ед. прод.;

Х23 - объем груза, перевозимого cо склада “Фили”в магазин “Фея”, ед. прод.;

Х24 - объем груза, перевозимого cо склада “Фили”в магазин “Ночное царство”, ед. прод.4

Х25 - объем груза, перевозимого cо склада “Фили”в магазин “Мех”, ед. прод.;

Х31 - объем груза, перевозимого cо склада “Беляево”в магазин “Всё для дома”, ед. прод.;

Х32 - объем груза, перевозимого cо склада “Беляево”в магазин “Здоровый сон”, ед. прод.;

Х33 - объем груза, перевозимого cо склада “Беляево”в магазин “Фея”, ед. прод.;

Х34 - объем груза, перевозимого cо склада “Беляево”в магазин “Ночное царство”, ед. прод.;

Х35 - объем груза, перевозимого cо склада “Беляево”в магазин “Мех”, ед. прод.;

Х41 - объем груза, перевозимого cо склада “Выхино”в магазин “Всё для дома”, ед. прод.;

Х42 - объем груза, перевозимого cо склада “Выхино”в магазин “Здоровый сон”, ед. прод.;

Х43 - объем груза, перевозимого cо склада “Выхино”в магазин “Фея”, ед. прод.;

Х44 - объем груза, перевозимого cо склада “Выхино”в магазин “Ночное царство”, ед. прод.;

Х45 - объем груза, перевозимого cо склада “Выхино”в магазин “Мех”, ед. прод.

Ограничения:

    1. по возможности склада “Вороново”, ед. прод.

х11 + х12 + х13+ х14 + х15 =20

    1. по возможности склада“Фили” , ед. прод.

х21 + х22 + х23 + х24 + х25 = 15

    1. по возможности склада“ Беляево ”, ед. прод.

х31 + х32 + х33 + х34 + х35 = 40

    1. по возможности склада“Выхино”, ед. прод.

х41 + х42 + х43 + х44 + х45 = 15

    1. по потребности магазина “Всё для дома”, ед. прод.

х11 + х2131 + х41 = 15

    1. по потребности магазина “Здоровый сон”, ед. прод.

х12 + х2232 + х42 = 10

    1. по потребности магазина “Фея”, ед. прод.

х13 + х2333 + х43 = 25

    1. по потребности магазина “Ночное царство”, ед. прод.

х14 + х2434 + х44 = 5

    1. по потребности магазина “Мех”, ед. прод.

х15 + х2535 + х45 = 35

    1. условие неотрицательности переменных

X11 ?0; Х12 ?0; Х13 ?0; Х14 ?0; Х15 ?0; Х21 ?0; Х22 ?0; Х23?0; Х23 ?0; Х23?0; Х31 ?0; Х32 ?0; Х33 ?0; Х34 ?0; Х35?0; Х41 ?0; Х42 ?0; Х43 ?0; Х44 ?0;Х45?0

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

F(x) = х11 + х12 + х13+ х14 + х15+ х21 + х22 + х23 + х24 + х25+ х31 + х32 + х33 + х34 + х3541 + х42 + х43 + х44 + х45

Решение:

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

Для получения исходного плана перевозок используем правило «северо-западного» угла. Расчёт начинается с заполнения левой верхней клеточки и постепенно до нижней правой, т е за счёт ресурсов первого поставщика удовлетворяются потребности первого потребителя. Если они выше, чем потребность первого потребителя, то удовлетворяются потребности второго потребителя, так постепенно распределяются ресурсы всех поставщиков.

При этом количество занятых клеток составит:

m + n – 1 = 4 + 5 – 1 = 8 , где

m – количество поставщиков:

n – количество потребителей.

Первоначальный план представлен в таблице 1.



Склады

магазины

Запас

Qi

“Всё для дома”

“Здоровый сон”

“Фея”

“Ночное царство”

“Мех”




“Вороново”

1

15

3


4


5

2

5

20

“Фили”

2


1


1

15

4

5

15


“ Беляево ”

1


3


3

10

2

5

1

25

40


“Выхино”

3


1

10

4


2

3

5

15

Спрос

bj

15

10

25


5


35

90=90


X11 =15; Х15 =5; Х23 =15; Х33 =10; Х34 =5; Х35 =25; Х42 =10; Х45 =5.

F (x) = 1*15+2*5+1*15+3*10+2*5+1*25+1*10+3*5=130

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

Ui +Vj = Cij

Vj – потенциал столбца

Ui – потенциал строки

Cij – тариф (показатель) занятой клетки

Для занятых клеток (1.1) (1.5) (2.3) (3.3) (3.4) (3.5) (4.2) (4.5)

1.1) V1 + U1 = 1 V1 = 1 U1 = 0

1.5) V1 + U5 = 2 V2 = 0 U2 = -3

2.2) V2 + U2 = 1 V3 = 4 U3 = -1

3.3) V3 + U3 = 3 V4 = 3 U4 = 1

3.4) V3 + U4 = 2 V5 = 2

3.5) V3 + U5 = 1

4.2) V4 + U2 = 1

4.5) V4 + U5 = 3

Для свободных клеток (1.2) (1.3) (1.4) (2.1) (2.2) (2.4) (2.5) (3.1) (3.2) (4.1) (4.3) (4.4) определяется характеристика по формуле

dij= Cij — (Ui+ Vj)

dij – характеристика свободной клетки

Vj – потенциал столбца

Ui – потенциал строки

Cij – тариф свободной клетки

1.2) d1.2= 3 — (V2 + U1) = 3 — (0 — 0) = 3

1.3) d1.3= 4 — (V3 + U1) = 4 — (4 + 0) = 0

1.4) d1.4= 5 — (V4 + U1) = 5 — (3 + 0) = 2

2.1) d2.1= 2 — (V1 + U2) = 2 — (1 — 3) = 4

2.2) d2.2= 1 — (V2 + U2) = 1 — (0 —3) = 4

2.4) d2.4= 4 — (V4 + U2) = 4 — (3 — 3) = 4

2.5) d2.5= 5 — (V5 + U2) = 5 — (2 — 3) = 6

3.1) d3.1= 1 — (V1 + U3) = 1 — (1 — 1) = 1

3.2) d3.2= 3 — (V2 + U3) = 3 — (0 — 1) = 4

4.1) d4.1= 3 — (V1 + U4) = 3 — (1 + 1) = 1

4.3) d4.3= 4 — (V3 + U4) = 4 — (3 + 1) = 0

4.4) d4.4= 2 — (V4 + U4) = 2 — (3 + 1) = —2

Отрицательные характеристики - при решении задач на min (положительные при решении задач на max) указывают на то, что транспортные расходы могут быть снижены, т.е. план не opt.

Т.к. d4.4 = — 2, следовательно план в табл. 1 не оптимальный. План улучшается за счет клетки с отрицательной характеристикой. Если получено несколько отрицательных характеристик, то выбирается клетка имеющая наименьшую отрицательную характеристику ( при решении задач на max наибольшую положительную).

План улучшается за счет клетки с отрицательной характеристикой (кл. 4.4).
  1   2
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации