LINEBURG


<< Пред. стр.

страница 8
(всего 15)

ОГЛАВЛЕНИЕ

След. стр. >>

Предположим, что запас сырья ресурса «труд» изменился на 12 ед.,
т.е. теперь он составляет 80 + 12 = 92 ед. Из теоремы об оценках (2.3.11)
известно, что колебание величины Ь, приводит к увеличению или
уменьшению fiX). Оно определяется величиной у, в случае, когда при
изменении величин Ь, значения переменных у, в оптимальном плане со­
ответствующей двойственной задачи остаются неизменными. В нашей за­
даче увеличение запасов ресурса «труд» приведет к увеличению значения
целевой функции на 16 тыс. руб. (А/(х) = Д?м • >'i = 12 • 4/3 = 16). Для
двойственных оценок оптимального плана весьма существенное значе­
ние имеет их предельный характер. Точной мерой влияния ограничений
на функционал оценки являются лишь при малом приращении ограничения.
Известно, что оценки не меняют своей величины, если не меняется набор
векторов, входящих в базис оптимального плана, тогда как интенсивности
этих векторов (значения неизвестных) в плане могут меняться.
Поэтому необходимо знать такие интервалы изменения каждого из
свободных членов системы ограничений исходной ЗЛП, или интервалы
устойчивости двойственных оценок, в которых оптимальный план двой­
ственной задачи не менялся бы. Эту информацию можно получить из
Отчета по устойчивости. В нашей задаче в нижеприведенном фраг­
менте отчета видно, что запасы дефицитных ресурсов «труд» и «обору­
дование» могут быть как уменьшены, так и увеличены, увеличение запа­
са ресурса «сырье» не повлияет на план выпуска продукции.

Ограничение Доп) стичое
Допустимое
уменьшение
правая часть увеличение

80 15
150
200
480 1Е+30

90
130 30


После увеличения запаса ресурса «труд» до 92 чел./ч было получено
новое решение задачи. Изменение запасов ресурсов в пределах интерва­
лов устойчивости двойственных оценок привело не только к изменению
значения целевой функции на 16 тыс. руб., но и к изменению плана вы­
пуска. При этом структура плана не изменилась - изделия, которые были
убыточны, не вошли и в новый план выпуска, так как цены на ресурсы

61
не изменились. Новый план выпуска составляет 28 ковров второго вида
и 18 ковров третьего вида. Изменение общей стоимости продукции на
16 тыс. руб. (24 - 8 = 16) получено за счет уменьшения на 2 ед. ковров
второго вида по цене 4 тыс руб. (4 тыс. руб. х (28 - 30) = -8 тыс. руб.) и
увеличения на 8 ед. ковров третьего вида по цене 3 тыс. руб. (3 тыс. руб. х
х (18-10) = 24 тыс. руб.).

Отчет по устойчивости 2
Изменяем ые ячейки
Допусти-мое
Результ Нормир Целевой Допустимое
коэффи­
Ячейка Имя значение стоимость уменьше­
у величение
циент ние
$в$з значение XI 3
0 -7 7 1Е+30
$с$з значение Х2 0 4
28 8 1
3
значение ХЗ 1
$D$3 18 0 175
значение Х4 1
$Е$3 0 -9 6667 9 6667 1Е+30


Ограничения
Ограни­ Допусти-чое
чение
Результ Теневая Допустимое
Ячейка Имя значение правая у меньше-
цена увеличение
часть ние
$F$7 труд левая часть 92 1 3333 92 138 27
480 1Е+30
$F$8 сырье левая часть 296 0 184
озззз ПО 54
$F$9 оборудование 130 84
левая часть


4. Чувствительность решения к изменению коэффициентов целевой
функции исходной задачи.
В первой части Отчета по устойчивости содержится информация
о допустимом увеличении и уменьшении коэффициентов целевой функ­
ции, при которых не меняется оптимальный план исходной задачи.
Целевой Допустимое Допустимое
коэффициент уменьшение
увеличение
7 1Е+30
3
4 1
8
1 175
3
9 6667 1Е+30
1


62
2.4. ТРАНСПОРТНАЯ ЗАДАЧА

Транспортная задача является одной из наиболее распространенных
задач линейного программирования и находит широкое практическое
приложение.
Постановка транспортной задачи. Некоторый однородный продукт,
сосредоточенный у т поставщиков Л, в количестве а{ (i = 1,..., т) единиц,
необходимо доставить п потребителям В, в количестве bs(j = 1, ..., п) ед.
Известна стоимость сц перевозки единицы груза от г-го поставщика ку'-му
потребителю.
Необходимо составить план перевозок, позволяющий вывести все
грузы, полностью удовлетворить потребности и имеющий минимальную
стоимость.
Сформулируем экономико-математическую модель транспортной
задачи. Обозначим через хц количество единиц груза, запланированных
к перевозке от /-го поставщика к j-му потребителю. Так как от i-ro по­
ставщика к у'-му потребителю запланировано к перевозке ху единиц гру­
за, то стоимость перевозки составит сц х,г
Стоимость всего плана выразится двойной суммой
тп
Z= 2J2JCIJXV

Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть перевезены, т.е.
п
Х*!/ =а ;, i = \,...,m,
7=1
б) все потребности должны быть удовлетворены, т.е.
т
X *!/=?;. j = \,...,n.
/=1
Таким образом, математическая модель транспортной задачи имеет
следующий вид: найти минимальное значение линейной функции
тп
z
= llcvxv (2-4-1)
i=ly=l
при ограничениях

63
?xy=a, i = ],..., т; (2.4.2)
7=1
т
Y.x,j=bj, j = l....,n; (2.4.3)
(=1
ху>0, i = \,...,m, j = \,...,n. (2.4.4)

В рассмотренной модели предполагается, что суммарные запасы
равны суммарным потребностям, т.е.
т п
X*. = X V (2-4.5)
1=1 у=1

Транспортная задача, в которой суммарные запасы и потребности
совпадают, т.е. выполняется условие (2.4.5), называется закрытой моде­
лью; в противном случае - открытой. Для открытой модели может быть
два случая:
а) суммарные запасы превышают суммарные потребности

т п
X*, > Ibj,
/=1 у=1



б) суммарные потребности превышают суммарные запасы

т п

x°.>xv
»=1 7=1


Линейная функция одинакова в обоих случаях, изменяется только
вид системы ограничений.
Найти минимальное значение линейной функции


^ ˜ 2^ 2^ ^у хи
i=U=i
при ограничениях

64
J=l
7=1 , - ч
(случаи а)
m
mx =b
Xy j, j = l—,n, xv >0;




(случай б)
m
ХХУ ˜bJ, j = h--,n, X,j >0.

Открытая модель решается приведением к закрытой модели.
В случае а, когда суммарные запасы превышают суммарные по­
требности, вводится фиктивный потребитель В„+\, потребность которого

т п

Vi^X^-X^ •
1=1 у=1


В случае б, когда суммарные потребности превышают суммарные
запасы, вводится фиктивный поставщик Ат+\, запасы которого

п т


7 =1 i=l



Как стоимость перевозки единицы груза до фиктивного потребите­
ля, так и стоимость перевозки груза от фиктивного поставщика полага­
ются равными нулю, так как груз в обоих случаях не перевозится.
Транспортная задача имеет п + т уравнений с т • п неизвестными.
Матрицу X = (xtl)m„, удовлетворяющую условиям (2.4.2) - (2.4.4),
называют планом перевозок транспортной задачи (^„-перевозками).
План X*, при котором целевая функция (2.4.1) обращается в мини­
мум, называется оптимальным.


65
Решение транспортной задачи
с помощью средства EXCEL «Поиск решения»

Исходные данные транспортной задачи приведены схематически:
внутри прямоугольника заданы удельные транспортные затраты на пере­
возку единицы груза (с,;), слева указаны мощности поставщиков (a,-), a
сверху - мощности потребителей (ty). Найти оптимальный план закреп­
ления поставщиков за потребителями (*,,).

Мощности Мощности потребителей
поставщиков 100 50
250 150
4
80 6 6 1
320 8 30 6 5
4 3 30
100 5
9 9
50 9 9


В данной задаче суммарные запасы равны суммарным потребно­
стям, т.е.
т п
2>, = 2>7=550.
1=1 7=1


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

Ввод условий задачи состоит из следующих основных шагов:
1. Создание формы для ввода условий задачи.
2. Ввод исходных данных.
3. Ввод зависимостей из математической модели.
4. Назначение целевой функции.
5. Ввод ограничений и граничных условий.

66
А В С D Е *v'--,!?'•••.
1
2 Матриц!i перевозок (изменяемые ячейки)
,•3 1 1 1
1
1
I

5 1 !
1 1
1 1
Ц 1
JL
8 Исходные данные
250 100 150 50
-9
80
1L 6 1 4
б
320 Щ 5
8 30
11
100 5 4 3; 30
12
9
50 9: 9
9
13
14
1
Рис. 2.4.1. Создание формы для ввода условий задачи.
Изменяемые ячейки - ВЗ:Е6. В эти ячейки будет записан опти­
мальный план перевозок - ху. Введены исходные данные задачи.

'." :,::.::'
Установить целевую ячейку: ]$в$15vj ^полнить j
Равной: С максимальному значению С" качению: |0
Закрыть
{* минимальному значению
изменяя ячейки;—;——

|$В$3:$Е$б Предположить
мп.тя


Параметры
щ*раничения;
$А$3:$А$6 = $А$10:$А$13 Добавить
JJ
•1$В$7:$Е$7 = $Б$9:$Е$9

Восстановить

Справка


Рис. 2.4.2. Введены зависимости из математической модели. Выражение для вычисления
значения целевой функции получено с помощью функции СУММПРОИЗВ(ВЗ:Е6,ВЮ:Е13).

67
IIP
••:• .."""iji'?.-:




Установить целевую ячейку: j$B$15_Vj Выполнить
Равной: С максимальному значению значению: Закрыть
(* минимальному значению
г Мзменая ячейки: —
!| • —.
°У Предположить
| 1$В$3'$Е$6
Параметры
Ограничения:-



Восстановить

Справка

Рис. 2.4.3. На экране диалоговое окно Поиск решения.

После вызова Поиска решения курсор подвести в поле «Установить
целевую ячейку» и ввести адрес: В15. Ввести направление целевой функ­
ции «минимальному значению». Поместить курсор в поле «Изменяя ячей­
ки». Ввести адреса изменяемых ячеек ВЗ:Е6. Далее следует добавить
ограничения.

!
в D Н

Матрица перево: ок (изменяемые»•ейюО

И* Сшшнзрйзе Ограничение:
ijjp"
|$А$З$А$6 •j||=$A$10$A$13 V|
4

Ж —t—
Добавить | Сдада 1
Ш Отеенз j
7 • ч
р Исходные иииые




1

Рис. 2.4.4. На экране диалоговое окно Добавление ограничения.

68
Все грузы должны быть перевезены, т.е.


Х% / , / = 1 , . . , W - A 3 A 6 = A1D A.13.
7=1

t
F О i H
i!
*•
Maipmvi перевозок (изменяемые ячейки)
i 4 1
Сложена эчейсу?
4 1

<< Пред. стр.

страница 8
(всего 15)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign