Оптимальная производственная программа: плавильное производство

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

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

Московский Государственный Институт Стали и Сплавов

(Технологический Университет)

Кафедра Экономики и менеджмента

Учебный курс: «Экономико-математические методы и модели:

финансовая математика»

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

«Оптимальная производственная программа: плавильное производство»

Москва

2006

Содержание

Введение. Цель курсовой работы

1. Формулировка задания

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

3. Формы записи задач линейного программирования

4. Способы перехода от одной формы записи задач линейного программирования к другой

5. Составление двойственных задач линейного программирования

6. Решение задач симплекс-методом

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

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

9. Решение задачи линейного программирования на компьютере в программе Microsoft Excel

Заключение

Информационные источники

Введение. Цель курсовой работы

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

1. Формулировка задания

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

На трех печах производятся три различные марки металлов.

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

Номер печи Марка металла	Продолжительность плавки, час-мин; Затраты, тыс.руб./т.	Цена, тыс.руб./т	Объем заказов, т.
	П-1	П-2	П-3
М-1	4-00; 92	4-30; 90	5-00; 87	95	600
М-2	3-12; 75	3-30; 70	4-00; 65	80	500
М-3	3-00; 57	3-12; 55	3-30; 53	60	450
Тоннаж, т.	20	30	40
Фонд времени, час	210	200	180

Составить:

1. Задачу линейного программирования на минимум суммарных затрат,

2. Задачу линейного программирования на максимум прибыли,

3. Двойственные задачи к первой и второй задаче линейного программирования.

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

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

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

Ограничения:

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

- коэффициенты целевой функции,

- коэффициенты левых частей ограничений, ,

- коэффициенты правых частей ограничений.

3. Формы записи задач линейного программирования

Общая форма записи (описание ситуации):

Задача линейного программирования в общей форме записи характеризуется следующими свойствами:

- Целевая функция максимизируется или минимизируется,

- Имеет место часть неравенства типа:

- «больше или равно»,

- «меньше или равно»,

- «равно»,

- На все переменные наложено условие неотрицательности.

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

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

Ограничения:

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

- коэффициенты целевой функции,

- коэффициенты левых частей ограничений, ,

- коэффициенты правых частей ограничений.

Для составления и анализа двойственной задачи линейного программирования задача записывается в стандартной форме

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

Ограничения:

4. Способы перехода от одной формы записи задач линейного программирования к другой

a. Переход от минимизации к максимизации целевой функции осуществляется умножением на (-1). Аналогично осуществляется переход от неравенства типа ? к ? и наоборот.

b. Переход от неравенств к равенствам осуществляется путем введения дополнительной переменной. Пусть имеется неравенство: , введем . Тогда неравенство преобразуется в равенство: . Отметим, что дополнительная переменная .

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

d. Введение условной неотрицательности на переменные осуществляется путем введение дополнительной переменной. Пусть на Х_k не наложено условие неотрицательности, то есть . Введем переменные и так, что . При этом и . Далее из рассмотрения исключается.

5. Составление двойственных задач линейного программирования

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

- Число ограничений двойственной задачи равно числу переменных прямой задачи.

- Число переменных двойственной задачи равно числу ограничений прямой задачи.

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

- Если ограничения прямой задачи имеют знак ?, то ограничения двойственной задачи имеют знак ?.

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

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

Пусть задача задана в стандартной форме:

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

- коэффициенты целевой функции,

- коэффициенты левых частей ограничений, ,

- коэффициенты правых частей ограничений.

Введем переменные:,

Двойственная задача будет иметь вид:

b. Существуют три основные теоремы двойственности

i. «Критерий эффективности» (1-я теорема)

Прямая задача:

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

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

Необходимое и достаточное условия отрицательности решения прямой и двойственной задач:

- Достаточное условие:

Если: - оптимальное решение прямой задачи,

- оптимальное решение двойственной задачи,

то:

- Необходимое условие:

Если: ,

то: - оптимальное решение прямой задачи,

- оптимальное решение двойственной задачи.

ii. «Теория равновесия» (2-я теорема)

Прямая и двойственная задачи заданы в стандартной форме записи. На оптимальные решения прямой и двойственной задачи выполняются следующие соотношения:

Следствия:

- Если i-ое ограничение прямой задачи выполняется как строгое неравенство , где Х* - оптимальное решение прямой задачи, то значение соответствующей двойственной переменной равно нулю .

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

- Если на оптимальное решение двойственной задачи k-ое ограничение выполняется как строгое неравенство, то соответствующее оптимальное решение в прямой задаче равна нулю: , .

- Если на оптимальном решении прямой задачи k-ая переменная больше нуля, то соответствующее ей ограничение двойственной задачи выполняется как строгое неравенство: ,

iii. «Теорема об оценках» (3-я теорема)

, где

.

6. Решение задач симплекс-методом

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

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

а) , б) в)

В случае (а) вводятся дополнительные переменные ui:

;

В случае (б) вводятся фиктивные переменные wi:

;

В случае (в) одновременно вводятся дополнительные переменные ui и фиктивные переменные wi:

.

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

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

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

Прямая задача

x_ik - объем производства i-ой марки металла на k-ой печи.

92x₁₁ + 90x₁₂ + 87x₁₃ + 75x₂₁ + 70x₂₂ + 65x₂₃ + 57x₃₁ + 55x₃₂ + 53x₃₃ min

Ограничения по объему заказов:

x₁₁ + x₁₂ + x₁₃ ? 600

x₂₁ + x₂₂ + x₂₃ ? 500

x₃₁ + x₃₂ + x₃₃ ? 450

Ограничения по фонду времени:

(4x₁₁ + 4,5x₁₂ + 5x₁₃) / 20 ? 210

(3,2x₂₁ + 3,5x₂₂ + 4x₂₃) / 30 ? 200

(3x₃₁ + 3,2x₃₂ + 3,5x₃₃) / 40 ? 180

Преобразуем ограничения по фонду времени:

0,2x₁₁ + 0,225x₁₂ + 0,25x₁₃ ? 210

0,1067x₂₁ + 0,1167x₂₂ + 0,13x₂₃ ? 200

0,075x₃₁ + 0,08x₃₂ + 0,0875x₃₃ ? 180

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

600y₁ + 500y₂ + 4500y₃ - 210y₄ - 200y₅ - 180y₆ max

y₁ - 0,24y₄ ? 92,

y₁ - 0,22y₅ ? 90,

y₁ - 0,25y₆ ? 87,

y₂ - 0,11y₄ ? 75,

y₂ - 0,12y₅ ? 70,

y₂ - 0,13y₆ ? 65,

y₃ - 0,08y₄ ? 57,

y₃ - 0,08y₅ ? 55,

y₃ - 0,09y₆ ? 53,

Решение прямой и двойственной задачи на минимум суммарных затрат

Прямая задача:

x₁₁ = 0,00

x₁₂ = 297,50

x₁₃ = 302500

x₂₁ = 0,00

x₂₂ = 0,00

x₂₃ = 500,00

x₃₁ = 0,00

x₃₂ = 0,0

x₃₃ = 450,00

x_{11,12, …, 33} = [ Т ]

Ограничения по объему заказов:

600 = 600 (1)

500 = 500 (2)

450 = 450 (3)

Ограничения по фонду времени:

0 < 210 (4)

66,94 < 200 (5)

180 = 180 (6)

F = 109 442,5

Решение двойственной задачи:

y₁ = 90,

y₂ = 66,56,

y₃ = 54,05,

y_{1,2, 3} = [ тыс.руб./Т ]

y₄ = 0,

y₅ = 0,

y₆ = 12,

y_{4,5, 6} = [ тыс.руб./час ]

Ограничения двойственной задачи:

90		92
90		90
87		87
66,56		75
66,56		70
65		65
54,05		57
54,05		55
53		53

F = 109 442,5

Анализ решения на минимум суммарных затрат

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

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

3. Ограничения:

3.1. Ограничение 4,5 прямой задачи выполняется как строгое неравенство, следовательно соответствующая ей переменная двойственной задачи у_4,5 = 0 (по 1-му следствию из Второй теоремы двойственности).

3.2. Ограничения 2,3,6,9 двойственной задачи выполняются как строгие неравенства, поэтому соответствующие им решения в прямой задаче равны 0.

3.3. y₁ >0, y₂ >0, y₃ >0, y₆ >0, следовательно, соответствующие им ограничения прямой задачи (1), (2), (3), (6) выполняются как строгое равенство (но 2 следствию из Второй теоремы двойственности),

3.4. x₁₂ > 0, x₁₃ > 0, x₂₃ > 0, x₃₃ > 0, следовательно, соответствующие им ограничения двойственной задачи выполняются как строгое равенство (2), (3), (6), (9) (по 4 следствию из Второй теоремы двойственности).

4. При увеличении объема заказов 1-й марки металла на 1 т. прибыль уменьшится на 90 тыс. руб.

При увеличении объема заказов 2-й марки металла на 1 т. прибыль уменьшится на 66,56 тыс. руб.

При увеличении объема заказов 3-й марки металла на 1 т. прибыль уменьшится на 54,05 тыс. руб.

5. При увеличении фонда времени на 1 час на 1-ой печи прибыль останется прежней.

При увеличении фонда времени на 1 час на 2-ой печи прибыль останется прежней.

При увеличении фонда времени на 1 час на 3-ой печи прибыль увеличится на 12 тыс. руб.

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

Прямая задача

(95-92)x₁₁ + (95-90)x₁₂ + (95-87)x₁₃ + (80-75)x₂₁ + (80-70)x₂₂ + (80-65)x₂₃ + (60-57)x₃₁ + (60-55)x₃₂ + (60-53)x₃₃ max

3x₁₁ + 5x₁₂ + 8x₁₃ + 5x₂₁ + 10x₂₂ + 15x₂₃ + 3x₃₁ + 5x₃₂ + 7x₃₃ max

Ограничения по объему заказов:

x₁₁ + x₁₂ + x₁₃ ? 600

x₂₁ + x₂₂ + x₂₃ ? 500

x₃₁ + x₃₂ + x₃₃ ? 450

Ограничения по фонду времени:

(4x₁₁ + 4,5x₁₂ + 5x₁₃) / 20 ? 210

(3,2x₂₁ + 3,5x₂₂ + 4x₂₃) / 30 ? 200

(3x₃₁ + 3,2x₃₂ + 3,5x₃₃) / 40 ? 180

Преобразуем ограничения по фонду времени:

0,2x₁₁ + 0,225x₁₂ + 0,25x₁₃ ? 210

0,1067x₂₁ + 0,1167x₂₂ + 0,13x₂₃ ? 200

0,075x₃₁ + 0,08x₃₂ + 0,0875x₃₃ ? 180

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

-600y₁ - 500y₂ - 450y₃ + 210y₄ + 200y₅ + 180y₆ min

- y₁ + 0,20y₄ ? 4,

- y₁ + 0,11y₅ ? 5,

- y₁ + 0,08y₆ ? 6,

- y₂ + 0,23y₄ ? 5,

- y₂ + 0,12y₅ ? 10,

- y₂ + 0,08y₆ ? 13,

- y₃ + 0,25y₄ ? 5,

- y₃ + 0,13y₅ ? 8,

- y₃ + 0,09y₆ ? 10.

Решение прямой и двойственной задачи на максимум общей прибыли

Прямая задача:

x₁₁ = 600,00

x₁₂ = 0,00

x₁₃ = 0,00

x₂₁ = 527,18

x₂₂ = 1713,80

x₂₃ = 1384,60

x₃₁ = 450,00

x₃₂ = 0

x₃₃ = 0

x_{11,12, …, 33} = [ Т ]

Ограничения по объему заказов:

600,00 ? 600,00 (1)

3625,59 ? 500,00 (2)

450,00 ? 450,00 (3)

Ограничения по фонду времени:

210,00 = 210,00 (4)

200,00 = 200,00 (5)

180,00 = 180,00 (6)

F = 43 693,1

Решение двойственной задачи:

y₁ = 6,37,

y₂ = 0,00,

y₃ = 0,51,

y_{1,2, 3} = [ тыс.руб./Т ]

y₄ = 56,8,

y₅ = 85,7,

y₆ = 115,4

y_{4,5, 6} = [ тыс.руб./час ]

Ограничения двойственной задачи:

3	?	3
12,908134	?	5
22,474083	?	8
5	?	5
10	?	10
15	?	15
3	?	3
6,3406575	?	5
9,5816271	?	7

F = 43 693,1

Анализ решения на минимум суммарных затрат

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

2. Ограничения:

2.1. Ограничение (2) прямой задачи выполнено как строгое неравенство, следовательно, соответствующая ей двойственная переменная равна 0 (у₂ = 0), (по 1-му следствию из Второй теоремы двойственности).

2.2. Ограничения (2), (3), (8), (9) двойственной задачи выполняются как строгие неравенства, следовательно, соответствующие значения прямой задачи равны 0 (x₁₂ = 0, x₁₃ = 0, x₃₂ = 0, x₃₃= 0), (по 3-му следствию из Второй теоремы двойственности).

2.3. x₁₁ > 0, x₂₁ > 0, x₂₂ > 0, x₂₃ > 0, x₃₁ > 0, следовательно, соответствующие им ограничения двойственной задачи выполняются как строгое равенство (1), (4), (5), (6), (7) (по 4-му следствию из Второй теоремы двойственности).

2.4. y₁ > 0, y₃ > 0, y₄ > 0, y₅ > 0, y₆ > 0, следовательно, соответствующие им ограничения прямой задачи (1), (3), (4), (5), (6) выполняются как строгое равенство (по 2-му следствию из Второй теоремы двойственности).

3. Фонд времени полностью израсходован.

4. При увеличении фонда времени на 1 час на 1-ой печи прибыль возрастет на 56,8тыс.руб.

При увеличении фонда времени на 1 час на 2-ой печи прибыль возрастет на 85,7тыс.руб.

При увеличении фонда времени на 1 час на 3-ей печи прибыль увеличится на 115,4 тыс.руб.

5. При увеличении объема заказов 1-ой марки металла на 1 т прибыль уменьшится на 6,37тыс. руб.

При увеличении объема заказов 2-ой марки металла на 1 т прибыль не изменится.

При увеличении объема заказов 3-ей марки металла на 1 т прибыль уменьшится на 0,51тыс.руб.

6. Самая выгодная марка металла - М-2.

Самая невыгодная марка металла - М-1.

7. Самая дефицитная печь - П-1.

9. Решения задачи линейного программирования на компьютере в программе Microsoft Excel.

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

1. Входим в программу Microsoft Excel.

2. Вводим коэффициенты целевой функции, ограничений.

3. Резервируем ячейки под переменные.

4. Суммируем коэффициенты целевой функции, помноженные на переменные, коэффициенты ограничений помноженные на переменные:

4.1. выбираем ячейку, в которой появится сумма;

4.2. входим в эту ячейку (в ней должен замигать курсор);

4.3. входим в функцию «Математика и тригонометрия»;

4.4. выбираем «Сумму произведений»;

4.5. выделяем мышкой ячейки, которые хотим перемножить;

4.6. в массиве 1 появится соответствующая запись;

4.7. выбираем массив 2 и т.д.;

4.8. нажимаем кнопку «Закончить»;

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

5. В меню «Сервис» ищем «Поиск решения».

6. Устанавливаем целевую ячейку, переменные и ограничения.

7. Нажимаем кнопку «Выполнить».

a. Задача на минимум суммарных затрат

b. Задача на максимум прибыли

Заключение

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

Информационные источники

1. Браверман Э.М. «Математические модели планирования и управления в экономических системах», - М.: Наука, 1976

2. Розоноэр Л.И. «Математические методы в решении экономических задач», - М.:МИСиС,1982

3. Рожков И.М., Сычев В.И. «Экономико-математические методы и модели», - М.:МИСиС, 1989.

4. Лекции по курсу «Экономико-математические методы и модели: финансовая математика» (проф. И.М.Рожков, доц. В.И.Сычев, МИСиС).

5. Лекции по курсу «Высшая математика» (доц. О.Н.Дьяченко, МИСиС).

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