Главная База знаний "Allbest" Экономико-математическое моделирование Линейное программирование

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

Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 13.06.2012
Размер файла 467,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Государственное образовательное учреждение

высшего профессионального образования

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет экономики и управления

Кафедра математических методов и моделей в экономике

ОТЧЕТ

по расчетно-графической работе

по курсу «Математические методы и модели исследования операций»

Задачи линейного программирования

Руководитель
___________ Яркова О.Н.
«___»____________2011 г.
Исполнитель
студентка гр. 10ММЭ
_______Абдрахимова Е.Г.
Оренбург 2011

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

"Оренбургский государственный университет"

Кафедра математических методов и моделей в экономике

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

по дисциплине «Математические методы и модели исследования операций»

на тему «Линейное программирование»

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

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

Содержание

  • 1. Решение задачи ЛП
  • 1.1 Гeометрическая интерпретация двумерной задачи ЛП и ее решение
  • 1.2 Решение задачи ЛП симплекс-методом
  • 2. Двойственная задача
  • 3. Транспортная задача
  • 3.1 Транспортная задача (открытого типа)
  • 3.2 Транспортная задача (закрытого типа)
  • 4. Задача о назначениях.
  • 5. Задача о коммивояжере
  • 6.Симплекс метод
  • Введение
  • В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решений, в том числе и в финансовой математике. Для решения задач линейного программирования разработано сложное программное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. Владение аппаратом линейного программирования необходимо каждому специалисту в области прикладной математики.
  • Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
  • · рационального использования сырья и материалов;
  • · задачи оптимального раскроя;
  • · оптимизации производственной программы предприятий;
  • · оптимального размещения и концентрации производства;
  • · составления оптимального плана перевозок, работы транспорта;
  • · управления производственными запасами;
  • · и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

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

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

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, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.

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

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

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

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 (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

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 и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

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

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

1) Вместо базисной переменной xk записываем xl; вместо небазисной переменной xlзаписываем xk.

2) ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l

3) все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l

4) все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l

5) оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,lx ak,j/ ak,l

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

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

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

1.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.

1.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».

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

Исходные данные (Рисунок 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 , Р4 являются убыточными; их производство нерентабельно.

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

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

2.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 является дефицитным красителем сделаем вывод, что , а , тогда

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

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

3.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

3.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 метод обеспечивает его доступность использования при необходимости.

Размещено на Allbest.ru


Подобные документы

  • Решение задачи линейного программирования симплекс-методом

    Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

    реферат [193,4 K], добавлен 28.12.2008

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

    Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.

    контрольная работа [367,5 K], добавлен 11.05.2014

  • Математические методы принятия управленческих решений

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

    контрольная работа [1,4 M], добавлен 31.03.2012

  • Применение графического метода и симплекс-метода для решения задач линейного программирования

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

    контрольная работа [398,2 K], добавлен 15.08.2012

  • Решение задач линейного программирования

    Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.

    курсовая работа [106,0 K], добавлен 05.10.2014

  • Линейное программирование. Теория массового обслуживания

    Задача оптимального планирования производства. Составление двойственной задачи, её решение по теоремам двойственности. Предельные вероятности состояний. Среднее время ожидания заявки в очереди. Принятие управленческих решений на основе теории игр.

    контрольная работа [218,5 K], добавлен 15.05.2015

  • Оптимизация плана производства

    Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.

    курсовая работа [458,6 K], добавлен 10.12.2013

  • Линейное программирование, теория игр

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

    контрольная работа [232,3 K], добавлен 02.01.2012

  • Оптимизационные задачи в экономике и алгоритмы решения некоторых задач линейного программирования

    Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.

    учебное пособие [126,0 K], добавлен 07.10.2014

  • Линейное программирование и методы оптимизации

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

    задача [579,8 K], добавлен 11.07.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены