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

Линейное программирование

Задание 1.

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

.

1. Решить задачу ЛП геометрически. 
2. Решить эту задачу с помощью симплекс-метода.

Задание 2.

На фабрике с помощью 5 видов красителей () создается 4 разновидности рисунков для тканей (). При известной отпускной стоимости 1м ткани каждого рисунка (руб.), известном расходе каждого красителя на окраску  ткани (г) и известном запасе красителя (кг):

1. Определить план выпуска ткани каждого рисунка, обеспечивающий максимальный доход от реализации тканей;
2. Составить двойственную задачу и найти ее решение;
3. Определить теневые цены на каждый краситель; указать дефицитные и недефицитные красители;
4. Указать, на сколько недоиспользуются недефицитные красители;
5. Показать доход и план выпуска тканей при увеличении запасов дефицитных красителей на I ед.;
6. Показать допустимые пределы изменения запасов красителей;
7. Показать допустимые пределы изменения отпускной стоимости на ткань каждого рисунка;
8. Оценить целесообразность введения в план производства выпуск ткани с разновидностью рисунка (), если нормы затрат красителей на 1 ед. ткани соответственно равны 6,2,1,4,4 г и доход, ожидаемый от реализации новой ткани, равен 5000 руб.;
9. Показать, допустимо ли увеличение всех дефицитных красителей одновременно на 1 кг каждого.

 

Задание 3.

Для транспортной задачи составить математиче­скую модель. Методом потенциалов найти оптимальные пла­ны. Опорный план найти методом северо-западного угла.

Задача 1. (Транспортная задача закрытого типа)

Три предприятия:  данного экономического района могут про­изводить некоторую однородную продукцию в количествах, указанных в столбце «производство». Эта продукция должна быть поставлена четырем потребителям:  в количествах, указанных в строке «потребности». Затраты, связанные с про­изводством и доставкой единицы продукции, заданы на пересечении соот­ветствующих поставщиков и потребителей в столбцах той же таблицы. Со­ставить такой план прикрепления потребителей к поставщикам, при котором общие затраты являются минимальными.

Задача 2. (Транспортная задача открытого типа).

На четырех хлебокомбинатах (поставщик):  ежедневно производится мука в количествах, указанных в столбце «производство». Эта мука потребляется тремя хлебзаводами (потребитель): в количествах, указанных в строке «потребности» - потребности, этой же таблицы. Тарифы перевозок 1т. муки с хлебокомбинатов к каждому из хлебозаводов заданы на пересечении соответствующих поставщиков и по­требителей в столбцах этой же таблицы. Составьте такой план доставки му­ки, при котором стоимость перевозок является минимальной.

Задание 4.

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

 

Задание 5.

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

 

Задание 6.

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

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

Задание на РГЗ. 2

Введение. 5

1. Теоретическая часть. 6

1.1  Алгоритм симплекс-метода. 6

2. Решение задачи ЛП. 10

2.1 Гeометрическая интерпретация двумерной задачи ЛП и ее решение. 10

2.2 Решение задачи ЛП симплекс-методом. 12

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

3.1 Составление и решение двойственной задачи. 19

4. Транспортная задача. 24

4.1 Транспортная задача (открытого типа) 24

4.2 Математическая модель транспортной задачи(закрытого типа): 25

5.Задача о назначениях………………………………………………………….33

6. Задача о коммивояжере……………………………………………………….39

7.Приложение А. Симплекс метод……………………...………………………43

Заключение. 62

Введение.

 

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

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

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

 

Целью данного РГЗ является выполнение расчетно-графической работы, закрепление знаний и навыков, необходимых для математического моделирования социально-экономических процессов. А также, приобретение навыков работы с программными пакетами «Линейное программирование» и «Дискретное программирование».

 

 

 

 

 

 

 

 

 

 

 

1.     Теоретическая часть.

 

Табличный симплекс-метод.

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

F=a₀₁x₁+a₀₂x₂+...a_0nx_n +b₀ → max

Исходная таблица для задачи имеет следующий вид:

	x1	x2	...	xn-1	xn	b
F	- a0,1	-a0,2	...	-a0,n-1	- a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

x₁, x₂, x_n - исходные переменные, x_n+1, x_n+2, x_n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

1.1  Алгоритм симплекс-метода.

  Подготовительный этап

 Приводим задачу ЛП  к каноническому виду

F=a₀₁x₁+a₀₂x₂+...a_0nx_n +b₀ → max

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a_0,n=-a_0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.  

 Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче :

	x1	x2	...	xn-1	xn	b
F	- a0,1	-a0,2	...	-a0,n-1	- a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	...	a2,n-1	a2,n	b2
...	...	...	...	...	...	...
xn+m	am,1	am,2	...	am,n-1	am,n	bm

 

 Шаг 1. Проверка на допустимость.   

Проверяем на положительность элементы столбца b (свободные члены):

1. Если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2.
2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l- он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Затем снова пересчитываем симплекс-таблицу согласно правилам.
3. Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
4. Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

 Шаг 2. Проверка на оптимальность.

 На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность:

1. Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b₀ - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.
2. Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b₀) a_0,l=min{a_0,i }. Первый столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.

      b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу по формулам:

1. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
2. Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
3. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение. 

Правила преобразований симплексной таблицы.

 При составлении новой симплекс-таблицы в ней происходят следующие изменения: 

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_lзаписываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,lx a_k,j/ a_k,l

Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.

                

Преобразуемый элемент a_i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

         2. Решение задачи ЛП.

2.1 Гeометрическая интерпретация двумерной задачи ЛП и ее решение.

 

Рассмотрим двумерную задачу:

 

  (1)

 

Необходимо найти максимальное значение целевой функции F = x₁+x₂ → max, при системе ограничений (1).Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом) (Рисунок 1).

 

Рисунок 1-Границы области допустимых решений.

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

 

Рисунок 2- границы области решений.

Рассмотрим целевую функцию задачи F = x₁+x₂ → max. 
Построим прямую, отвечающую значению функции F = 0: F = x₁+x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (Рисунок 3).

 

Рисунок 3- поиск максимального решения.

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

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

Решив систему уравнений, получим: x₁ = 1.0769, x₂ = 3.4615.
Откуда найдем максимальное значение целевой функции:
F(X) = 1*1.0769 + 1*3.4615 = 4.54.

2.2 Решение задачи ЛП симплекс-методом

 

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

Определим максимальное значение целевой функции F(X) = x₁ + x₂ при следующих условиях-ограничений:

 

  (2)

 

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

 

 

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

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

x₃, x₄,

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

X1 = (0,0,8,3)

 

Базис	B	x1	x2	x3	x4
x3	8	1	2	1	0
x4	3	6	-1	0	1
F(X0)	0	-1	-1	0	0

 

Переходим к основному алгоритму симплекс-метода.

 

Итерация №0.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

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

 

Базис	B	x1	x2	x3	x4	min
x3	8	1	2	1	0	4
x4	3	6	-1	0	1	-
F(X1)	0	-1	-1	0	0	0

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4
x2	4	1/2	1	1/2	0
x4	7	61/2	0	1/2	1
F(Х1)	4	-1/2	0	1/2	0

 

 

Итерация №1.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее, следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (6¹/₂) и находится на пересечении ведущего столбца и ведущей строки.

 

Базис	B	x1	x2	x3	x4	min
x2	4	1/2	1	1/2	0	8
x4	7	61/2	0	1/2	1	11/13
F(X2)	4	-1/2	0	1/2	0	0

 

 

 

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4
x2	36/13	0	1	6/13	-1/13
x1	11/13	1	0	1/13	2/13
F(X2)	47/13	0	0	7/13	1/13

 

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

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

 

Базис	B	x1	x2	x3	x4
x2	36/13	0	1	6/13	-1/13
x1	11/13	1	0	1/13	2/13
F(X3)	47/13	0	0	7/13	1/13

 

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

x₂ = 3⁶/₁₃

x₁ = 1¹/₁₃

F(X) = 1•3⁶/₁₃ + 1•1¹/₁₃ = 4⁷/₁₃.

 

Используя программу «Симплекс-метод», получим аналогичный результат (Рисунок 4).

 

 

Рисунок 4 - результат вычисления полученный путём проверки в программе «SIMPLEX».

 

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

Исходные данные (Рисунок 5):

Номер Варианта	Вид Красителей	Разновидность рисунка. Расход красителей на окраску 1 м ткани (грамм)				Запасы красителей (грамм)
		Р1	Р2	Р3	Р4
1	А1	3	1	2	10	25 000
	А2	4	3	8	6	120 000
	А3	2	3	7	9	155 000
	А4	8	5	12	11	250 000
	А5	2	3	4	1	100 000
	Стоимость одного метра ткани (руб.)	49	33	76	109

 

Рисунок 5 – таблица исходных данных.

 

1. Для определение плана выпуска ткани каждого вида рисунка, обеспечивающего максимальный доход от реализации тканей необхадимо составить экономико-математическую модель задачи. Для этого введём обозначения следующего вида:

 – план выпуска ткани рисунка вида  ;

 – план выпуска ткани рисунка вида  ;

 – план выпуска ткани рисунка вида  ;

 – план выпуска ткани рисунка вида  ;

 

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

 

 F(X) = 49x₁ + 33x₂ + 76x₃ + 109x₄

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

 

 

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

 

3x₁ + 1x₂ + 2x₃ + 10x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 25000

4x₁ + 3x₂ + 8x₃ + 6x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ = 120000

2x₁ + 3x₂ + 7x₃ + 9x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 155000

8x₁ + 5x₂ + 12x₃ + 11x₄ + 0x₅ + 0x₆ + 0x₇ + 1x₈ + 0x₉ = 250000

2x₁ + 3x₂ + 4x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ = 100000

 

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

 

3	1	2	10	1	0	0	0	0
4	3	8	6	0	1	0	0	0
2	3	7	9	0	0	1	0	0
8	5	12	11	0	0	0	1	0
2	3	4	1	0	0	0	0	1

 

Решим систему уравнений относительно базисных переменных: (x₅, x₆, x₇, x₈, x₉), полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,25000,120000,155000,250000,100000)

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x5	25000	3	1	2	10	1	0	0	0	0
x6	120000	4	3	8	6	0	1	0	0	0
x7	155000	2	3	7	9	0	0	1	0	0
x8	250000	8	5	12	11	0	0	0	1	0
x9	100000	2	3	4	1	0	0	0	0	1
F(X0)	0	-49	-33	-76	-109	0	0	0	0	0

 

Переходим к основному алгоритму симплекс-метода.

 

Итерация №0.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: следовательно, 1-ая строка является ведущей.

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x5	25000	3	1	2	10	1	0	0	0	0	2500
x6	120000	4	3	8	6	0	1	0	0	0	20000
x7	155000	2	3	7	9	0	0	1	0	0	172222/9
x8	250000	8	5	12	11	0	0	0	1	0	227273/11
x9	100000	2	3	4	1	0	0	0	0	1	100000
F(X1)	0	-49	-33	-76	-109	0	0	0	0	0	0

 

 

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x4	2500	3/10	1/10	1/5	1	1/10	0	0	0	0
x6	105000	21/5	22/5	64/5	0	-3/5	1	0	0	0
x7	132500	-7/10	21/10	51/5	0	-9/10	0	1	0	0
x8	222500	47/10	39/10	94/5	0	-11/10	0	0	1	0
x9	97500	17/10	29/10	34/5	0	-1/10	0	0	0	1
F(X1)	272500	-163/10	-221/10	-541/5	0	109/10	0	0	0	0

 

Итерация №1.

 

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее: следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (¹/₅) и находится на пересечении ведущего столбца и ведущей строки.

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x4	2500	3/10	1/10	1/5	1	1/10	0	0	0	0	12500
x6	105000	21/5	22/5	64/5	0	-3/5	1	0	0	0	154413/17
x7	132500	-7/10	21/10	51/5	0	-9/10	0	1	0	0	2548010/13
x8	222500	47/10	39/10	94/5	0	-11/10	0	0	1	0	227044/49
x9	97500	17/10	29/10	34/5	0	-1/10	0	0	0	1	2565717/19
F(X2)	272500	-163/10	-221/10	-541/5	0	109/10	0	0	0	0	0

 

 

Получаем новую симплекс-таблицу:

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x3	12500	11/2	1/2	1	5	1/2	0	0	0	0
x6	20000	-8	-1	0	-34	-4	1	0	0	0
x7	67500	-81/2	-1/2	0	-26	-31/2	0	1	0	0
x8	100000	-10	-1	0	-49	-6	0	0	1	0
x9	50000	-4	1	0	-19	-2	0	0	0	1
F(X2)	950000	65	5	0	271	38	0	0	0	0

 

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

 

 

 

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

 

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x3	12500	11/2	1/2	1	5	1/2	0	0	0	0
x6	20000	-8	-1	0	-34	-4	1	0	0	0
x7	67500	-81/2	-1/2	0	-26	-31/2	0	1	0	0
x8	100000	-10	-1	0	-49	-6	0	0	1	0
x9	50000	-4	1	0	-19	-2	0	0	0	1
F(X3)	950000	65	5	0	271	38	0	0	0	0

 

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

x₃ = 12500

x₆ = 20000

x₇ = 67500

x₈ = 100000

x₉ = 50000

 

F(X) = 76•12500 = 950000

X_оптим = ( 0; 0; 12500; 0; 0; 120000; 155000; 250000; 100000).

 

Для получения максимальной прибыли 950 000 руб. необхадимо выпустить тканей рисунков вида Р₃  в объеме 12500.

Ткани рисунков вида Р₁ , Р_{2  ,} Р₄  являются убыточными; их производство нерентабельно.

 

Проверка при помощи программного продукта (Рисунок 5):

 

 

Рисунок 5 – проверка реализованная программным методом.

 

3.1 Составление и решение двойственной задачи.

 

Обозначим :

y₁ – теневая цена красителя А₁;

y₂ – теневая цена красителя А₂;

y₃ – теневая цена красителя А₃;

y₄ – теневая цена красителя А₄;

y₅ – теневая цена красителя А₅;

 

 25000y₁ + 120000y₂ + 155000y₃ + 250000y₄ + 100000y₅ → min

 

 

 

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

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

Из теоремы двойственности следует, что Y = C*A^-1.

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

A = (A₃, A₆, A₇, A₈, A₉, ) =

2	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

 

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

А^-1 =

1/2	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A^-1 =

(76, 0, 0, 0, 0) x

1/2	0	0	0	0
0	1	0	0	0
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

 

 = (38;0;0;0;0)

Оптимальный план двойственной задачи равен:

y₁ = 38

y₂ = 0

y₃ = 0

y₄ = 0

y₅ = 0

F_max = 25000*38+120000*0+155000*0+250000*0+100000*0 = 950000.

 

Таким образом дефицитным красителем является краситель А₁ , а к не дефицитным красителям относятся красители А₂ , А₃ , А₄ ,  А_{5 .} Недефицитные красители недоиспользуются  на :

• краситель А₂ на 20 000 грамм;
• краситель А₃ на 67 500 грамм;
• краситель А₄ на 100 000 грамм;
• краситель А₅ на 50 000 грамм;

При увеличении запасов красителя краситель А₁ на 1 ед. (25001 грамм) можно получить увеличение прибыли на 38 руб., что составит 950038 руб. При этом план выпуска ткани рисунка Р₃ надо увеличить на 0,5 м, т.е выпустить ткани  12500,5 . В этом случае недефицитные красители будут недоиспользоваться :

1. Краситель Р₂ – 4 ; его недоиспользование составит 20 004 грамм;
2. Краситель Р₃ – 3,5; его недоиспользование составит 67 503,5 грамм;
3. Краситель Р₄ – 6 ; его недоиспользование составит 100 006 грамм;
4. Краситель Р₅ – 2 ; его недоиспользование составит 50 002 грамм;

 

Для вычисления допустимых пределов изменения запасов красителей составим матрицу  и вектор-столбец :

 

 

Найдём матрицу , обратную исходной матрице .

 

 

Найдём допустимые пределы изменения запасов красителей из условий:

 

 

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

 

Запишем двойственную задачу:

 

F*= 25000y₁ + 120000y₂ + 155000y₃ + 250000y₄ + 100000y₅ → min

 

 

Приведём задачу к каноническому виду и преобразуем целевую функцию для решения задачи на

 

F*= -25000y₁ -120000y₂ - 155000y₃ - 250000y₄ - 100000y₅ → max

 

 

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

 

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9
x2	18.17	1.67	1	1.5	1.83	0.83	0	0	0	-0.17
x8	69.33	11.33	0	5	2.67	2.67	0	0	1	-1.33
x6	23.67	3.67	0	4	-0.67	1.33	1	0	0	-0.67
x7	21.5	4	0	1.5	0.5	-0.5	0	1	0	-0.5
F(X9)	-227083.33	4166.67	0	136250	227083.33	89583.33	0	0	0	2083.33

 

x₂ = 18.17

x₈ = 69.33

x₆ = 23.67

x₇ = 21.5

F(X) = -12500*18.17 = -227083.33

 

Составим матрицу  и вектор столбец

 

 

 

 

 

 

Найдём матрицу

 

 

Допустимые пределы изменения отпускной стоимости тканей каждого рисунка:

 

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

 

 

т.к. - отрицательно, введение в план производства ткани с новым рисунком целесообразно.

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

 

,

 

так же исходя из того что краситель А₁ является дефицитным красителем сделаем вывод, что , а , тогда

 

Это говорит о том что увеличение дефицитных красителей не приводит к изменению плана производства тканей.

 

4. Транспортная задача

4.1 Транспортная задача (открытого типа)

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

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

  

  

      

Где

 

Исходные данные:

 

	1		2		3		Запасы
1		1		9		4	100
2		4		3		3	80
3		2		1		2	50
4		6		2		9	50
Потребности	90		100		80

 

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

Так как ,  то введем 4-го фиктивного потребителя, спрос  которого

	1		2		3		4		Запасы
1		1		9		4		0	100
2		4		3		3		0	80
3		2		1		2		0	50
4		6		2		9		0	50
Потребности	90		100		80		10

 

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

 

,    (1)

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

 

 

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

 

	1	2	3	4	Запасы
1	1	9	4	0	100
2	4	3	3	0	80
3	2	1	2	0	50
4	6	2	9	0	50
Потребности	90	100	80	10

 

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

∑a = 100 + 80 + 50 + 50 = 280

∑b = 90 + 100 + 80 + 10 = 280

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

 

	1	2	3	4	Запасы
1	1	9	4	0	10
2	4	3	3	0	80
3	2	1	2	0	50
4	6	2	9	0	50
Потребности	90	100	80	10

 

Этап I. Поиск первого опорного плана.

 

Построим первый опорный план транспортной задачи.

 

Этап II. Улучшение опорного плана.

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

	v1=1	v2=9	v3=10	v4=1
u1=0	[90]	9[10]	4	0
u2=-6	4	3[80]	3	0
u3=-8	2	1[10]	2[40]	0
U4=-1	6	2	9[40]	0[10]

 

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

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

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

 

	1	2	3		Запасы
1	1[90]	9[10][-]	4[+]	0	100
2	4	3[80]	3	0	80
3	2	1[10][+]	2[40][-]	0	50
4	6	2	9[40]	0[10]	50
Потребности	90	100	80	10

 

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[80]	3	0	80
3	2	1[20]	2[30]	0	50
4	6	2	9[40]	0[10]	50
Потребности	90	100	80	10

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

	v1=1	v2=3	v3=4	v4=-5
u1=0	1[90]	9	4[10]	0
u2=0	4	3[80]	3	0
u3=-2	2	1[20]	2[30]	0
u4=5	6	2	9[40]	0[10]

 

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

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[80]	3	0	80
3	2	1[20][-]	2[30][+]	0	50
4	6	2[+]	9[40][-]	0[10]	50
Потребности	90	100	80	10

 

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

 

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[80]	3	0	80
3	2	1	2[50]	0	50
4	6	2[20]	9[20]	0[10]	50
Потребности	90	100	80	10

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

	v1=1	v2=-3	v3=4	v4=-5
u1=0	1[90]	9	4[10]	0
u2=6	4	3[80]	3	0
u3=-2	2	1	2[50]	0
u4=5	6	2[20]	9[20]	0[10]

 

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

 

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[80][-]	3[+]	0	80
3	2	1	2[50]	0	50
4	6	2[20][+]	9[20][-]	0[10]	50
Потребности	90	100	80	10

 

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

 

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

	1	2	3	4	Запасы
1	1[90]	9	4[10]	0	100
2	4	3[60]	3[20]	0	80
3	2	1	2[50]	0	50
4	6	2[40]	9	0[10]	50
Потребности	90	100	80	10

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=4	v3=4	v4=2
u1=0	1[90]	9	4[10]	0
u2=-1	4	3[60]	3[20]	0
u3=-2	2	1	2[50]	0
u4=-2	6	2[40]	9	0[10]

 

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

 

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[10][-]	0[+]	100
2	4	3[60][-]	3[20][+]	0	80
3	2	1	2[50]	0	50
4	6	2[40][+]	9	0[10][-]	50
Потребности	90	100	80	10

 

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[0]	0[10]	100
2	4	3[50]	3[30]	0	80
3	2	1	2[50]	0	50
4	6	2[50]	9	0	50
Потребности	90	100	80	10

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=4	v3=4	v4=0
u1=0	1[90]	9	4[0]	0[10]
u2=-1	4	3[50]	3[30]	0
u3=-2	2	1	2[50]	0
u4=-2	6	2[50]	9	0

 

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

 

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

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

 

	1	2	3	4	Запасы
1	1[90]	9	4[0]	0[10]	100
2	4	3[50][-]	3[30][+]	0	80
3	2	1[+]	2[50][-]	0	50
4	6	2[0]	9	0	50
Потребности	90	100	80	10

 

Цикл приведен в таблице (3,2; 3,3; 2,3; 2,2; ).

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

 

	1	2	3	4	Запаы
1	1[90]	9	4[0]	0[10]	100
2	4	3[0]	3[80]	0	80
3	2	1[50]	2	0	50
4	6	2[50]	9	0	50
Потребности	90	100	80	10

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=4	v3=4	v4=0
u1=0	1[90]	9	4[0]	0[10]
u2=-1	4	3[0]	3[80]	0
u3=-3	2	1[50]	2	0
u4=-2	6	2[50]	9	0

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

 

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

F(x) = 1*90 + 0*10 + 3*80 + 1*50 + 2*50  = 480

 

Заключение.

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

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

 

Скачать: raspechatat.doc