Модели оптимального объема производства

Тип работы:
Курсовая
Предмет:
Экономические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Санкт-Петербургский государственный горный университет

Кафедра информатики и компьютерных технологий

Курсовая работа

По дисциплине: Экономико-математические модели и методы

Модели оптимального объема производства

Выполнил: студент ЛГ-08

Перцева Е.А.

Проверил: Доцент

Петухова Н.М.

Санкт-Петербург 2012

Содержание

1. Введение

2. Задача 1

3. Задача 2

4. Задача 3

5. Задача 4

1. Введение

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

1)построение математической модели

2)нахождение оптимального решения, используя математические методы

3)решение задачи средствами Excel

модель оптимальный объем производство перевозка

2. ЗАДАЧА 1

УСЛОВИЯ ЗАДАЧИ

Цех предприятия производит два вида изделий, А и В, для изготовления которых требуются ресурсы трех видов R1, R2, R3. Данные о наличии ресурсов, количество ресурсов каждого вида, необходимое для изготовления тысячи изделий, А и В (нормы расхода), а также прибыль, получаемая от реализации тысячи изделия каждого вида, приведены в табл. 1.1. Определить оптимальные объемы производства каждого вида изделий за плановый период, обеспечивающие максимальную прибыль предприятию.

Таблица 1. 1

Виды ресурсов

Наличие

Нормы расхода

Тип А

Тип В

R1

200

10

5

R2

100

2,5

5

R3

60

2

1,2

Прибыль от продажи

15

16

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Пусть за плановый период выпускается Х1 (тыс. шт.) изделий А и Х2 (тыс. шт.) изделий В. По условию задачи (табл. 1) прибыль, получаемая от реализации 1000 шт. изделий А, составляет 15 (уел. ед.), а 1000 шт. изделий В — 16 (усл. ед.).

Тогда прибыль, получаемая от реализации Xt (тыс. шт.) изделий А и Х2 (тыс. шт.) изделий В, выпущенных за плановый период, может быть записана в виде выражения Z= 15 Х1+16Х2.

Отрицательные значения Х1 и Х2 не имеют смысла, то есть Х1 > =0, Х2 > =0.

Величины Х1 и Х2 нельзя выбирать произвольно, так как на них накладываются ограничения, определяемые наличием ресурсов R1, R2, R3. Как видно из табл. 1, для изготовления тыс. шт. изделий А требуется 10 (ед.) ресурса R1, а для изготовления тыс. шт. изделий В — 5 (ед.) ресурса R1. Следовательно, расход ресурса R1 для выпуска Х1 (тыс. шт.) изделий А составит 10 Х1 (ед.), а для выпуска Х2 (тыс. шт.) изделий В — 2 (ед.). Таким образом, для планового выпуска деталей А и В потребуется 10 Х1+ 2 (ед.) ресурса R1. В связи с тем, что запас ресурса R1 составляет 200 (ед.), ограничение по нему будет иметь вид: 10 Х1 + 2, <= 200;

Аналогично рассуждая, можно составить ограничения для ресурсов R2 и R3: R2: 2,5Х1 + 2<= 100;

R3: 2 Х1 + 1,2Х2<= 60.

Получили математическую модель задачи.

Имеем целевую функцию линейной формы:

Z = 15Xi + 12 --> шах (1)

систему линейных ограничений:

10 Х1 + 2, <= 200

2,5Х1 + 2<= 100 (2)

2 Х1 + 1,2Х2<= 60

и граничные условия: X, >= 0, Х2 > =0 (3)

Задача формулируется следующим образом: найти такие неотрицательные значения переменных X, и Х2, которые будут удовлетворять системе ограничений (2) и обращать в максимум целевую функцию (1).

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

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ

Введем на плоскости прямоугольную систему координат Х1, Х2.

ОПРЕДЕЛЕНИЕ ОБЛАСТИ ДОПУСТИМЫХ РЕШЕНИЙ

Область допустимых решений определяется граничными условиями (3) и системой неравенств (2). Граничные условия Х1 > =0, Х2 > =0 указывают на то, что область допустимых решений находится в 1-м квадранте.

Построим систему неравенств (2). Каждое неравенство геометрически определяет полуплоскость с граничными прямыми

10 Х1 + 2, <= 200

2,5Х1 + 2<= 100 (4)

2 Х1 + 1,2Х2<= 60

Построим эти прямые (рис. 1). Каждая из них делит плоскость на две полуплоскости. Решение следует искать в той полуплоскости, все точки которой удовлетворяют неравенству. Чтобы определить эту полуплоскость, возьмем какую-нибудь точку на плоскости, например точку с координатами (0,0). Если приравнять нулю значения Х1 и Х2 в левой части соответствующих неравенств, получим соотношение 0 <= const, значит точка с координатами (0,0) входит в полуплоскость, соответствующую рассматриваемому неравенству. Во все полуплоскости, соответствующие ограничениям (2) входит начало координат (при Х1=Х2=0 10 Х1 + 5Х2, <= 200, 2,5Х1 + 5Х2<= 100, 2 Х1 + 1,2Х2<= 60). Так как система (2) совместна, то полуплоскости, пересекаясь, образуют общую для всех полуплоскостей часть, которая представляет собой многоугольник. Таким образом, определили область, удовлетворяющую всем ограничениям и граничным условиям, то есть область допустимых решений (многоугольник решений). Известно, что оптимальное решение должно находиться на границе этой области, и, если решение единственное, в одной из ее вершин. Точка с координатами (X1, Х2), в которой значение целевой функции достигает максимума, должна находиться в одной из вершин выделенного многоугольника.

НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ

Проведем линию уровня целевой функции, проходящую через начало координат:

Z= 15Х1 + 16Х2 = 0.

Значение Z возрастает в направлении нормального вектора п = {15; 16}. Будем передвигать прямую параллельно самой себе в направлении вектора п до тех пор, пока многоугольник решений не будет находиться по одну сторону от нее, и прямая не будет иметь с ним, по крайней мере, одну общую точку. Этой точкой будет точка С с координатами Х1 = 13,3 и Х2= 13,3, в которой целевая функция Z принимает максимальное значение. Подставив значения Х1= 13,3 и Х2= 13,3 в целевую функцию Z= 15Х1 + 16Х2 = 0. Получим ее максимальное значение Z = 15•13,3+16•13,3 =413.

Общая прибыль от реализации x1 изделий вида, А и x2 изделий вида В составит:

Z=15•x1+16•x2> max

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

Решим неравенства, преобразовав их в равенства:

1) 10•x1+5•x2=200

x1=0 > x2=40

x2=0 > x1=20

2) 2,5•x1+5•x2=100

x1=0 > x2=20

x2=0 > x1=40

3) 2•x1+1,2•x2=60

x1=0 > x2=50

x2=0 > x1=30

10•x1+5•x2=200

2,5•x1+5•x2=100

x1=13,3 (13)

x2=13,3 (13)

Z=15•13,3+16•13,3=413

Это оптимальное решение.

(Точность решения задачи будет зависеть от точности построения графика.)

Ответ: max Z =413 при Xt = 13,3, Х2 = 13,3.

ИСПОЛЬЗОВАНИЕ СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧИ

Определение базисного (допустимого) решения

10•x1+5•x2?200 10•x1+5•x2+x3=200

2,5•x1+5•x2?100 2,5•x1+5•x2+x4=100

2•x1+1,2•x2?60 2•x1+1,2•x2+x5=60

x1, x2, x3, x4, x5?0 Z=15•x1+16•x2+0•x3+0•x4+0•x5

x3=200-(10•x1+5•x2)

x4=100-(2,5•x1+5•x2)

x5=60-(2•x1+1,2•x2)

Z=0-(-15•x1-16•x2-0•x3-0•x4-0•x5)

x1=0, x2=0, x3=200, x4=100, x5=60

1. Из отрицательных элементов последней строки табл.1. 2, соответствующих переменным x1 и x2, выберем максимальный по модулю элемент: -16, соответствует x2. Небазисная переменная x2 должна быть введена в базис. 2. Поделим элементы столбца значений базисных переменных на соответствующие положительные коэффициенты выбранного столбца: 200/5=40

100/5=20

60/1,2=50

Запишем частные от деления во вспомогательный столбец б. Выберем элемент, который дает минимальное частное от деления: 20. Минимальное частное 20 соответствует второй строке с базисной переменной x4. Переменная x4 должна быть выведена из базиса.

3. Разделим элементы выбранной строки (второй строки) на разрешающий элемент (5). Результат запишем во вторую строку симплекс-таблицы 9. Построение первой строки симплекс-таблицы 1. 3

4. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент первого элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов первой строки симплекс-таблицы 1.2. Получим первую строку симплекс-таблицы 1.3.

Построение третьей строки симплекс-таблицы 1.3.

5. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент третьего элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов третьей строки симплекс-таблицы 1.2. Получим третью строку симплекс-таблицы 1.3.

Построение четвертой строки симплекс-таблицы 1. 3

6. Элементы полученной второй строки симплекс-таблицы 1.3 умножим на коэффициент четвертого элемента выделенного столбца симплекс-таблицы 1.2 и вычтем из соответствующих элементов четвертой строки симплекс-таблицы 1.2. Получим четвертую строку симплекс-таблицы 1.3. 7. В симплекс-таблице 1.3 проделываются аналогичные операции, что и в симплекс-таблице 1.2. Полученные результаты записываем в симплекс-таблицу 1.4.

Таблица 1. 2

Базисные переменные

Значения базисных переменных

Коэффициенты

х1

х2

х3

х4

х5

б

1

х3

200

10

5

1

0

0

40

2

х4

100

2,5

5

0

1

0

20

3

х5

60

2

1,2

0

0

1

50

4

z

0

-15

-16

0

0

0

Таблица 1. 3

Базисные переменные

Значения базисных переменных

Коэффициенты

х1

х2

х3

х4

х5

б

1

х3

100

7,5

0

1

-1

0

13,3

2

х2

20

0,5

1

0

0,2

0

40

3

х5

36

1,4

0

0

-0,24

1

25,7

4

z

320

-7

0

0

3,2

0

Проверим, является ли данное решение допустимым.

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

Проверка на оптимальность:

целевая функция имеет максимальное значение, так как все коэффициенты в строке целевой функции положительны.

Таблица 1. 4

Базисные переменные

Значения базисных переменных

Коэффициенты

х1

х2

х3

х4

х5

1

x1

13,33

1

0

0,1333

-0,133

0

2

x2

13,33

0

1

-0,07

0,27

0

3

x5

17,33

0

0

-0,19

-0,05

1

4

z

413

0

0

1

2

0

Двойственная задача

Исходная задача Двойственная задача

10•x1+5•x2?200 10•y1+2,5•y2+2•y3?15

2,5•x1+5•x2?100 5•y1+5•y2+1,2•y3?16

2•x1+1,2•x2?60

x1, x2?0

Z=15•x1+16•x2> max Zд=200•y1+100•y2+60•y3> min

Анализ оптимального решения

При увеличении ресурса Ri: Z=Zопт+yi•1

При уменьшении ресурса Ri: Z=Zопт-yi•1

R1: Z=Zопт+1•1=413+1=414

Z=Zопт-1•1=413−1=412

R2: Z=Zопт+2•1=413+2=415

Z=Zопт-2•1=413−2=411

R3: Z=Zопт+0•1=413+0=413

Z=Zопт-0•1=413−0=413

Отчёты по пределам

Z=15•13,3+16•13,3=413

Для значения х1 на нижнем пределе:

Z=15•0+16•13,3=213

Для значения х2 на нижнем пределе:

Z=15•13,3+16•0=200

РЕШЕНИЕ ЗАДАЧИ В EXCEL

Для решения задачи составьте электронную таблицу, отражающую ее математическую модель (рис. 2, 3). На рис. 2 показана электронная таблица в режиме отображения вычислений (исходное состояние), на рис. 3 — в режиме отображения формул. На рисунках введено сокращение: ЦФ — целевая функция.

Рис. 2

Рис. 3

переменные

х1

х2

значение

0

0

цф

коэф вцф

15

16

=СУММПРОИЗВ (B3: C3;B5:C5)

ресурсы

левая часть

знак

правая часть

R1

10

5

=СУММПРОИЗВ ($B$ 3: $C$ 3;B8:C8)

?

200

R2

2,5

5

=СУММПРОИЗВ ($B$ 3: $C$ 3;B9:C9)

?

100

R3

2

1,2

=СУММПРОИЗВ ($B$ 3: $C$ 3;B10:C10)

?

60

Работа в диалоговом окне «Поиск решения»

Для подготовки к решению задачи оптимизации выполните команду: Сервис — Поиск решения. На экране появится диалоговое окно Поиск решения (рис. 4). Выполните следующие действия:

В поле Установить целевую ячейку введите адрес $D$ 5.

Для выбора направления изменения целевой функции установите переключатель в положение Максимальному значению.

Рис. 4

В поле Изменяя ячейки введите адрес блока ячеек $ 3: $С$ 3.

4. Введите граничные условия и ограничения: щелкните по кнопке Добавить. На экране появится диалоговое окно Добавление ограничения. Для ввода граничных условий Х1чХ2 > 0 в поле Ссылка на ячейку введите левую часть отношения (B3: СЗ), в следующее поле — его знак (?), в последнее поле введите правую часть ограничения — 0. Щелкните по клавише Добавить. На экране появится диалоговое окно Добавление ограничения. Введите ограничения по ресурсам: D8: D10 ? F8: F10 аналогичным образом и щелкните по кнопке ОК. На экране появится диалоговое окно Поиск решения с введенными ограничениями (рис. 5).

Решение задачи Решение задачи будем производить в диалоговом окне Поиск решения. В нем выполните следующие действия:

1. Щелкните по кнопке Параметры. Появится диалоговое окно Параметры поиска решения (рис. 6).

2. Установите Максимальное время решения задачи (оставьте предлагаемое по умолчанию — 100 с), Предельное число итераций (оставьте предлагаемое по умолчанию — 100).

3. Установите флажок Линейная модель.

4. Нажмите ОК. Появится диалоговое окно Поиск решения.

5. Щелкните по кнопке Выполнить. Появится диалоговое окно Результаты поиска решения (рис. 7).

Рис. 5

Рис. 6

Рис. 7

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

Закройте окно, нажав ОК. На экране появится исходная таблица с результаты решения задачи (рис. 8): в блоке ячеек ВЗ: СЗ — значения переменных Х12 1=13,33, Х2=13,33), в ячейке D5 — максимальное значение целевой функции (413,33).

Результаты решения в Excel совпадают с результатами, полученными при решении задачи графическим методом и симплекс-методом.

Рис. 8

Анализ оптимального решения задачи в Excel

Отчет по результатам

Щелкните мышью по ярлычку Отчет по результатам. На экране появится лист данного отчета (рис. 9).

В верхней таблице отчета указан номер ячейки — $D$ 5 (целевой ячейки), в которой находится значение целевой функции, исходное, равное 0, и результирующее — максимальное значение целевой функции — 413,33, полученное в результате решения задачи оптимизации.

В средней таблице отчета располагаются номера ячеек, в которых находятся значения искомых переменных Х1 и Х2, исходные (равные нулю) и результирующие значения (соответственно 13,33 и 13,33), при которых целевая функция достигает максимального значения.

Рис. 9

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

Ниже приводятся номера ячеек, в которых располагаются значения искомых переменные Х1 и Х2 и их значения, при которых целевая функция достигает максимального значения.

Отчет по устойчивости

Щелкните мышью по ярлычку Отчет по устойчивости. На экране появится лист данного отчета (рис. 10).

Рис. 10

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

В таблице Изменяемые ячейки выводятся номера ячеек, в которых находятся искомые переменные Х1 и Х2 и их значения, при которых целевая функция достигает максимума.

В столбце Целевой коэффициент приводятся значения коэффициентов при изменяемых переменных Х1 и Х2 в выражении целевой функции.

Столбцы Допустимое увеличение и Допустимое уменьшение

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

В таблице Ограничения содержится информация об ограничениях, накладываемых на оптимизируемые переменные.

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

Данные столбца Теневая цена характеризуют изменение значения целевой функции (Z) при увеличении на единицу значения соответствующего ограничения (для ресурсов R1, R2, R3), т. е. двойственные оценки (Y1 Y2, Y3)

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

Отчет по пределам

Щелкните по ярлычку Отчет по пределам. Появится окно отчета (рис. 11).

Рис. 11

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

Z= 15Х1 + 16Х2 = 15Ч13,33 + 16Ч13,33 = 76,7+ 73,3 = 413,3 — оптимальное решение.

Задача 2

Условие задачи

Предприятию требуется перевезти товары стрех складов (S1, S2, S3) в четыре магазина (Ml, М2, МЗ, М4). Данные о наличии товаров на складе, спрос на него в магазинах, а также стоимости перевозки тысячи штук товара (в условных единицах) со складов в магазины приведены в табл. 2,1. Составить такой план перевозки товаров, при котором затраты будут минимальными. (Транспортировка товаров возможна с любого склада в любой магазин.)

Таблица 2. 1

Наличие товаров на складах

Спрос на товары в магазинах

Ml

М2

МЗ

М4

30

10

30

30

S1

25

6

10

4

7

S2

45

9

12

6

4

S3

30

2

3

5

8

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

Пусть Xij — количество товара, отправляемого из склада i в магазин j, Cij — стоимость перевозки тысячи единиц товара со склада i в магазин j. Очевидно, что Xij ? 0 и Cij ? 0. В силу ограничений наличие товара на складах и спрос на него в магазинах величина должны выполняться следующие условия:

1.

X11 + X12 + X13 + X14 = 25

X21 + X22 + X23 + X24 = 45

X31 + X32 + X33 + X34 = 30

2.

X11 + X21 + X31 = 30

X12 + X22 + X32 = 10

X13 +X23 + X33 = 30

X14 +X24 + X34 = 30

Общая стоимость перевозок равна:

Для рассматриваемого примера

Z = 6 • X11 + 10 • X12 + 4 • X13 + 7 • X14 + 9 • X21 + 12 • X22 + 6 • X23 + 4 • X24 + 2 • X31 +3 • X32 + 5 • X33 + 8 • X34

Задача формулируется следующим образом: определить такие неотрицательные значения переменных Xij, которые удовлетворяют ограничениям 1 и 2 и обращают в минимум целевую функцию Z. В такой постановке является транспортной задачей линейного программирования. Необходимым и достаточным условием разрешимости транспортной задачи является условие баланса:

Где

= - суммарное количество товара на складах;

= - суммарное количество товара, требуемое в магазинах.

В данной задаче

= 100,

Следовательно, задача с балансом.

РЕШЕНИЕ ЗАДАЧИ

Решение транспортной задачи состоит из двух этапов:

Определение допустимого решения (базисного решения).

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

Определение допустимого решения методом северо-западного угла

Согласно условию задачи составим таблицу. (тарифы cij располагаются в нижнем правом углу ячейки)

Рассмотрим маршрут доставки от поставщика S1 к потребителю M1 (ячейка S1M1). Запасы поставщика S1 составляют 25 единиц продукции. Потребность потребителя M1 составляет 30 единиц продукции. От поставщика S1 к потребителю M1 будем доставлять min = { 25, 30 } = 25 единиц продукции. Разместим в ячейку S1M1 значение равное 25

Мы полностью удовлетворили потребность потребителя S1. Вычеркиваем строку 1 таблицы, т. е исключаем её из дальнейшего рассмотрения.

Таблица 2. 2

Остатки

Mi

5

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25

10

4

7

S2 = 45

9

12

6

4

S3 = 30

2

3

5

8

Рассмотрим маршрут доставки от поставщика S2 к потребителю M1 (ячейка S2M1).

Запасы поставщика S2 составляют 45 единиц продукции. Потребность потребителя M1 составляет 5 единиц продукции. От поставщика S2 к потребителю M1 будем доставлять min = { 45, 5 } = 5 единиц продукции.

Разместим в ячейку S2M1 значение равное 5

Мы полностью израсходoвали запасы поставщика M1. Вычеркиваем столбец 1 таблицы, т. е исключаем его из дальнейшего рассмотрения.

Таблица 2. 3

Остатки

Mi

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25

10

4

7

40

S2 = 45

9

5

12

6

4

S3 = 30

2

3

5

8

Рассмотрим маршрут доставки от поставщика S2 к потребителю M2 (ячейка S2M2). Запасы поставщика S2 составляют 40 единиц продукции. Потребность потребителя M2 составляет 10 единиц продукции. От поставщика S2 к потребителю M2 будем доставлять min = { 40, 10 } = 10 единиц продукции. Разместим в ячейку S2M2 значение равное 10

Мы полностью удовлетворили потребность потребителя M2. Вычеркиваем столбец 2 таблицы, т. е исключаем его из дальнейшего рассмотрения.

Таблица 2. 4

Остатки

Mi

0

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25

10

4

7

30

S2 = 45

9

5

12

10

6

4

S3 = 30

2

3

5

8

Рассмотрим маршрут доставки от поставщика S2 к потребителю M3 (ячейка S2M3).

Запасы поставщика S2 составляют 30 единиц продукции. Потребность потребителя M3 составляет 30 единиц продукции. От поставщика S2 к потребителю M3 будем доставлять min = { 30, 30 } = 30 единиц продукции.

Разместим в ячейку S2M3 значение равное 30

Мы полностью израсходoвали запасы поставщика S2 и удовлетворили потребность потребителя M3. Вычеркиваем строку 2 таблицы и столбец 3, т. е исключаем их из дальнейшего рассмотрения.

Таблица 2. 5

Остатки

Mi

0

0

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25

10

4

7

0

S2 = 45

9

5

12

10

6

30

4

S3 = 30

2

3

5

8

Рассмотрим маршрут доставки от поставщика S3 к потребителю M4 (ячейка S3M4).

Запасы поставщика S3 составляют 30 единиц продукции. Потребность потребителя M3 составляет 30 единиц продукции.

От поставщика S3 к потребителю M4 будем доставлять min = { 30, 30 } = 30 единиц продукции.

Разместим в ячейку S3M4 значение равное 30

Мы полностью удовлетворили потребность потребителя M4 и израсходовали запасы поставщика S3. Вычеркиваем столбец 4 и строку 3 таблицы, т. е исключаем его из дальнейшего рассмотрения.

Таблица 2. 7

Остатки

Mi

0

0

0

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25

10

4

7

0

S2 = 45

9

5

12

10

6

30

4

0

S3 = 30

2

0

3

5

8

30

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

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n — 1, где m — количество строк в таблице, n — количество столбцов в таблице.

Количество базисных ячеек (задействованных маршрутов) равно 6, что и требовалось.

Мы нашли начальное решение, т. е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Z = 6 * 25 + 5 * 9 + 10 * 12 + 30 * 6 + 30 * 8 = 735 ден. ед.

Общие затраты на доставку всей продукции, для начального решения, составляют 735 ден. ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число — ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число — vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij — тариф клетки SiMj)

Поскольку, число базисных клеток — 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v1 = 0.

V1 + u1 = c11 v1 + u1 = 6 u1 = 6 — 0 = 6

V1 + u2 = c21 v1 + u2 =9 u2 = 9 — 0 = 9

V2 + u2 = c22 v2 + u2 = 12 v2 = 12 — 9 = 3

V3 + u2 = c23 v3 + u2 = 6 v3 = 6 — 9 = -3

V1 + u3 = c31 v1 + u3 = 2 u3 = 2 — 0 = 2

V4 + u3 = c34 v4 + u3 = 8 v4 = 8 — 2 = 6

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

Таблица 2. 8

Склады

Магазины

М1=

30

М2=

10

М3 =

30

М4 =

30

Ui

S1 =25

4

5

6

7

U1=6

S2 = 45

5

6

9

2

U2=9

S3 = 30

1

5

4

3

U3=-2

Vj

V1=0

V2=3

V3=-3

V4=6

G12 = c12 — (u1 + v2 ) = 10 — (6 + 3) = 1

G13 = c13 — (u1 + v3 ) = 4 — (6 + (-3)) = 1

G14 = c14 — (u1 + v4 ) = 7 — (6 + 6) = -5

G24 = c24 — (u2 + v4 ) = 4 — (9 + 6) = -11

G31 = c31 — (u3 + v2 ) = 3 — (2 + 3) = -2

G32 = c32 — (u3 + v3 ) = 5 — (2 + (-3)) = 6

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

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке S1M4 (14=-5).

Построим цикл для выбранной ячейки S1M4:

Среди ячеек цикла S1M4, S1M1, S3M1, S3M4 номера которых четные, найдем ячейку, обладающую найменьшим значением.

min = { 25, 30} = 25 В данном случае это ячейка S1M1.

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

От ячеек цикла с четными номерами отнимает 25. К ячейкам с нечетными номерами прибавляем 25.

Таблица 2. 9

Остатки

Mi

0

0

0

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

25-25

10

4

7

+25

0

S2 = 45

9

5

12

10

6

30

4

0

S3 = 30

2

0+25

3

5

8

30-25

Таблица 2. 10

Остатки

Mi

0

0

0

0

Склады

Магазины

Si

М1=

30

М2=

10

М3 =

30

М4 =

30

0

S1 =25

6

10

4

7

25

0

S2 = 45

9

5

12

10

6

30

4

0

S3 = 30

2

25

3

5

8

5

Общие затраты на доставку всей продукции, для данного решения, составляют:

Z = 5* 9 + 2 * 25 + 12 * 10 + 6 * 30 + 7 * 25+5*8 = 610 ден. ед.

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

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число — ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число — vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij — тариф клетки SiMj)

Поскольку, число базисных клеток — 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем u2 = 0

v1 + u2 = c21 v1 + u2 = 9 v1 = 9 — 0 = 9

v2 + u2 = c22 v2 + u2 = 12 v2 = 12 — 0 = 12

v3 + u2 = c23 v3 + u2 = 6 v3 = 6 — 0 = 6

v1 + u3 = c31 v1 + u3 = 2 u3 = 2 — 9 = -7

v4 + u3 = c34 v4 + u3 = 8 v4 = 8 — (-7) = 15

v4 + u1 = c14 v4 + u1 = 7 u1 = 7 — 15 = -8

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

Таблица 2. 11

Склады

Магазины

М1=

30

М2=

10

М3 =

30

М4 =

30

Ui

S1 =25

6

10

4

7

U1=-8

S2 = 45

9

12

6

4

U2=0

S3 = 30

2

3

5

8

U3=-7

Vj

V1=9

V2=12

V3=6

V4=15

G11 = c11 — (u1 + v1 ) = 6 — (-8 + 9) = 5

G12 = c12 — (u1 + v2 ) = 10 — (-8 + 12) = 6

G13 = c13 — (u1 + v3 ) = 4 — (-8 + 6) = 6

G24 = c24 — (u2 + v4 ) = 4 — (0 + 15) = -11

G32 = c32 — (u3 + v2 ) = 3 — (-7 + 12) = -2

G33 = c33 — (u3 + v3 ) = 5 — (-7 + 6) = 6

Среди оценок свободных ячеек есть отрицательные, следовательно решение не является оптимальным. Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки остановим свой выбор на ячейке S2M4 (G24=-11)

Построим цикл для выбранной ячейки S2M4

Ячейки образующие цикл для свободной ячейки S2M4:

S2M4, S2M1, S3M1, S3M4

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

Среди ячеек цикла S2M1, S3M4 номера которых четные, найдем ячейку, обладающую наименьшим значением

Min = {5,5} = 5

В данном случае, таких ячеек две. Остановим выбор на ячейке S2M1

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

От ячеек цикла с четными номерами отнимаем 5. К ячейкам с нечетными номерами прибавляем 5.

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

Таблица 2. 12

Склады

Магазины

М1=

30

М2=

10

М3 =

30

М4 =

30

S1 =25

6

10

4

7

25

S2 = 45

9

5-5

12

10

6

30

4

+5

S3 = 30

2

25+5

3

5

8

5−5

Таблица 2. 13

Склады

Магазины

М1=

30

М2=

10

М3 =

30

М4 =

30

S1 =25

6

10

4

7

25

S2 = 45

9

12

10

6

30

4

5

S3 = 30

2

30

3

5

8

Z=2*30+12*10+6*30+7*25+4*5=555 ден. ед.

ОПРЕДЕЛИМ ОПТИМАЛЬНОЕ РЕШЕНИЕ МЕТОДОМ ПОТЕНЦИАЛОВ.

Каждой строке Si ставим в соответствие некоторое число — ui, называемое потенциалом поставщика.

Каждому столбцу Mj ставим в соответствие некоторое число — vj, называемое потенциалом потребителя.

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

(ui + vj = cij, где cij — тариф клетки SiMj)

Поскольку, число базисных клеток — 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.

Примем v4 = 0

V4 + u1 = c14 v4 + u1 = 7 u1 = 7 — 0 = 7

V4 + u2 = c24 v4 + u2 = 4 u2 = 4 — 0 = 4

V4 + u3 = c34 v4 + u3 = 8 u3 = 8 — 0 = 8

V2 + u2 = c22 v2 + u2 = 12 v2 = 12 — 4 = 8

V3 + u2 = c23 v3 + u2 = 6 v3 = 6 — 4 = 2

ПоказатьСвернуть
Заполнить форму текущей работой