Xreferat.com » Рефераты по экономико-математическому моделированию » Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов

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

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

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

Кафедра «Экономика, финансы и управление на транспорте»


КОНТРОЛЬНАЯ РАБОТА

по дисциплине: «ЭКОНОМИКО-МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ»


Воронеж 2008

Задача №1


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

Задание:

  1. Построить оптимальный план перевозок каменного угля с пяти станций Аi (i = 1,2,3,4,5), до девяти крупных потребителей, имеющих подъездные пути Вj (j = 1,2,…,9).

  2. Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

Исходные данные (вариант 67):

Данные о наличии ресурсов на пяти станциях отправления Аi приведены в таблице 1, данные о размерах прибытия груза Вj на девять станций назначения – в таблице 2.


Таблица 1 - Ресурсы станций отправления Аi (строки матрицы)

Номер станции отправления Значение

А1

150

А2

160

А3

400

А4

150

А5

140
Итого: 1000

Таблица 2 - Объем потребности Вj получателя (столбцы матрицы)

Номер станции назначения Значение

В1

135

В2

105

В3

95

В4

115

В5

85

В6

105

В7

90

В8

135

В9

135
Итого: 1000

Решение:

Расстояние перевозки от каждой i–й станции отправления до каждой j–й станции назначения указано в правом верхнем углу каждой клетки матрицы. В левом верхнем углу ряда клеток матрицы указаны ограничения пропускной способности.

Условием задачи установлено, что размер всех ресурсов у отправителей равен общей потребности получателей:



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



Первоначально строится начальный план базисного варианта способом наименьшего значения критерия.

Любой допустимый план является оптимальным тогда и только тогда, когда каждой строке и каждому столбцу матрицы могут быть присвоены некоторые числа Ui и Vj, называемые потенциалами и отвечающие условиям:


Vj – Ui ≤ Cij для хij = 0; (1)

Vj – Ui = Cij для dij > хij > 0; (2)

Vj – Ui ≥ Cij для хij = dij; (3)


где Vj – потенциал j–го столбца;

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

Cij – расстояние перевозки от i–го поставщика до j–го потребителя;

хij – корреспонденция (размеры перевозок) от i–го поставщика до j–го потребителя;

dij – величина пропускной способности ij клетки.

Присвоение потенциалов начинают со строки, в которой среди базисных клеток имеется максимальное расстояние. Этой строке можно присвоить любой положительный потенциал, например, 100. Затем, используя условие оптимальности (2), находят потенциалы остальных строк и столбцов по формулам:

для j–го столбца


Vj = Ui + Cij;


для i–й строки


Ui = Vj – Cij.


Корреспонденция улучшения плана находится из следующего выражения:


хул = min [хij четн, (dij – хij)нечетн]



Вj

Аi

В1=135 В2=105 В3=95 В4=115 В5=85 В6=105 В7=90 В8=135 В9=135

Ui


– 90 30 100 110 150 30 50 + 60 80 90
А1=150 45



30 75

100

х

1+40

х



+ 10 40 45 50 – 25 70 30 15 30 10 30
А2=160 80


80



180

х

1+20 х 1+10




10 20 35 80 160 90 + 80 – 70 40 60
А3=400 10 105


15 135 135 90


х 1+20
1+25 1+90 х х х

50 5 40 30 120 40 75 30 40 20
А4=150


95
55


220




х
х




15 15 25 10 20 35 + 25 – 80 20 70 90
А5=140

95 20 5 20


180



х
х х














Vj

190 125 190 250 205 260 160 130 150












F(х) = 45·90 + 30·50 + 75·60 + 80·10 + 80·25 + 10·20 + 105·35 + 15·70 + 135·40 + 135·60 + 95·30 + 55·40 + 95·10 + 20·35 + 5·25 + 20·80 = 39700 ден. ед.

80 – 70 + 60 – 90 + 10 – 25 + 25 – 80 = – 90 < 0 – цикл подходит

r = {15; 45; 80; 20} =15



Вj

Аi

В1=135 В2=105 В3=95 В4=115 В5=85 В6=105 В7=90 В8=135 В9=135

Ui


– 90 + 30 100 110 150 30 50 60 80 90
А1=150 30


30 90

100

х 1+85
1+40

х 1+40 1+50

+10 40 45 50 – 25 70 30 15 30 10 30
А2=160 95


65



180

х

1+20 х 1+10
1+10


10 20 – 35 80 160 90 + 80 70 40 60
А3=400 10 105


15
135 135 180


х


х
х х

50 5 40 30 120 40 75 30 40 20
А4=150


95
55


220




х
х




15 15 25 10 20 35 + 25 – 80 20 70 90
А5=140

95 20 20 5


180



х
х х














Vj

190 215 190 250 205 260 160 220 240












F(х) = 39700 – 90·15 = 38350 ден.ед.

30 – 90 + 10 – 25 + 25 – 80 + 80 – 35 = – 85 < 0 – цикл подходит

r = {30; 65; 5; 105} = 5



Вj

Аi

В1=135 В2=105 В3=95 В4=115 В5=85 В6=105 В7=90 В8=135 В9=135

Ui


– 90 + 30 100 110 150 30 50 60 80 90
А1=150 25 5


30 90

100

х х



х



+ 10 40 45 50 – 25 70 30 15 30 10 30
А2=160 100


60



180

х


х





10 20 – 35 80 160 + 90 80 70 40 60
А3=400 10 100

20
135 135 95


х 1+15
1+20 х
х х

50 5 40 30 120 40 75 30 40 20
А4=150


95
55


135

1+5
1+15 х
х




15 15 25 10 20 35 25 80 20 70 90
А5=140

95 20 25



180



х
х















Vj

190 130 190 165 205 175 160 135 155












F(х) = 38350 – 85·5 = 37925 ден.ед.

90 – 25 + 10 – 90 + 30 – 35 = – 20 < 0 – цикл подходит

r = {60; 25; 100} = 25


Вj

Аi

В1=135 В2=105 В3=95 В4=115 В5=85 В6=105 В7=90 В8=135 В9=135

Ui


90 30 100 110 150 30 50 60 80 90
А1=150
30


30 90

105


х



х



10 40 45 50 25 70 30 15 30 10 30
А2=160 125


35



165

х


х





10 20 35 80 160 90 80 70 40 60
А3=400 10 75

25 20
135 135 100


х

х х
х х

50 5 40 30 120 40 75 30 40 20
А4=150


95
55


140




х
х




15 15 25 10 20 35 25 80 20 70 90
А5=140

95 20 25



165



х
х















Vj

175 135 175 170 190 180 165 140 160












План оптимальный.

F(х) = 37925 – 20·25 = 37425 ден.ед.

Ответ: F(х)нач. = 39700 ден.ед.; F(х)опт. = 37425 ден.ед.


Задача №2


Графический метод решения задачи оптимизации производственных процессов

Задание: Решить задачу линейного программирования графическим методом. Исходные данные (вариант 7):

Целевая функция: f(x) = x1 + 2x2 → max,

Ограничения: –x1 – x2 ≥ –1, x1– 2x2 ≤ 1.

Решение:

–х1 – х2 ≥ –1

х1 – 2х2 ≤ 1 (–1)

х1 ≥ 0; х2 ≥ 0

х1 + х2 ≤ 1

2 – х1 ≥ 1

х1 + х2 = 1

х1 = 1 – х2


Если х1 = 0, то х2 = 1;

если х2 = 0, то х1 = 1.


х1 – 2х2 = 1

х1 = 1 + 2х2


Если х1 = 0, то х2 = –1/2;

если х2 = 0, то х1 = 1.

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

х2 ≤ – х1 +1 – нижняя полуплоскость;

2 ≥ х1 –1 – верхняя полуплоскость.


Рис. 1 - Решением системы неравенств является т. С (0;1)

Ответ: х1= 0

х2 = 1


Задача №3


Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством.

Исходные данные (вариант 7):

Целевая функция: f(x) = x1 + 2x2 –3х3 → max.

Ограничения: x1 + x2 + х3 = 25,


2x1 – 3x2 + 3х3 ≥ 10;

x1 – 3x2 + 4х3 ≤ 30.


Решение:

Т.к. дана задача на максимизацию целевой функции f, то она сводится к задаче на минимизацию функции –f.

Введем функцию q = –f = –x1 – 2x2 +3х3

От ограничений неравенств переходим к ограничениям-равенствам, введя новые переменные х4 и х5:


х4 = 2x1 – 3x2 + 3х3 – 10; х5 = –x1 + 3x2 – 4х3 + 30.


Получим следующую основную задачу линейного программирования:


x1 + x2 + х3 = 25

х4 = 2x1 – 3x2 + 3х3 – 10

х5 = –x1 + 3x2 – 4х3 + 30

q = –x1 – 2x2 +3х3 → min

Выразим из 1-го уравнения х1 через другие неизвестные и подставим это его выражение в другие уравнения, а также в уравнение для функции q. Получим:


x1 = –x2 – х3 + 25

х4 = –2x2 – 2x3 + 50 –3х2 + 3х3 – 10

х5 = х2 + x3 – 25 + 3х2 – 4x3 + 30

q = x2 + х3 – 25 + 2х2 + 3x3

x1 = –x2 – х3 + 25 (1)

х4 = –5x2 + х3 + 40 (2)

х5 = 4х2 – 3x3 + 5 (3)

q = –x2 + 4х3 – 25 (4)


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


5x2 = х3 – х4 + 40

х2 = 0,2х3 – 0,2х4 + 8

x1 = –0,2x3 + 0,2х4 – 8 –x3 + 25

х2 = 0,2х3 – 0,2х4 + 8

х5 = 0,8х3 – 0,8x4 + 32 –3x3 + 5

q = –0,2x3 + 0,2х4 – 8 + 4х3 – 25

x1 = –1,2x3 + 0,2х4 + 17

х2 = 0,2х3 – 0,2х4 + 8

х5 = –2,2х3 – 0,8x4 + 37

q = 3,8x3 + 0,2х4 – 33


В выражении для функции q оба неизвестных входят со знаком «+». Поэтому можно утверждать, что найден оптимальный план: х3 = х4 = 0. Подставив эти значения в последнюю систему ограничений, получим и остальные неизвестные:

х1 = 17; х2 = 8; х5 = 37;

Оптимальное значение функции q = – 33, следовательно

f(x) = 33 млрд.руб.

Ответ: f(x) = 33 млрд.руб.


Задача №4


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

Задание:

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

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

Исходные данные – (вариант 67).

Решение:

Задачу решаем методом динамического программирования, последовательно двигаясь от конца трассы к ее началу, при этом на каждом шаге процесса выбирая то направление трассы, которое дает меньшую стоимость ее строительства от рассматриваемого пункта до пункта В (рис. 2).

Рис. 2


Ответ: Минимальные затраты на сооружение участка А – В составят W = 131 ден.ед.


Задача №5


Задача оптимального распределения ресурсов.

Задание (вариант 67):

Предприятие имеет свободных К млрд. руб. средств, которые оно может вложить в пять различных производственных программ. При этом прибыль от каждой из программ зависит от объема инвестиций. Эти зависимости fi известны и имеют следующий вид:


f(х) = bx – ax2


и конкретно:

f11) = 0,18x1 – 0,05x12;

f22) = 0,16x2 – 0,04x22;

f33) = 0,14x3 – 0,02x32;

f44) = 0,12x4 – 0,02x42;

f55) = 0,1x5 – 0,01x52 млрд.руб.


где х1, х2, х3, х4, х5 – инвестиции в программы, млрд.руб. Их общий объем равен К = 8,5 млрд.руб.

Требуется найти неотрицательные объемы инвестиций х1, х2, х3, х4, х5 соответствующие наибольшей общей прибыли


П = f11) + f22) + f33) + f44) + f55).


Решение:

Возможны следующие варианты:

  1. Все средства передаются первой программе;

  2. Средства распределяются между первой и второй программами;

  3. Средства распределяются между первой, второй и третьей программами;

  4. Средства распределяются между первой, второй, третьей и четвертой программами;

  5. Средства распределяются между первой, второй, третьей, четвертой и пятой программами.

Рассмотрим все 5 вариантов.


  1. К1 = х1 = 8,5


П1 = f11) = 0,18 8,5 – 0,05 8,52 = – 2,08 млрд.руб. < 0, следов–но убыток.

  1. К2 = х1 + х2

П2 = f11) + f22)

0,18 – 2 0,05х1 = 0,16 – 2 0,04х2

х1 + х2 = 8,5

0,1х1 – 0,08х2 = 0,02

х1 = 8,5 – х2

0,1 (8,5 – х2) – 0,08х2 = 0,02

0,85 – 0,1х2 – 0,08х2 = 0,02

0,85 – 0,18х2 = 0,02

0,18х2 = 0,83

х2 = 4,61

х1 = 8,5 – 4,61 = 3,89

П2 = 0,18 · 3,89 – 0,05 3,892 + 0,16 4,61 – 0,04 4,612 = 0,7 – 0,757 + 0,738 – 0,85 = – 0,169 млрд.руб. < 0, следов–но убыток.


  1. К3 = х1 + х2 + х3


П3 = f11) + f22) + f33)

0,18 – 0,1х1 = 0,16 – 0,08х2

0,16 – 0,08х2 = 0,14 – 2 · 0,02х3

х1 + х2 + х3 = 8,5

0,18 – 0,1х1 = 0,16 – 0,08х2

0,16 – 0,08х2 = 0,14 – 0,04х3

х1 + х2 + х3 = 8,5

0,1х1 – 0,08х2 = 0,18 – 0,16 · 50

0,08х2 – 0,04х3 = 0,16 – 0,14

х1 + х2 + х3 = 8,5

1 – 4х2 = 1 (1)

2 – 2х3 = 1 (2)

х1 + х2 + х3 = 8,5 (3)

Из 2 – го ур – ия: х3 = 2х2 – 0,5


1 – 4х2 = 1

х1 + х2 + 2х2 – 0,5 = 8,5

1 – 4х2 = 1 (1)

х1 + 3х2 = 9 (2)


Из 2 – го ур – ия: х1 = 9 – 3х2

5 (9 – 3х2) – 4х2 = 1

45 – 15х2 – 4х2 = 1

19х2 = 44

х1 = 9 – 3 · 2,316 = 2,052

х3 = 2 · 2,316 – 0,5 = 4,132

П3 = 0,18 · 2,052 – 0,05 · 2,0522 + 0,16 · 2,316 – 0,04 · 2,3162 + 0,14 · 4,132 – 0,02 · 4,1322 =

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

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

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

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