Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

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

по дисциплине «Экономико-математическое моделирование»

Для студентов 3 курса заочного отделения

направление подготовки38.03.01 Экономика (бакалавр)

профиль"Финансы и кредит"

VI семестр (2016/17 уч. год)

 


Содержание

 

 

Задание № 1. 3

Задание № 3. 21

Задание № 4. 29

Задание № 5. 33

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 36

 

 


Задание № 1

 

Решить графическим методом задачу линейной оптимизации при условиях:

В-нт
2,12     -1   -2 -1          

 

Решение:

 

Необходимо найти максимальное значение целевой функции:

F = x1+2x2 → max,

при системе ограничений:

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

а) Построим уравнение -x1+x2 = -2 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = -2. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 2. Соединяем точку (0;-2) с (2;0) прямой линией. Определим полуплоскость, задаваемую неравенством.

Выбрав точку (0; 0), определим знак неравенства в полуплоскости:

-1*0+1*0+2 ≥ 0, т.е. -x1+x2 + 2≥ 0 в полуплоскости ниже прямой.

б) Построим уравнение -x1+2x2 = 12 по двум точкам.

Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 6. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = -12. Соединяем точку (0;6) с (-12;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:

-1* 0 + 2* 0 - 12 ≤ 0, т.е. -x1+2x2 - 12≤ 0 в полуплоскости ниже прямой.

в) Построим уравнение 3x1+x2 = 15 по двум точкам. Для нахождения первой точки приравниваем x1 = 0. Находим x2 = 15. Для нахождения второй точки приравниваем x2 = 0. Находим x1 = 5. Соединяем точку (0;15) с (5;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости:

3*0 + 1*0 - 15 ≤ 0, т.е. 3x1+x2 - 15≤ 0 в полуплоскости ниже прямой.


или

 

2) Определяем границы области допустимых решений.

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

Обозначим границы области многоугольника решений.

3) Рассмотрим целевую функцию задачи F = x1+2x2 → max.

Построим прямую, отвечающую значению функции F = 0:

F = x1+2x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (1; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

-x1+2x2=12

3x1+x2=15

Решив систему уравнений, получим:

x1 = 2.5714,

x2 = 7.2857

Откуда найдем максимальное значение целевой функции:

F(X) = 1*2.5714 + 2*7.2857 = 17.1429

Изменение коэффициентов целевой функции.

Изменение значений коэффициентов c1 и c2 приводит к изменению угла наклона прямой z. Существует интервалы изменения коэффициентов c1 и c2, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации.

Необходимо определить интервал оптимальности для отношения c1 / c2 (или c2 и c1). Если значение отношения c1 / c2 не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным.

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

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

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

На предыдущем рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых

(-x1+2x2=12) и (3x1+x2=15).

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

при условии c1 ≠ 0

Или

при условии c2 ≠ 0

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

При c2 = 2

Или

-1 ≤ c1 ≤ 6

При c1 = 1

Или

-2 ≤ c21/3

Оценка ресурсов.

На данном этапе важно проанализировать следующие аспекты:

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

2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.

Оценка ресурса M2

Концевые точки отрезка определяют интервал осуществимости для ресурса M2.

Количество сырья, соответствующего точке (4.25,2.25), равно:

-1*4.25 + 2*2.25 = 0.25

Количество сырья, соответствующего точке (0,15), равно:

-1*0 + 2*15 = 30

Таким образом, интервал осуществимости для ресурса M2 составляет:

0.25 ≤ M2 ≤ 30

Вычислим значение целевой функции в этих точках:

F(4.25,2.25) = 1·4.25 + 2·2.25 = 8.75

F(0,15) = 1·0 + 2·15 = 30

Изменение области решений при увеличении запасов ресурса M2

Оценка ресурса M3

Концевые точки отрезка определяют интервал осуществимости для ресурса M3.

Количество сырья, соответствующего точке (0,6), равно:

3*0 + 1*6 = 6

Количество сырья, соответствующего точке (16,14), равно:

3*16 + 1*14 = 62

Таким образом, интервал осуществимости для ресурса M3 составляет

6 ≤ M3 ≤ 62

Вычислим значение целевой функции в этих точках:

F(0,6) = 1·0 + 2·6 = 12

F(16,14) = 1·16 + 2·14 = 44

Изменение области решений при увеличении запасов ресурса M3


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

Составим двойственную задачу к прямой задаче.

y1-y2+3y3≥1

-y1+2y2+y3≥2

2y1+12y2+15y3 → min

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

Отметим, что решение двойственной задачи дает оптимальную систему оценок ресурсов.

Для решения двойственной задачи используем вторую теорему двойственности.

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

1*2.57-1*7.29 = -4.71 < 2

1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0

-1*2.57 + 2*7.29 = 12 = 12

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2 > 0).

3*2.57 + 1*7.29 = 15 = 15

3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-й ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3 > 0).

Поскольку x1>0, первое ограничение в двойственной задаче будет равенством.

Поскольку x2>0, второе ограничение в двойственной задаче будет равенством.

С учетом найденных оценок, новая система примет вид:

y1 = 0

y1-y2+3y3 = 1

-y1+2y2+y3 = 2

12y2+15y3 → min

Или

-y2+3y3 = 1

2y2+y3 = 2

12y2+15y3 → min

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

Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

-y1+3y2=1

2y1+y2=2

Решив систему уравнений, получим:

y1 = 0.7143, y2 = 0.5714

Откуда найдем минимальное значение целевой функции:

F(X) = 12*0.7143 + 15*0.5714 = 17.1429

y2 = 0.71

y3 = 0.57

Z(Y) = 12*0.71+15*0.57 = 17.14

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

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

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №1 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x1 > 0)

0*0 + (-1)*0.71 + 3*0.57 = 1 = 1

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что продукт №2 экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x2 > 0)

0*0 + 2*0.71 + 1*0.57 = 2 = 2

 

Задание №2

 

Предприятие планирует выпуск двух видов продукции и , на производство которых расходуется три вида сырья , и запас каждого из них равен . На производство единицы -го вида продукции требуется -го вида сырья. Прибыль от реализации единицы -го вида продукции составляет тыс. рублей. Составить математическую модель задачи и симплекс-методом найти план производства, обеспечивающий максимальную прибыль.

 

В-нт  
2,12                      

 

 

Решение:

 

Определим максимальное значение целевой функции

F(X) = 3x1+5x2

при следующих условиях-ограничений.

7x2≤9

5x1+3x2≤7

5x1+4x2≤13

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x3.

В 2-м неравенстве смысла (≤) вводим базисную переменную x4.

В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

0x1 + 7x2 + 1x3 + 0x4 + 0x5 = 9

5x1 + 3x2 + 0x3 + 1x4 + 0x5 = 7

5x1 + 4x2 + 0x3 + 0x4 + 1x5 = 13

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
         
         
         

 

 

 

 

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

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

Решим систему уравнений относительно базисных переменных: x3, x4, x5.

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,9,7,13)

Базисное решение называется допустимым, если оно неотрицательно.

Базис В x1 x2 x3 x4 x5
x3            
x4            
x5            
F(X0)   -3 -5      

 

Итерация №0.

1. Проверяем критерий оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определяем новую базисную переменную.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

3. Определяем новую свободную переменную.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (7) и находится на пересечении ведущего столбца и ведущей строки.

Базис В x1 x2 x3 x4 x5 min
x3             1.29
x4             2.33
x5             3.25
F(X1)   -3 -5        

 

4. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы.

Вместо переменной x3 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент РЭ=7. На месте разрешающего элемента в плане получаем 1. В остальных клетках столбца x2записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.

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

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

НЭ = СЭ - (А*В)/РЭ, (2.1)

где

СТЭ - элемент старого плана,

РЭ - разрешающий элемент (7),

А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B x1 x2 x3 x4 x5
9 / 7 = 1.29 0 / 7 = 0 7 / 7 = 1 1 / 7 = 0.14 0 / 7 = 0 0 / 7 = 0

 

После преобразований получаем новую таблицу:

Базис В x1 x2 x3 x4 x5
x2 1.29     0.14    
x4 3.14     -0.43    
x5 7.86     -0.57    
F(X1) 6.43 -3   0.71    

 

Итерация №1.

1. Проверка критерия оптимальности.

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

2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Базис В x1 x2 x3 x4 x5 min
x2 1.29     0.14     -
x4 3.14     -0.43     0.63
x5 7.86     -0.57     1.57
F(X2) 6.43 -3   0.71      

 

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 2 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=5. На месте разрешающего элемента в плане получаем 1. В остальных клетках столбца x1записываем нули. Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.

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

Представим расчет каждого элемента в виде таблицы:

 

 

B x1 x2 x3 x4 x5
3.14 / 5 = 0.63 5 / 5 = 1 0 / 5 = 0 -0.43 / 5 = -0.0857 1 / 5 = 0.2 0 / 5 = 0

 

После преобразований получаем новую таблицу:

Базис В x1 x2 x3 x4 x5
x2 1.29     0.14    
x1 0.63     -0.0857 0.2  
x5 4.71     -0.14 -1  
F(X2) 8.31     0.46 0.6  

 

1. Проверка критерия оптимальности.

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

Окончательный вариант симплекс-таблицы:

Базис В x1 x2 x3 x4 x5
x2 1.29     0.14    
x1 0.63     -0.0857 0.2  
x5 4.71     -0.14 -1  
F(X3) 8.31     0.46 0.6  

 

Оптимальный план можно записать так:

x1 = 0.6286, x2 = 1.286

F(X) = 3*0.6286 + 5*1.286 = 8.3143

Графически решение можно представить следующим образом:

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 4.71.

Значение 0 в столбце x1 означает, что использование x1 - выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 0.46 в столбце x3 означает, что теневая цена (двойственная оценка) равна y1=0.46.

Значение 0.6 в столбце x4 означает, что теневая цена (двойственная оценка) равна y2=0.6.


Задание № 3

 

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

Стоимость перевозки единицы груза с -го склада -му потребителю составляет тыс.рублей: . Найти методом потенциалов план перевозки обеспечивающий минимальные затраты.

В-нт
                                       

 

Решение:

 

Математическая модель транспортной задачи:

F = ∑∑cijxij, (3.1)

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

∑xij = ai, i = 1,2,…, m, (3.2)

∑xij = bj, j = 1,2,…, n, (3.3)

xij ≥ 0

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x11 – количество груза из 1-го склада 1-му потребителю

x12 – количество груза из 1-го склада 2-му потребителю

x13 – количество груза из 1-го склада 3-му потребителю

x14 – количество груза из 1-го склада 4-му потребителю

x21 – количество груза из 2-го склада 1-му потребителю

x22 – количество груза из 2-го склада 2-му потребителю

x23 – количество груза из 2-го склада 3-му потребителю

x24 – количество груза из 2-го склада 4-му потребителю

x31 – количество груза из 3-го склада 1-му потребителю

x32 – количество груза из 3-го склада 2-му потребителю

x33 – количество груза из 3-го склада 3-му потребителю

x34 – количество груза из 3-го склада 4-му потребителю

Ограничения по запасам:

x11 + x12 + x13 + x14 ≤ 70 (для 1 склада)

x21 + x22 + x23 + x24 ≤ 50 (для 2 склада)

x31 + x32 + x33 + x34 ≤ 80 (для 3 склада)

Ограничения по потребностям:

x11 + x21 + x31 = 80 (для 1 потребителя)

x12 + x22 + x32 = 20 (для 2 потребителя)

x13 + x23 + x33 = 40 (для 3 потребителя)

x14 + x24 + x34 = 60 (для 4 потребителя)

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

9x11 + 10x12 + 1x13 + 5x14 + 2x21 + 1x22 + 8x23 + 3x24 + 4x31 + 3x32 + 3x33 + 2x34 → min

С целью составления двойственной задачи переменные xij в условии (3.2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3.3) на v1, v2, vj,.., vn.

Поскольку каждая переменная xij входит в условия (3.2, 3.3) и целевую функцию (3.1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ∑aiui + ∑bjvj

при условии

ui + vj ≤ cij, i = 1,2,..,m; j = 1,2,..,n (3.4)

В систему условий (3.4) будет mxn неравенств.

По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

ui + vj ≤ cij, если xij = 0,

ui + vj = cij, если xij ≥ 0,

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

Числа ui, vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

          Запасы
           
           
           
Потребности          

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 70 + 50 + 80 = 200

∑b = 80 + 20 + 40 + 60 = 200

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

          Запасы
           
           
           
Потребности          

 

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

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

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

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

Искомый элемент равен 1 тыс. руб.

Для этого элемента запасы равны 70 единиц, потребности 40 единиц. Поскольку минимальным является 40 единиц, то вычитаем его.

x13 = min(70,40) = 40 единиц

        70 - 40 = 30
    x    
    x    
    40 - 40 = 0    

 

Искомый элемент равен 1 тыс. руб.

Для этого элемента запасы равны 50 единиц, потребности 20 единиц. Поскольку минимальным является 20 единиц, то вычитаем его.

x22 = min(50,20) = 20 единиц.

  x      
    x   50 - 20 = 30
  x x    
  20 - 20 = 0      

 

Искомый элемент равен 2 тыс. руб.

Для этого элемента запасы равны 30 единиц, потребности 80 единиц. Поскольку минимальным является 30 единиц, то вычитаем его.

x21 = min(30,80) = 30 единиц.

  x      
    x x 30 - 30 = 0
  x x    
80 - 30 = 50        

 

 

Искомый элемент равен 2 тыс. руб.

Для этого элемента запасы равны 80 единиц, потребности 60 единиц. Поскольку минимальным является 60 единиц, то вычитаем его.

x34 = min(80,60) = 60 единиц.

  x   x  
    x x  
  x x   80 - 60 = 20
      60 - 60 = 0  

 

Искомый элемент равен 4 тыс. руб.

Для этого элемента запасы равны 20 единиц, потребности 50 единиц. Поскольку минимальным является 20 единиц, то вычитаем его.

x31 = min(20,50) = 20 единиц.

  x   x  
    x x  
  x x   20 - 20 = 0
50 - 20 = 30        

 

Искомый элемент равен 9 тыс. руб.

Для этого элемента запасы равны 30 единиц, потребности 30 единиц. Поскольку минимальным является 30, то вычитаем его.

x11 = min(30,30) = 30 единиц.

  x   x 30 - 30 = 0
    x x  
  x x    
30 - 30 = 0        

 

          Запасы
  9[30]   1[40]    
  2[30] 1[20]      
  4[20]     2[60]  
Потребности          

 

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

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 9*30 + 1*40 + 2*30 + 1*20 + 4*20 + 2*60 = 590 тыс. руб.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 9; 0 + v1 = 9; v1 = 9

u2 + v1 = 2; 9 + u2 = 2; u2 = -7

u2 + v2 = 1; -7 + v2 = 1; v2 = 8

u3 + v1 = 4; 9 + u3 = 4; u3 = -5

u3 + v4 = 2; -5 + v4 = 2; v4 = 7

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

  v1=9 v2=8 v3=1 v4=7
u1=0 9[30]   1[40]  
u2=-7 2[30] 1[20]    
u3=-5 4[20]     2[60]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;4): 0 + 7 > 5; ∆14 = 0 + 7 - 5 = 2

Выбираем максимальную оценку свободной клетки (1;4): 5

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

        Запасы  
  9[30][-]   1[40] 5[+]  
  2[30] 1[20]      
  4[20][+]     2[60][-]  
Потребности          

 

Цикл приведен в таблице (1,4 → 1,1 → 3,1 → 3,4).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 30 единиц. Прибавляем 30 единиц к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 единиц из хij, стоящих в минусовых клетках. В результате получим новый опорный план.

          Запасы
      1[40] 5[30]  
  2[30] 1[20]      
  4[50]     2[30]  
Потребности          

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

u1 + v4 = 5; 0 + v4 = 5; v4 = 5

u3 + v4 = 2; 5 + u3 = 2; u3 = -3

u3 + v1 = 4; -3 + v1 = 4; v1 = 7

u2 + v1 = 2; 7 + u2 = 2; u2 = -5

u2 + v2 = 1; -5 + v2 = 1; v2 = 6

  v1=7 v2=6 v3=1 v4=5
u1=0     1[40] 5[30]
u2=-5 2[30] 1[20]    
u3=-3 4[50]     2[30]

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Минимальные затраты составят:

F(x) = 1*40 + 5*30 + 2*30 + 1*20 + 4*50 + 2*30 = 530 тыс. руб.

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

G = 0*0 -5*50 -3*80 + 7*80 + 6*20 + 1*40 + 5*60 = 530 тыс. руб.

 

Рис. 3.1. Граф оптимального плана перевозок

 

Анализ оптимального плана.

Из 1-го склада необходимо груз направить 3-му потребителю (40 единиц), 4-му потребителю (30 единиц)

Из 2-го склада необходимо груз направить 1-му потребителю (30 единиц), 2-му потребителю (20 единиц)

Из 3-го склада необходимо груз направить 1-му потребителю (50 единиц), 4-му потребителю (30 единиц)

 

 


Задание № 4

 

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

 

В-т
                               

Решение:

Исходная матрица имеет вид:

         
         
         


Математическая модель задачи:

F = ∑∑cijxij, (4.1)

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

∑xij = n, i = 1,2,…, m, (4.2)

∑xij = m, j = 1,2,…, n, (4.3)

xij ≥ 0, целые

Запишем экономико-математическую модель для нашей задачи.

Переменные xij принимают значения 1, если i-й станок выполнит j-ю работу. Если данное условие не выполняется, то xij=0.

Ограничения по станкам:

x11 + x12 + x13 + x14 + x15 = 1

x21 + x22 + x23 + x24 + x25 = 1

x31 + x32 + x33 + x34 + x35 = 1

Ограничения по работам:

x11 + x21 + x31 = 1

x12 + x22 + x32 = 1

x13 + x23 + x33 = 1

x14 + x24 + x34 = 1

x15 + x25 + x35 = 1

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

6x11 + 8x12 + 9x13 + 5x14 + 6x15 + 9x21 + 7x22 + 8x23 + 6x24 + 5x25 + 8x31 + 7x32 + 9x33 + 8x34 + 7x35 → min

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

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

           
           
           
           
           

 

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

         
         
         
         
         
         

 

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу.

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

Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем.

Фиксируем нулевое значение в клетке (2, 5). Другие нули в строке 2 и столбце 5 вычеркиваем.

Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.

Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем.

Фиксируем нулевое значение в клетке (5, 3). Другие нули в строке 5 и столбце 3 вычеркиваем.

В итоге получаем следующую матрицу:

      [0]  
        [0]
  [0]     [-0-]
[0] [-0-] [-0-] [-0-] [-0-]
[-0-] [-0-] [0] [-0-] [-0-]

 

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

         
         
         
         
         

 

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

 

      [0]  
        [0]
  [0]     [-0-]
[0] [-0-] [-0-] [-0-] [-0-]
[-0-] [-0-] [0] [-0-] [-0-]

 

Cmin = 5 + 5 + 7 = 17

Таким образом

1 станок должен выполнить 4-ю работу

2 станок должен выполнить 5-ю работу

3 станок должен выполнить 2-ю работу


Задание № 5

Банк имеет операционистов для обслуживания вкладчиков. Поток клиентов поступает в банк с интенсивностью . Средняя продолжительность обслуживания операционистом одного вкладчика

Определить:

1) вероятность простоя операционистов;

2) вероятность отказа клиенту в обслуживании;

3) вероятность обслуживания клиента;

4) среднее время ожидания клиента в очереди;

5) коэффициент занятости операционистов.

 

<== предыдущая лекция | следующая лекция ==>
Мотивация (стимулирование). | НАУЧНО-ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АНАЛИЗА СЕБЕСТОИМОСТИ ПРОДУКЦИИ


Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных