Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Программирование и основы алгоритмизации (ведение в исследование операций)

Программирование и основы алгоритмизации (ведение в исследование операций)

Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	28.10.2014
Размер файла	58,9 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

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

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

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

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

по дисциплине «Программирование и основы алгоритмизации (введение в исследование операций)»

Содержание

Введение

1. Формализация задач

2. Методы решения

3. Решение задачи

4. Решение задачи в среде MS EXCEL

5. Анализ задачи на чувствительность

Заключение

Литература

Введение

Мебельная фабрика выпускает столы, стулья, платяные и книжные шкафы. При изготовлении этой продукции используется два типа древесных материалов (досок). В таблице приведены нормативные затраты на единицу изделия. Объемы наличных ресурсов каждого типа соответственно равны 1500, 1000, 3200. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно.

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

Таблица 1

Ресурсы	Запас ресурсов	Затраты
		Стол	Стул	Шкаф платяной	Шкаф книжный
Доски I типа	1500	5	1	12	15
Доски II типа	1000	3	2	6	5
Труд чел./ч.	3200	7	5	10	12
Прибыль		60	25	140	160

1. Формализация задачи

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

Организация операции.

В качестве параметров, описывающих количество каждого вида продукции, примем:

x₁ - количество столов, x₂ - количество стульев, x₃ - количество шкафов платяных, x₄ - количество шкафов книжных. Единица измерения - штуки. При этом, имеем условные ограничения: количество выпускаемой продукции не может быть отрицательным, и является целым числом: хi?0, хi-целые числа (i = 1…4).

Оперирующая сторона

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

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

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

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

Доски I типа, доски II типа, трудовой ресурс, установленное условие количества изделий. Данные ограничения приведены в системе:

5x₁ + x₂ + 12x₃ + 15x₄?1500 - доски I типа.

3x₁ + 2x₂ + 6x₃ + 5x₄?1000 - доски II типа.

7x₁ + 5x₂ + 10x₃ + 12x₄?3200 - трудовой ресурс.

x₁?40 - количество столов.

x₂?120 - количество стульев.

x₃?20 - количество шкафов платяных.

x₄?20 - количество шкафов книжных.

Критерий эффективности

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

Т.к. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно организации операции и параметров, заданных выше, то целевая функция имеет вид: L(x) = 60x₁+25x₂ +140x₃+160x₄ (>max)

Стратегии ОС

Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. В виду поставленной цели и имеющихся у меня в настоящий момент знаний, лучшая и выполнимая стратегия - рассчет оптимального количества изделий. ЛПР может перейти к другим стратегиям, путем введения новых ограничений, и активных средств. Так же можно предположить существование субъективных желаний исполнителя и заказчика, определяющее выбор стратегии ОС. Количество этих стратегий определяется многоугольником решений задачи. ЛПР может принять и выбрать любую из них.

2. Методы решения

Данная задача относится к типу целочисленных.

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

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

- методы отсечений

- методы разветвлений

- приближенные методы (даны допустимые решения, хотя и в общем случае неоптимальные)

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

3. Решение задачи

программирование прибыль мебельный таблица

Цель задачи - получение максимальной прибыли - может быть достигнута несколькими способами. Математическим выражением цели является критериальная функции L, структура которой отражает вклад каждого из способов достижения цели. В сформулированной задаче представлено n таких способов. Под способом достижения цели понимается получение информации о распределении ресурсов для максимизации прибыли. Коэффициент C_jпредставляет собой удельную прибыль применения j-того способа достижения цели (прибыль от продажи одного изделия j-того типа). Переменные Х_j - искомые величины, представляющие собой интенсивность использования j-того способа достижения цели (количество изделий j-того типа).

Для достижения цели имеем: m- виды ресурсов, b_i - возможный объем потребления i-того ресурса (максимальное количество древесного ресурса и трудового фактора). Коэффициент a_ij - расход i-того ресурса для производства одного изделия j-того типа.

Метод Гомори

Решим задачу с нецелочисленными переменными:

Максимизировать

L(x) = 60x₁+25x₂ +140x₃+160x₄

при ограничениях

5x₁ + x₂ + 12x₃ + 15x₄?1500

3x₁ + 2x₂ + 6x₃ + 5x₄?1000

7x₁ + 5x₂ + 10x₃ + 12x₄?3200

x₁?40

x₂?120

x₃?20

x₄?20

хi?0

Этап 1

Приведем модель к стандартному виду: введем балансовые переменные x₅, x₆, x₇, x₈, x₉, x_10,x_11, не имеющие физического смысла для приведения неравенств к равенствам.

Максимизировать

L(x) = 60x₁+25x₂ +140x₃+160x₄

при ограничениях

5x₁ + x₂ + 12x₃ + 15x₄ + x₅= 1500

3x₁ + 2x₂ + 6x₃ + 5x₄ + x₆ = 1000

7x₁ + 5x₂ + 10x₃ + 12x₄+x₇ = 3200

x₁ -x₈ = 40

x₂ -x₉= 120

x₃-x₁₀= 20

x₄ +x₁₁ = 20

x_1… x₁₁?0

Решение системы производится путём ввода искусственных переменных Х_i. Для исключения из базиса этих переменных, их вводят в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных. Таким образом, из исходной получается новая M-задача.

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна - для составляющей L(x), а другая - для составляющей M. При составлении симплекс таблицы полагают, что исходные переменные являются небазисными, а дополнительные (x_n+m) и искусственные(X_i)- базисными.

Этап 2

Введем искусственные переменные x₁₂, x₁₃, x₁₄

5x₁ + x₂ + 12x₃ + 15x₄ + x₅ = 1500

3x₁ + 2x₂ + 6x₃ + 5x₄+x₆ = 1000

7x₁ + 5x₂ + 10x₃ + 12x₄ +x₇ = 3200

x₁ -x₈ +x₁₂ = 40

x₂ -x₉ + x₁₃ = 120

x₃ -x₁₀ + x₁₄ = 20

x₄ +x₁₁ = 20

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

L(X) = 60x₁+25x₂+140x₃+160x₄ - Mx₁₂ - Mx₁₃ - Mx₁₄ > max

Из уравнений выражаем искусственные переменные:

x₁₂ = 40-x₁+x₈

x₁₃ = 120-x₂+x₉

x₁₄ = 20-x₃+x₁₀

подставим в целевую функцию:

L(X) = (60+M)x₁+(25+M)x₂+(140+M)x₃+(160)x₄+(-M)x₈+(-M)x₉+(-M)x₁₀+

+(-180M) x₁₁

Прежде чем приступить к симплекс-преобразованиям, запишем исходные данные:

1. Размерность матрицы А - m x n, m=7, n=14.

2. Матрица А:

Таблица 2

5	1	12	15	1	0	0	0	0	0	0	0	0	0
3	2	6	5	0	1	0	0	0	0	0	0	0	0
7	5	10	12	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	0	0	-1	0	0	0	1	0	0
0	1	0	0	0	0	0	0	-1	0	0	0	1	0
0	0	1	0	0	0	0	0	0	-1	0	0	0	1
0	0	0	1	0	0	0	0	0	0	1	0	0	0

3. Вектор свободных членов в уравнениях ограничений b_i_,i=1…m:

b=(1500, 1000, 3200, 40, 120, 20, 20)

4. Коэффициенты при переменных в критериальной функции C_j:

C=(60+M, 25+M, 140+M,160,0,0,0,-M,-M,-M, -180M,0,0,0)

Этап 4

Симплекс преобразования.

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

x₅, x₆, x₇, x₁₂, x₁₃, x₁₄, x₁₁,

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

X1 = (0,0,0,0,1500,1000,3200,0,0,0,20,40,120,20)

Таблица 3

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₅	1500	5	1	12	15	1	0	0	0	0	0	0	0	0	0
x₆	1000	3	2	6	5	0	1	0	0	0	0	0	0	0	0
x₇	3200	7	5	10	12	0	0	1	0	0	0	0	0	0	0
x₁₂	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₁₄	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X0)	-180M	-60-M	-25-M	-140-M	-160	0	0	0	M	М	M	0	0	0	0

Итерация №0.

Первый опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

b_i / a_i3 и из них выберем наименьшее: x₁₄- разрешающая строка

Разрешающий элемент = 1.

Таблица 4

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₅	1500	5	1	12	15	1	0	0	0	0	0	0	0	0	0	125
x₆	1000	3	2	6	5	0	1	0	0	0	0	0	0	0	0	166²/₃
x₇	3200	7	5	10	12	0	0	1	0	0	0	0	0	0	0	320
x₁₂	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₁₄	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1	20
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	-
L(X1)	-180M	-60-M	-25-M	-140-M	-160	0	0	0	M	M	M	0	0	0	0	0

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

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₅	1260	5	1	0	15	1	0	0	0	0	12	0	0	0	-12
x₆	880	3	2	0	5	0	1	0	0	0	6	0	0	0	-6
x₇	3000	7	5	0	12	0	0	1	0	0	10	0	0	0	-10
x₁₂	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X1)	2800-160M	-60-M	-25-M	0	-160	0	0	0	M	M	-140	0	0	0	140+M

Итерация №1.

Данный опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее: строка x₁₂

Разрешающий элемент = 1

Таблица 6

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₅	1260	5	1	0	15	1	0	0	0	0	12	0	0	0	-12	252
x₆	880	3	2	0	5	0	1	0	0	0	6	0	0	0	-6	293¹/₃
x₇	3000	7	5	0	12	0	0	1	0	0	10	0	0	0	-10	428⁴/₇
x₁₂	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	40
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1	-
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	-
L(X2)	2800-160M	-60-M	-25-M	0	-160	0	0	0	M	M	-140	0	0	0	140+M	0

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

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₅	1060	0	1	0	15	1	0	0	5	0	12	0	-5	0	-12
x₆	760	0	2	0	5	0	1	0	3	0	6	0	-3	0	-6
x₇	2720	0	5	0	12	0	0	1	7	0	10	0	-7	0	-10
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X2)	5200-120M	0	-25-M	0	-160	0	0	0	-60	M	-140	0	60+M	0	140+M

Итерация №2.

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

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее: x₁₃ строка является разрешающей.

Разрешающий элемент =1

Таблица 8

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₅	1060	0	1	0	15	1	0	0	5	0	12	0	-5	0	-12	1060
x₆	760	0	2	0	5	0	1	0	3	0	6	0	-3	0	-6	380
x₇	2720	0	5	0	12	0	0	1	7	0	10	0	-7	0	-10	544
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₁₃	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	120
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1	-
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	-
L(X3)	5200-120M	0	-25-M	0	-160	0	0	0	-60	M	-140	0	60+M	0	140+M	0

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

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₅	940	0	0	0	15	1	0	0	5	1	12	0	-5	-1	-12
x₆	520	0	0	0	5	0	1	0	3	2	6	0	-3	-2	-6
x₇	2120	0	0	0	12	0	0	1	7	5	10	0	-7	-5	-10
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X3)	8200	0	0	0	-160	0	0	0	-60	-25	-140	0	60+M	25+M	140+M

Итерация №3.

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

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее: строка x₁₁

Разрешающий элемент =1.

Таблица 10

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₅	940	0	0	0	15	1	0	0	5	1	12	0	-5	-1	-12	62²/₃
x₆	520	0	0	0	5	0	1	0	3	2	6	0	-3	-2	-6	104
x₇	2120	0	0	0	12	0	0	1	7	5	10	0	-7	-5	-10	176²/₃
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1	-
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	20
L(X4)	8200	0	0	0	-160	0	0	0	-60	-25	-140	0	60+M	25+M	140+M	0

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

