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

0

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

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

Задание 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

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

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

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

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

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

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

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

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

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

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

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

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


Введение.

 

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

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

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

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

 

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

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

F=a01x1+a02x2+...a0nxn +b0 → 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

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

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

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

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

F=a01x1+a02x2+...a0nxn +b0 → max

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,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. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l- он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Затем снова пересчитываем симплекс-таблицу согласно правилам.
  3. Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
  4. Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

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

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

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

      bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0

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

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

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

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

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

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

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

                

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


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

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

 

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

 

  (1)

 

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

 

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

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

 

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

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

 

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

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

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


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

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

 

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

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

 

  (2)

 

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

 

 

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

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

x3, x4,

Полагая, что свободные переменные равны 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.

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

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

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

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

Следовательно, 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.

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

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

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

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

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

 

Базис

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

 

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

x2 = 36/13

x1 = 11/13

F(X) = 1•36/13 + 1•11/13 = 47/13.

 

Используя программу «Симплекс-метод», получим аналогичный результат (Рисунок 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) = 49x1 + 33x2 + 76x3 + 109x4

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

 

 

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

 

3x1 + 1x2 + 2x3 + 10x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 25000

4x1 + 3x2 + 8x3 + 6x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 120000

2x1 + 3x2 + 7x3 + 9x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 155000

8x1 + 5x2 + 12x3 + 11x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 250000

2x1 + 3x2 + 4x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 = 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

 

Решим систему уравнений относительно базисных переменных: (x5, x6, x7, x8, x9), полагая, что свободные переменные равны 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.

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: следовательно, 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.

 

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

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

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

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

 

Базис

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

 

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

x3 = 12500

x6 = 20000

x7 = 67500

x8 = 100000

x9 = 50000

 

F(X) = 76•12500 = 950000

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

 

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

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

 

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

 

 

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

 

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

 

Обозначим :

y1 – теневая цена красителя А1;

y2 – теневая цена красителя А2;

y3 – теневая цена красителя А3;

y4 – теневая цена красителя А4;

y5 – теневая цена красителя А5;

 

 25000y1 + 120000y2 + 155000y3 + 250000y4 + 100000y5 → min

 

 

 

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

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

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

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

A = (A3, A6, A7, A8, A9, ) =

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)

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

y1 = 38

y2 = 0

y3 = 0

y4 = 0

y5 = 0

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

 

Таким образом дефицитным красителем является краситель А1 , а к не дефицитным красителям относятся красители А2 , А3 , А4 ,  А5 . Недефицитные красители недоиспользуются  на :

  • краситель А2 на 20 000 грамм;
  • краситель А3 на 67 500 грамм;
  • краситель А4 на 100 000 грамм;
  • краситель А5 на 50 000 грамм;

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

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

 

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

 

   

 

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

 

 

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

 

 

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

 

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

 

F*= 25000y1 + 120000y2 + 155000y3 + 250000y4 + 100000y5 → min

 

 

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

 

F*= -25000y1 -120000y2 - 155000y3 - 250000y4 - 100000y5 → 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

 

x2 = 18.17

x8 = 69.33

x6 = 23.67

x7 = 21.5

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

 

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

 

 

 

 

 

 

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

 

 

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

 

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

 

 

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

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

 

,

 

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

 

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

 

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. Улучшение опорного плана.

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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]

 

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

Выбираем максимальную оценку свободной клетки (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

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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]

 

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

Выбираем максимальную оценку свободной клетки (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

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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]

 

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

 

Выбираем максимальную оценку свободной клетки (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

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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]

 

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

 

Выбираем максимальную оценку свободной клетки (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

 

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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

 

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

 

Выбираем максимальную оценку свободной клетки (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

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 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

 

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

 

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

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

 

Заключение.

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

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

 

Скачать: raspechatat.doc

Категория: Контрольные работы / Экономическая информатика

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