Таблица 11

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₅	640	0	0	0	0	1	0	0	5	1	12	-15	-5	-1	-12
x₆	420	0	0	0	0	0	1	0	3	2	6	-5	-3	-2	-6
x₇	1880	0	0	0	0	0	0	1	7	5	10	-12	-7	-5	-10
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1
L(X4)	11400	0	0	0	0	0	0	0	-60	-25	-140	160	60+M	25+M	140+M

Итерация №4.

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i10 и из них выберем наименьшее: строка x₅разрешающая.

Разрешающий элемент =12.

Таблица 12

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₅	640	0	0	0	0	1	0	0	5	1	12	-15	-5	-1	-12	53¹/₃
x₆	420	0	0	0	0	0	1	0	3	2	6	-5	-3	-2	-6	70
x₇	1880	0	0	0	0	0	0	1	7	5	10	-12	-7	-5	-10	188
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₃	20	0	0	1	0	0	0	0	0	0	-1	0	0	0	1	-
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	-
L(X5)	11400	0	0	0	0	0	0	0	-60	-25	-140	160	60+M	25+M	140+M	0

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

Таблица 13

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	53¹/₃	0	0	0	0	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	1	-1¹/₄	^-5/₁₂	^-1/₁₂	-1
x₆	100	0	0	0	0	^-1/₂	1	0	¹/₂	1¹/₂	0	2¹/₂	^-1/₂	-1¹/₂	0
x₇	1346²/₃	0	0	0	0	^-5/₆	0	1	2⁵/₆	4¹/₆	0	¹/₂	-2⁵/₆	-4¹/₆	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	73¹/₃	0	0	1	0	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	0	-1¹/₄	^-5/₁₂	^-1/₁₂	0
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X5)	18866²/₃	0	0	0	0	11²/₃	0	0	-1²/₃	-13¹/₃	0	-15	1²/₃+M	13¹/₃+M	M

Итерация №5.

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i11 и из них выберем наименьшее: x₄разрешающая строка.

Разрешающий элемент = 1.

Таблица 14

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₁₀	53¹/₃	0	0	0	0	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	1	-1¹/₄	^-5/₁₂	^-1/₁₂	-1	-
x₆	100	0	0	0	0	^-1/₂	1	0	¹/₂	1¹/₂	0	2¹/₂	^-1/₂	-1¹/₂	0	40
x₇	1346²/₃	0	0	0	0	^-5/₆	0	1	2⁵/₆	4¹/₆	0	¹/₂	-2⁵/₆	-4¹/₆	0	2693¹/₃
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₃	73¹/₃	0	0	1	0	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	0	-1¹/₄	^-5/₁₂	^-1/₁₂	0	-
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	20
L(X6)	18866²/₃	0	0	0	0	11²/₃	0	0	-1²/₃	-13¹/₃	0	-15	1²/₃+M	13¹/₃+M	M	0

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

Таблица 15

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	78¹/₃	0	0	0	1¹/₄	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	1	0	^-5/₁₂	^-1/₁₂	-1
x₆	50	0	0	0	-2¹/₂	^-1/₂	1	0	¹/₂	1¹/₂	0	0	^-1/₂	-1¹/₂	0
x₇	1336²/₃	0	0	0	^-1/₂	^-5/₆	0	1	2⁵/₆	4¹/₆	0	0	-2⁵/₆	-4¹/₆	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0
x₃	98¹/₃	0	0	1	1¹/₄	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	0	0	^-5/₁₂	^-1/₁₂	0
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X6)	19166²/₃	0	0	0	15	11²/₃	0	0	-1²/₃	-13¹/₃	0	0	1²/₃+M	13¹/₃+M	M

Итерация №6.

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i9 и из них выберем наименьшее: строка x₆разрешающая.

Разрешающий элемент равен =1¹/₂

Таблица 16

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₁₀	78¹/₃	0	0	0	1¹/₄	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	1	0	^-5/₁₂	^-1/₁₂	-1	940
x₆	50	0	0	0	-2¹/₂	^-1/₂	1	0	¹/₂	1¹/₂	0	0	^-1/₂	-1¹/₂	0	33¹/₃
x₇	1336²/₃	0	0	0	^-1/₂	^-5/₆	0	1	2⁵/₆	4¹/₆	0	0	-2⁵/₆	-4¹/₆	0	320⁴/₅
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₂	120	0	1	0	0	0	0	0	0	-1	0	0	0	1	0	-
x₃	98¹/₃	0	0	1	1¹/₄	¹/₁₂	0	0	⁵/₁₂	¹/₁₂	0	0	^-5/₁₂	^-1/₁₂	0	1180
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	-
L(X7)	19166²/₃	0	0	0	15	11²/₃	0	0	-1²/₃	-13¹/₃	0	0	1²/₃+M	13¹/₃+M	M	0

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

Таблица 17

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	75⁵/₉	0	0	0	1⁷/₁₈	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	0	^-7/₁₈	0	-1
x₉	33¹/₃	0	0	0	-1²/₃	^-1/₃	²/₃	0	¹/₃	1	0	0	^-1/₃	-1	0
x₇	1197⁷/₉	0	0	0	6⁴/₉	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	0	-1⁴/₉	0	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	153¹/₃	0	1	0	-1²/₃	^-1/₃	²/₃	0	¹/₃	0	0	0	^-1/₃	0	0
x₃	95⁵/₉	0	0	1	1⁷/₁₈	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	0	^-7/₁₈	0	0
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X7)	19611¹/₉	0	0	0	-7²/₉	7²/₉	8⁸/₉	0	2⁷/₉	0	0	0	-2⁷/₉+M	M	M

Итерация №7.

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

Вычислим значения ? по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее: строка x₁₁разрешающая.

Разрешающий элемент равен =1.

Таблица 18

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄	?
x₁₀	75⁵/₉	0	0	0	1⁷/₁₈	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	0	^-7/₁₈	0	-1	54²/₅
x₉	33¹/₃	0	0	0	-1²/₃	^-1/₃	²/₃	0	¹/₃	1	0	0	^-1/₃	-1	0	-
x₇	1197⁷/₉	0	0	0	6⁴/₉	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	0	-1⁴/₉	0	0	185²⁵/₂₉
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0	-
x₂	153¹/₃	0	1	0	-1²/₃	^-1/₃	²/₃	0	¹/₃	0	0	0	^-1/₃	0	0	-
x₃	95⁵/₉	0	0	1	1⁷/₁₈	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	0	^-7/₁₈	0	0	68⁴/₅
x₁₁	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0	20
L(X8)	19611¹/₉	0	0	0	-7²/₉	7²/₉	8⁸/₉	0	2⁷/₉	0	0	0	-2⁷/₉+M	M	M	0

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

Таблица 19

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	47⁷/₉	0	0	0	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	-1⁷/₁₈	^-7/₁₈	0	-1
x₉	66²/₃	0	0	0	0	^-1/₃	²/₃	0	¹/₃	1	0	1²/₃	^-1/₃	-1	0
x₇	1068⁸/₉	0	0	0	0	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	-6⁴/₉	-1⁴/₉	0	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	186²/₃	0	1	0	0	^-1/₃	²/₃	0	¹/₃	0	0	1²/₃	^-1/₃	0	0
x₃	67⁷/₉	0	0	1	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	-1⁷/₁₈	^-7/₁₈	0	0
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X8)	19755⁵/₉	0	0	0	0	7²/₉	8⁸/₉	0	2⁷/₉	0	0	7²/₉	-2⁷/₉+M	M	M

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

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

Таблица 20

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂	x₁₃	x₁₄
x₁₀	47⁷/₉	0	0	0	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	-1⁷/₁₈	^-7/₁₈	0	-1
x₉	66²/₃	0	0	0	0	^-1/₃	²/₃	0	¹/₃	1	0	1²/₃	^-1/₃	-1	0
x₇	1068⁸/₉	0	0	0	0	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	-6⁴/₉	-1⁴/₉	0	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	1	0	0
x₂	186²/₃	0	1	0	0	^-1/₃	²/₃	0	¹/₃	0	0	1²/₃	^-1/₃	0	0
x₃	67⁷/₉	0	0	1	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	-1⁷/₁₈	^-7/₁₈	0	0
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0	0	0
L(X9)	19755⁵/₉	0	0	0	0	7²/₉	8⁸/₉	0	2⁷/₉	0	0	7²/₉	-2⁷/₉+M	M	M

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

x₁₀ = 47⁷/₉

x₉ = 66²/₃

x₇ = 1068⁸/₉

x₁ = 40

x₂ = 186²/₃

x₃ = 67⁷/₉

x₄ = 20

F(X) = 60*40 + 25*186²/₃ + 140*67⁷/₉ + 160*20 = 19755⁵/₉

Этап 5

В полученном оптимальном плане присутствуют дробные числа.

По 3-у уравнению с переменной x₇, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью ⁸/₉, составляем дополнительное ограничение:

⁸/₉-⁵/₉x₅-²/₉x₆-⁴/₉x₈-⁵/₉x₁₁?0

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

⁸/₉-⁵/₉x₅-²/₉x₆-⁴/₉x₈-⁵/₉x₁₁ + x₁₂ = 0,

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

Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование L(x) = -L(X).

Таблица 21

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂
x₁₀	47⁷/₉	0	0	0	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	-1⁷/₁₈	0
x₉	66²/₃	0	0	0	0	^-1/₃	²/₃	0	¹/₃	1	0	1²/₃	0
x₇	1068⁸/₉	0	0	0	0	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	-6⁴/₉	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	0
x₂	186²/₃	0	1	0	0	^-1/₃	²/₃	0	¹/₃	0	0	1²/₃	0
x₃	67⁷/₉	0	0	1	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	-1⁷/₁₈	0
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0
x₁₂	^-8/₉	0	0	0	0	^-5/₉	^-2/₉	0	^-4/₉	0	0	^-5/₉	1
F(X0)	-19755⁵/₉	0	0	0	0	-7²/₉	-8⁸/₉	0	-2⁷/₉	0	0	-7²/₉	0

На пересечении ведущих строки и столбца находится разрешающий элемент равный ^-4/₉

Таблица 22

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂
x₁₀	47⁷/₉	0	0	0	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	1	-1⁷/₁₈	0
x₉	66²/₃	0	0	0	0	^-1/₃	²/₃	0	¹/₃	1	0	1²/₃	0
x₇	1068⁸/₉	0	0	0	0	⁵/₉	-2⁷/₉	1	1⁴/₉	0	0	-6⁴/₉	0
x₁	40	1	0	0	0	0	0	0	-1	0	0	0	0
x₂	186²/₃	0	1	0	0	^-1/₃	²/₃	0	¹/₃	0	0	1²/₃	0
x₃	67⁷/₉	0	0	1	0	¹/₉	^-1/₁₈	0	⁷/₁₈	0	0	-1⁷/₁₈	0
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0
x₁₂	^-8/₉	0	0	0	0	^-5/₉	^-2/₉	0	^-4/₉	0	0	^-5/₉	1
L(X)	-19755⁵	0	0	0	0	-7²/₉	-8⁸/₉	0	-2⁷/₉	0	0	-7²/₉	0
и	0	-	-	-	-	13	40	-	6¹/₄	-	-	13	-

Выполняем преобразования симплексной таблицы методом Жордана-Гаусса.

Таблица 23

Базис	B	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁	x₁₂
x₁₀	47	0	0	0	0	^-3/₈	^-1/₄	0	0	0	1	-1⁷/₈	⁷/₈
x₉	66	0	0	0	0	^-3/₄	¹/₂	0	0	1	0	1¹/₄	³/₄
x₇	1066	0	0	0	0	-1¹/₄	-3¹/₂	1	0	0	0	-8¹/₄	3¹/₄
x₁	42	1	0	0	0	1¹/₄	¹/₂	0	0	0	0	1¹/₄	-2¹/₄
x₂	186	0	1	0	0	^-3/₄	¹/₂	0	0	0	0	1¹/₄	³/₄
x₃	67	0	0	1	0	^-3/₈	^-1/₄	0	0	0	0	-1⁷/₈	⁷/₈
x₄	20	0	0	0	1	0	0	0	0	0	0	1	0
x₈	2	0	0	0	0	1¹/₄	¹/₂	0	1	0	0	1¹/₄	-2¹/₄
L(X0)	-19750	0	0	0	0	-3³/₄	-7¹/₂	0	0	0	0	-3³/₄	-6¹/₄

Решение получилось целочисленным. Нет необходимости применять метод Гомори.

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

x₁₀ = 47

x₉ = 66

x₇ = 1066

x₁ = 42

x₂ = 186

x₃ = 67

x₄ = 20

x₈ = 2

L(X) = 19750

Решение задачи: стульев нужно произвести 42 шт., столов 186 шт., шкафов платяных 67 шт., шкафов книжных 20 шт. Прибыль при полученном решении составляет 19750 р. Значения остальных переменных, введенных для преобразования неравенств в равенства, не имеют физического смысла. В ходе решения соблюдены все ограничения.

4. Решение задачи в среде MS EXCEL

Ручной просчет формулами доказан функцией «Поиск решения» в среде MS EXCEL.

К данному решению прилагаю файл *.xls, с ручным просчетом и решением задачи с помощью стандартной функции MS Excel «Поиск решения».

5. Анализ задачи на чувствительность

Произведем анализа задачи на чувствительность в среде MS EXCEL.

Ресурс доски I типа - дефицитный

Ресурс доски II типа - дефицитный

Ресурс трудовой недефицитный.

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

Интерпретация: допустимо уменьшение трудового ресурса на 1068 ч/час (с целочисленным округлением), уменьшение количества досок II типа на 100 шт., досок I типа на 430 шт. Так же уменьшения производства мебели каждого типа, кроме книжных шкафов и столов (см. столбец «допустимое уменьшение»). Аналогично допустимое увеличение ресурсов и количества мебели.

При этом оптимальное решение таково:

X₁ = 40, x₂ = 186, x₃ = 67, x₄ = 20. А максимальная прибыль составит около 19755 р.

Заключение

Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. В виду поставленной цели и имеющихся у меня в настоящий момент знаний, лучшая и выполнимая стратегия - расчет оптимального количества изделий. ЛПР может перейти к другим стратегиям, путем введения новых ограничений, и активных средств. Так же можно предположить существование субъективных желаний исполнителя и заказчика, определяющее выбор стратегии ОС. Количество этих стратегий определяется многоугольником решений задачи. ЛПР может принять и выбрать любую из них.

Литература

Фаронов В.В. Программирование на персональных ЭВМ. - М.: Изд-во МГТУ, 2009.-580 с.

Фаронов В.В. Алгоритмизация (в 3-х книгах). Кн.1. Основы Турбо Паскаля. - М.: Учебно-инженерный центр <<МВТУ - ФЕСТО ДИДАКТИК>>, 2010. - 304 с.

Федоров А. Особенности программирования. - Киев.: Диалектика, 2008.-144 с.

Хершель Р. Программирование. /2-е изд., перераб. - Вологда: МП <<МИК>>, 2009.-342 с.

Форонов В.В. Алгоритм. Начальный курс. Учебное пособие. Издание 7-е, переработанное. М.: <<Нолидж>>, издатель МОЛГАЧЕВА с.в., 2009. - 576 с.

Пильщиков В.Н. Сборник упражнений Учеб. пособ. для вузов. - М.: Наука, 2006.

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

курсовая работа "Программирование и основы алгоритмизации (ведение в исследование операций)" скачать

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

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

курсовая работа [100,0 K], добавлен 31.10.2014
Решение задачи линейного программирования симплекс-методом
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа [1,1 M], добавлен 21.03.2012
Исследование методов решения линейных уравнений
Методы ветвей и границ первого и второго порядка. Оптимальный и пассивный поиск. Недостатки метода Ньютона. Метод золотого сечения. Примеры унимодальных функций. Динамическое и линейное программирование. Метод Жордана-Гаусса. Решение задачи коммивояжера.

курсовая работа [1,1 M], добавлен 20.07.2012
Решение задач линейного программирования графическим методом
Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.

курсовая работа [663,9 K], добавлен 10.06.2014
Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.

курсовая работа [38,9 K], добавлен 15.11.2009
Применение метода динамического программирования в различных задачах
Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.

курсовая работа [503,3 K], добавлен 28.06.2015
Решение системы линейных уравнений методом Гаусса и Жордана-Гаусса
Сущность метода Гаусса при решении систем линейных уравнений. Элементарные преобразования этого метода. Краткое описание среды визуальной разработки Delphi. Описание основных применяемых процедур и алгоритм роботы программы по решению уравнений.

курсовая работа [1,1 M], добавлен 29.08.2010
Деревянный алгоритм решения задачи коммивояжёра
Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.

курсовая работа [586,3 K], добавлен 04.04.2015
Решение общей задачи линейного программирования с помощью программы Excel
Планирование прибыли при производстве двух видов топлива. Составление оптимального плана выпуска продукции для получения максимальной прибыли от ее реализации. Определение опорного плана перевозок грузов методом минимальной стоимости и с помощью Excel.

контрольная работа [32,5 K], добавлен 12.11.2014
Решение задач линейного программирования в MS Excel
Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

курсовая работа [1,1 M], добавлен 27.08.2012

Другие документы, подобные "Программирование и основы алгоритмизации (ведение в исследование операций)"

весь список подобных работ

скачать работу можно здесь

сколько стоит заказать работу?

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

5	1	12	15	1	0	0	0	0	0	0	0	0	0
3	2	6	5	0	1	0	0	0	0	0	0	0	0
7	5	10	12	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	0	0	-1	0	0	0	1	0	0
0	1	0	0	0	0	0	0	-1	0	0	0	1	0
0	0	1	0	0	0	0	0	0	-1	0	0	0	1
0	0	0	1	0	0	0	0	0	0	1	0	0	0

5	1	12	15	1	0	0	0	0	0	0	0	0	0
3	2	6	5	0	1	0	0	0	0	0	0	0	0
7	5	10	12	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	0	0	-1	0	0	0	1	0	0
0	1	0	0	0	0	0	0	-1	0	0	0	1	0
0	0	1	0	0	0	0	0	0	-1	0	0	0	1
0	0	0	1	0	0	0	0	0	0	1	0	0	0

5	1	12	15	1	0	0	0	0	0	0	0	0	0
3	2	6	5	0	1	0	0	0	0	0	0	0	0
7	5	10	12	0	0	1	0	0	0	0	0	0	0
1	0	0	0	0	0	0	-1	0	0	0	1	0	0
0	1	0	0	0	0	0	0	-1	0	0	0	1	0
0	0	1	0	0	0	0	0	0	-1	0	0	0	1
0	0	0	1	0	0	0	0	0	0	1	0	0	0