Программирование и основы алгоритмизации (ведение в исследование операций)
Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 28.10.2014 |
Размер файла | 58,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на 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. Формализация задачи
Операция - обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики, при заданных условиях.
Организация операции.
В качестве параметров, описывающих количество каждого вида продукции, примем:
x1 - количество столов, x2 - количество стульев, x3 - количество шкафов платяных, x4 - количество шкафов книжных. Единица измерения - штуки. При этом, имеем условные ограничения: количество выпускаемой продукции не может быть отрицательным, и является целым числом: хi?0, хi-целые числа (i = 1…4).
Оперирующая сторона
Руководство мебельной фабрики, как постановщик задачи. Непосредственный изготовитель продукции (трудовой ресурс) - лица, изготовляющие мебель. Покупатель (или заказчик) - лицо, обеспечивающее существование имеющейся цели. Поставщик материала (используемого ограниченного ресурса) - лицо, принимающее участие в процессе достижения цели.
Лицо, принимающее решение (ЛПР) - индивид или группа людей, которые осуществляют выбор и несут ответственность за принятое решение в соответствии со своими полномочиями, установленными руководством фирмы.
Исследователь операций - лицо, чья работа состоит в рациональной организации процесса, поиска и разработки методов решений поставленной задачи. В данной задаче исследование операций осуществляю я.
Существуют ограничения на количество ресурсов и выпускаемых изделий:
Доски I типа, доски II типа, трудовой ресурс, установленное условие количества изделий. Данные ограничения приведены в системе:
5x1 + x2 + 12x3 + 15x4?1500 - доски I типа.
3x1 + 2x2 + 6x3 + 5x4?1000 - доски II типа.
7x1 + 5x2 + 10x3 + 12x4?3200 - трудовой ресурс.
x1?40 - количество столов.
x2?120 - количество стульев.
x3?20 - количество шкафов платяных.
x4?20 - количество шкафов книжных.
Критерий эффективности
Цель задачи: Определить, какое количество изделий, выпускаемых фабрикой, удовлетворяющих последней системе, будет максимизировать прибыль.
Т.к. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно организации операции и параметров, заданных выше, то целевая функция имеет вид: L(x) = 60x1+25x2 +140x3+160x4 (>max)
Стратегии ОС
Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. В виду поставленной цели и имеющихся у меня в настоящий момент знаний, лучшая и выполнимая стратегия - рассчет оптимального количества изделий. ЛПР может перейти к другим стратегиям, путем введения новых ограничений, и активных средств. Так же можно предположить существование субъективных желаний исполнителя и заказчика, определяющее выбор стратегии ОС. Количество этих стратегий определяется многоугольником решений задачи. ЛПР может принять и выбрать любую из них.
2. Методы решения
Данная задача относится к типу целочисленных.
Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
При решении полностью целочисленных задач линейного программирования используются:
- методы отсечений
- методы разветвлений
- приближенные методы (даны допустимые решения, хотя и в общем случае неоптимальные)
Небольшая размерность задачи позволяет применить метод динамического программирования и метод сечения Гомори. Т.к. в основе последнего лежит двойственный симплекс метод линейного программирования, позволяющий наряду с нахождением решения, выявить и чувствительность модели к изменению параметров, то решим задачу этим методом.
3. Решение задачи
программирование прибыль мебельный таблица
Цель задачи - получение максимальной прибыли - может быть достигнута несколькими способами. Математическим выражением цели является критериальная функции L, структура которой отражает вклад каждого из способов достижения цели. В сформулированной задаче представлено n таких способов. Под способом достижения цели понимается получение информации о распределении ресурсов для максимизации прибыли. Коэффициент Cj представляет собой удельную прибыль применения j-того способа достижения цели (прибыль от продажи одного изделия j-того типа). Переменные Хj - искомые величины, представляющие собой интенсивность использования j-того способа достижения цели (количество изделий j-того типа).
Для достижения цели имеем: m- виды ресурсов, bi - возможный объем потребления i-того ресурса (максимальное количество древесного ресурса и трудового фактора). Коэффициент aij - расход i-того ресурса для производства одного изделия j-того типа.
Метод Гомори
Решим задачу с нецелочисленными переменными:
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
5x1 + x2 + 12x3 + 15x4?1500
3x1 + 2x2 + 6x3 + 5x4?1000
7x1 + 5x2 + 10x3 + 12x4?3200
x1?40
x2?120
x3?20
x4?20
хi?0
Этап 1
Приведем модель к стандартному виду: введем балансовые переменные x5, x6, x7, x8, x9, x10, x11, не имеющие физического смысла для приведения неравенств к равенствам.
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
5x1 + x2 + 12x3 + 15x4 + x5 = 1500
3x1 + 2x2 + 6x3 + 5x4 + x6 = 1000
7x1 + 5x2 + 10x3 + 12x4+x7 = 3200
x1 -x8 = 40
x2 -x9 = 120
x3-x10 = 20
x4 +x11 = 20
x1… x11?0
Решение системы производится путём ввода искусственных переменных Хi. Для исключения из базиса этих переменных, их вводят в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных. Таким образом, из исходной получается новая M-задача.
Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна - для составляющей L(x), а другая - для составляющей M. При составлении симплекс таблицы полагают, что исходные переменные являются небазисными, а дополнительные (xn+m) и искусственные(Xi)- базисными.
Этап 2
Введем искусственные переменные x12, x13, x14
5x1 + x2 + 12x3 + 15x4 + x5 = 1500
3x1 + 2x2 + 6x3 + 5x4+x6 = 1000
7x1 + 5x2 + 10x3 + 12x4 +x7 = 3200
x1 -x8 +x12 = 40
x2 -x9 + x13 = 120
x3 -x10 + x14 = 20
x4 +x11 = 20
Целевая функция:
L(X) = 60x1+25x2+140x3+160x4 - Mx12 - Mx13 - Mx14 > max
Из уравнений выражаем искусственные переменные:
x12 = 40-x1+x8
x13 = 120-x2+x9
x14 = 20-x3+x10
подставим в целевую функцию:
L(X) = (60+M)x1+(25+M)x2+(140+M)x3+(160)x4+(-M)x8+(-M)x9+(-M)x10+
+(-180M) x11
Прежде чем приступить к симплекс-преобразованиям, запишем исходные данные:
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. Вектор свободных членов в уравнениях ограничений bi, i=1…m:
b=(1500, 1000, 3200, 40, 120, 20, 20)
4. Коэффициенты при переменных в критериальной функции Cj:
C=(60+M, 25+M, 140+M,160,0,0,0,-M,-M,-M, -180M,0,0,0)
Этап 4
Симплекс преобразования.
Решим систему уравнений относительно базисных переменных:
x5, x6, x7, x12, x13, x14, x11,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,1500,1000,3200,0,0,0,20,40,120,20)
Таблица 3
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x5 |
1500 |
5 |
1 |
12 |
15 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x6 |
1000 |
3 |
2 |
6 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x7 |
3200 |
7 |
5 |
10 |
12 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x12 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x14 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
x11 |
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.
Первый опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x3, так как это наибольший коэффициент по модулю. Вычислим значения ? по строкам как частное от деления:
bi / ai3 и из них выберем наименьшее: x14 - разрешающая строка
Разрешающий элемент = 1.
Таблица 4
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x5 |
1500 |
5 |
1 |
12 |
15 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
125 |
|
x6 |
1000 |
3 |
2 |
6 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1662/3 |
|
x7 |
3200 |
7 |
5 |
10 |
12 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
320 |
|
x12 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x14 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
20 |
|
x11 |
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 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x5 |
1260 |
5 |
1 |
0 |
15 |
1 |
0 |
0 |
0 |
0 |
12 |
0 |
0 |
0 |
-12 |
|
x6 |
880 |
3 |
2 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
-6 |
|
x7 |
3000 |
7 |
5 |
0 |
12 |
0 |
0 |
1 |
0 |
0 |
10 |
0 |
0 |
0 |
-10 |
|
x12 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
x11 |
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.
Данный опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x1, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: строка x12
Разрешающий элемент = 1
Таблица 6
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x5 |
1260 |
5 |
1 |
0 |
15 |
1 |
0 |
0 |
0 |
0 |
12 |
0 |
0 |
0 |
-12 |
252 |
|
x6 |
880 |
3 |
2 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
-6 |
2931/3 |
|
x7 |
3000 |
7 |
5 |
0 |
12 |
0 |
0 |
1 |
0 |
0 |
10 |
0 |
0 |
0 |
-10 |
4284/7 |
|
x12 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
40 |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
- |
|
x11 |
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 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x5 |
1060 |
0 |
1 |
0 |
15 |
1 |
0 |
0 |
5 |
0 |
12 |
0 |
-5 |
0 |
-12 |
|
x6 |
760 |
0 |
2 |
0 |
5 |
0 |
1 |
0 |
3 |
0 |
6 |
0 |
-3 |
0 |
-6 |
|
x7 |
2720 |
0 |
5 |
0 |
12 |
0 |
0 |
1 |
7 |
0 |
10 |
0 |
-7 |
0 |
-10 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
x11 |
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.
Текущий план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: x13 строка является разрешающей.
Разрешающий элемент =1
Таблица 8
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x5 |
1060 |
0 |
1 |
0 |
15 |
1 |
0 |
0 |
5 |
0 |
12 |
0 |
-5 |
0 |
-12 |
1060 |
|
x6 |
760 |
0 |
2 |
0 |
5 |
0 |
1 |
0 |
3 |
0 |
6 |
0 |
-3 |
0 |
-6 |
380 |
|
x7 |
2720 |
0 |
5 |
0 |
12 |
0 |
0 |
1 |
7 |
0 |
10 |
0 |
-7 |
0 |
-10 |
544 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x13 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
120 |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
- |
|
x11 |
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 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x5 |
940 |
0 |
0 |
0 |
15 |
1 |
0 |
0 |
5 |
1 |
12 |
0 |
-5 |
-1 |
-12 |
|
x6 |
520 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
3 |
2 |
6 |
0 |
-3 |
-2 |
-6 |
|
x7 |
2120 |
0 |
0 |
0 |
12 |
0 |
0 |
1 |
7 |
5 |
10 |
0 |
-7 |
-5 |
-10 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
x11 |
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.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x4, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai4 и из них выберем наименьшее: строка x11
Разрешающий элемент =1.
Таблица 10
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x5 |
940 |
0 |
0 |
0 |
15 |
1 |
0 |
0 |
5 |
1 |
12 |
0 |
-5 |
-1 |
-12 |
622/3 |
|
x6 |
520 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
3 |
2 |
6 |
0 |
-3 |
-2 |
-6 |
104 |
|
x7 |
2120 |
0 |
0 |
0 |
12 |
0 |
0 |
1 |
7 |
5 |
10 |
0 |
-7 |
-5 |
-10 |
1762/3 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
- |
|
x11 |
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 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x5 |
640 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
1 |
12 |
-15 |
-5 |
-1 |
-12 |
|
x6 |
420 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
2 |
6 |
-5 |
-3 |
-2 |
-6 |
|
x7 |
1880 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
7 |
5 |
10 |
-12 |
-7 |
-5 |
-10 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
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.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x10, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai10 и из них выберем наименьшее: строка x5 разрешающая.
Разрешающий элемент =12.
Таблица 12
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x5 |
640 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
1 |
12 |
-15 |
-5 |
-1 |
-12 |
531/3 |
|
x6 |
420 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
3 |
2 |
6 |
-5 |
-3 |
-2 |
-6 |
70 |
|
x7 |
1880 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
7 |
5 |
10 |
-12 |
-7 |
-5 |
-10 |
188 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x3 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
- |
|
x4 |
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 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
531/3 |
0 |
0 |
0 |
0 |
1/12 |
0 |
0 |
5/12 |
1/12 |
1 |
-11/4 |
-5/12 |
-1/12 |
-1 |
|
x6 |
100 |
0 |
0 |
0 |
0 |
-1/2 |
1 |
0 |
1/2 |
11/2 |
0 |
21/2 |
-1/2 |
-11/2 |
0 |
|
x7 |
13462/3 |
0 |
0 |
0 |
0 |
-5/6 |
0 |
1 |
25/6 |
41/6 |
0 |
1/2 |
-25/6 |
-41/6 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
731/3 |
0 |
0 |
1 |
0 |
1/12 |
0 |
0 |
5/12 |
1/12 |
0 |
-11/4 |
-5/12 |
-1/12 |
0 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
L(X5) |
188662/3 |
0 |
0 |
0 |
0 |
112/3 |
0 |
0 |
-12/3 |
-131/3 |
0 |
-15 |
12/3+M |
131/3+M |
M |
Итерация №5.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец переменной x11, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai11 и из них выберем наименьшее: x4 разрешающая строка.
Разрешающий элемент = 1.
Таблица 14
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x10 |
531/3 |
0 |
0 |
0 |
0 |
1/12 |
0 |
0 |
5/12 |
1/12 |
1 |
-11/4 |
-5/12 |
-1/12 |
-1 |
- |
|
x6 |
100 |
0 |
0 |
0 |
0 |
-1/2 |
1 |
0 |
1/2 |
11/2 |
0 |
21/2 |
-1/2 |
-11/2 |
0 |
40 |
|
x7 |
13462/3 |
0 |
0 |
0 |
0 |
-5/6 |
0 |
1 |
25/6 |
41/6 |
0 |
1/2 |
-25/6 |
-41/6 |
0 |
26931/3 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x3 |
731/3 |
0 |
0 |
1 |
0 |
1/12 |
0 |
0 |
5/12 |
1/12 |
0 |
-11/4 |
-5/12 |
-1/12 |
0 |
- |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
20 |
|
L(X6) |
188662/3 |
0 |
0 |
0 |
0 |
112/3 |
0 |
0 |
-12/3 |
-131/3 |
0 |
-15 |
12/3+M |
131/3+M |
M |
0 |
Получаем новую симплекс-таблицу:
Таблица 15
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
781/3 |
0 |
0 |
0 |
11/4 |
1/12 |
0 |
0 |
5/12 |
1/12 |
1 |
0 |
-5/12 |
-1/12 |
-1 |
|
x6 |
50 |
0 |
0 |
0 |
-21/2 |
-1/2 |
1 |
0 |
1/2 |
11/2 |
0 |
0 |
-1/2 |
-11/2 |
0 |
|
x7 |
13362/3 |
0 |
0 |
0 |
-1/2 |
-5/6 |
0 |
1 |
25/6 |
41/6 |
0 |
0 |
-25/6 |
-41/6 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
x3 |
981/3 |
0 |
0 |
1 |
11/4 |
1/12 |
0 |
0 |
5/12 |
1/12 |
0 |
0 |
-5/12 |
-1/12 |
0 |
|
x11 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
L(X6) |
191662/3 |
0 |
0 |
0 |
15 |
112/3 |
0 |
0 |
-12/3 |
-131/3 |
0 |
0 |
12/3+M |
131/3+M |
M |
Итерация №6.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.
В качестве разрешающего выберем столбец x9, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai9 и из них выберем наименьшее: строка x6 разрешающая.
Разрешающий элемент равен =11/2
Таблица 16
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x10 |
781/3 |
0 |
0 |
0 |
11/4 |
1/12 |
0 |
0 |
5/12 |
1/12 |
1 |
0 |
-5/12 |
-1/12 |
-1 |
940 |
|
x6 |
50 |
0 |
0 |
0 |
-21/2 |
-1/2 |
1 |
0 |
1/2 |
11/2 |
0 |
0 |
-1/2 |
-11/2 |
0 |
331/3 |
|
x7 |
13362/3 |
0 |
0 |
0 |
-1/2 |
-5/6 |
0 |
1 |
25/6 |
41/6 |
0 |
0 |
-25/6 |
-41/6 |
0 |
3204/5 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x2 |
120 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
- |
|
x3 |
981/3 |
0 |
0 |
1 |
11/4 |
1/12 |
0 |
0 |
5/12 |
1/12 |
0 |
0 |
-5/12 |
-1/12 |
0 |
1180 |
|
x11 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
- |
|
L(X7) |
191662/3 |
0 |
0 |
0 |
15 |
112/3 |
0 |
0 |
-12/3 |
-131/3 |
0 |
0 |
12/3+M |
131/3+M |
M |
0 |
Получаем новую симплекс-таблицу:
Таблица 17
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
755/9 |
0 |
0 |
0 |
17/18 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
0 |
-7/18 |
0 |
-1 |
|
x9 |
331/3 |
0 |
0 |
0 |
-12/3 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
0 |
-1/3 |
-1 |
0 |
|
x7 |
11977/9 |
0 |
0 |
0 |
64/9 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
0 |
-14/9 |
0 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
1531/3 |
0 |
1 |
0 |
-12/3 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
0 |
-1/3 |
0 |
0 |
|
x3 |
955/9 |
0 |
0 |
1 |
17/18 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
0 |
-7/18 |
0 |
0 |
|
x11 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
L(X7) |
196111/9 |
0 |
0 |
0 |
-72/9 |
72/9 |
88/9 |
0 |
27/9 |
0 |
0 |
0 |
-27/9+M |
M |
M |
Итерация №7.
Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты. В качестве разрешающего выберем столбец x4, так как это наибольший коэффициент по модулю.
Вычислим значения ? по строкам как частное от деления: bi / ai4 и из них выберем наименьшее: строка x11 разрешающая.
Разрешающий элемент равен =1.
Таблица 18
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
? |
|
x10 |
755/9 |
0 |
0 |
0 |
17/18 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
0 |
-7/18 |
0 |
-1 |
542/5 |
|
x9 |
331/3 |
0 |
0 |
0 |
-12/3 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
0 |
-1/3 |
-1 |
0 |
- |
|
x7 |
11977/9 |
0 |
0 |
0 |
64/9 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
0 |
-14/9 |
0 |
0 |
18525/29 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
- |
|
x2 |
1531/3 |
0 |
1 |
0 |
-12/3 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
0 |
-1/3 |
0 |
0 |
- |
|
x3 |
955/9 |
0 |
0 |
1 |
17/18 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
0 |
-7/18 |
0 |
0 |
684/5 |
|
x11 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
20 |
|
L(X8) |
196111/9 |
0 |
0 |
0 |
-72/9 |
72/9 |
88/9 |
0 |
27/9 |
0 |
0 |
0 |
-27/9+M |
M |
M |
0 |
Получаем новую симплекс-таблицу:
Таблица 19
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
477/9 |
0 |
0 |
0 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
-17/18 |
-7/18 |
0 |
-1 |
|
x9 |
662/3 |
0 |
0 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
12/3 |
-1/3 |
-1 |
0 |
|
x7 |
10688/9 |
0 |
0 |
0 |
0 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
-64/9 |
-14/9 |
0 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
1862/3 |
0 |
1 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
12/3 |
-1/3 |
0 |
0 |
|
x3 |
677/9 |
0 |
0 |
1 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
-17/18 |
-7/18 |
0 |
0 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
L(X8) |
197555/9 |
0 |
0 |
0 |
0 |
72/9 |
88/9 |
0 |
27/9 |
0 |
0 |
72/9 |
-27/9+M |
M |
M |
Индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
Таблица 20
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
477/9 |
0 |
0 |
0 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
-17/18 |
-7/18 |
0 |
-1 |
|
x9 |
662/3 |
0 |
0 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
12/3 |
-1/3 |
-1 |
0 |
|
x7 |
10688/9 |
0 |
0 |
0 |
0 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
-64/9 |
-14/9 |
0 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
x2 |
1862/3 |
0 |
1 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
12/3 |
-1/3 |
0 |
0 |
|
x3 |
677/9 |
0 |
0 |
1 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
-17/18 |
-7/18 |
0 |
0 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
L(X9) |
197555/9 |
0 |
0 |
0 |
0 |
72/9 |
88/9 |
0 |
27/9 |
0 |
0 |
72/9 |
-27/9+M |
M |
M |
Оптимальный план можно записать так:
x10 = 477/9
x9 = 662/3
x7 = 10688/9
x1 = 40
x2 = 1862/3
x3 = 677/9
x4 = 20
F(X) = 60*40 + 25*1862/3 + 140*677/9 + 160*20 = 197555/9
Этап 5
В полученном оптимальном плане присутствуют дробные числа.
По 3-у уравнению с переменной x7, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 8/9, составляем дополнительное ограничение:
8/9-5/9x5-2/9x6-4/9x8-5/9x11?0
Преобразуем полученное неравенство в уравнение:
8/9-5/9x5-2/9x6-4/9x8-5/9x11 + x12 = 0,
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.
Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование L(x) = -L(X).
Таблица 21
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x10 |
477/9 |
0 |
0 |
0 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
-17/18 |
0 |
|
x9 |
662/3 |
0 |
0 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
12/3 |
0 |
|
x7 |
10688/9 |
0 |
0 |
0 |
0 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
-64/9 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
|
x2 |
1862/3 |
0 |
1 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
12/3 |
0 |
|
x3 |
677/9 |
0 |
0 |
1 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
-17/18 |
0 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
x12 |
-8/9 |
0 |
0 |
0 |
0 |
-5/9 |
-2/9 |
0 |
-4/9 |
0 |
0 |
-5/9 |
1 |
|
F(X0) |
-197555/9 |
0 |
0 |
0 |
0 |
-72/9 |
-88/9 |
0 |
-27/9 |
0 |
0 |
-72/9 |
0 |
На пересечении ведущих строки и столбца находится разрешающий элемент равный -4/9
Таблица 22
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x10 |
477/9 |
0 |
0 |
0 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
1 |
-17/18 |
0 |
|
x9 |
662/3 |
0 |
0 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
1 |
0 |
12/3 |
0 |
|
x7 |
10688/9 |
0 |
0 |
0 |
0 |
5/9 |
-27/9 |
1 |
14/9 |
0 |
0 |
-64/9 |
0 |
|
x1 |
40 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
|
x2 |
1862/3 |
0 |
1 |
0 |
0 |
-1/3 |
2/3 |
0 |
1/3 |
0 |
0 |
12/3 |
0 |
|
x3 |
677/9 |
0 |
0 |
1 |
0 |
1/9 |
-1/18 |
0 |
7/18 |
0 |
0 |
-17/18 |
0 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
x12 |
-8/9 |
0 |
0 |
0 |
0 |
-5/9 |
-2/9 |
0 |
-4/9 |
0 |
0 |
-5/9 |
1 |
|
L(X) |
-197555 |
0 |
0 |
0 |
0 |
-72/9 |
-88/9 |
0 |
-27/9 |
0 |
0 |
-72/9 |
0 |
|
и |
0 |
- |
- |
- |
- |
13 |
40 |
- |
61/4 |
- |
- |
13 |
- |
Выполняем преобразования симплексной таблицы методом Жордана-Гаусса.
Таблица 23
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x10 |
47 |
0 |
0 |
0 |
0 |
-3/8 |
-1/4 |
0 |
0 |
0 |
1 |
-17/8 |
7/8 |
|
x9 |
66 |
0 |
0 |
0 |
0 |
-3/4 |
1/2 |
0 |
0 |
1 |
0 |
11/4 |
3/4 |
|
x7 |
1066 |
0 |
0 |
0 |
0 |
-11/4 |
-31/2 |
1 |
0 |
0 |
0 |
-81/4 |
31/4 |
|
x1 |
42 |
1 |
0 |
0 |
0 |
11/4 |
1/2 |
0 |
0 |
0 |
0 |
11/4 |
-21/4 |
|
x2 |
186 |
0 |
1 |
0 |
0 |
-3/4 |
1/2 |
0 |
0 |
0 |
0 |
11/4 |
3/4 |
|
x3 |
67 |
0 |
0 |
1 |
0 |
-3/8 |
-1/4 |
0 |
0 |
0 |
0 |
-17/8 |
7/8 |
|
x4 |
20 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
x8 |
2 |
0 |
0 |
0 |
0 |
11/4 |
1/2 |
0 |
1 |
0 |
0 |
11/4 |
-21/4 |
|
L(X0) |
-19750 |
0 |
0 |
0 |
0 |
-33/4 |
-71/2 |
0 |
0 |
0 |
0 |
-33/4 |
-61/4 |
Решение получилось целочисленным. Нет необходимости применять метод Гомори.
Оптимальный целочисленный план можно записать так:
x10 = 47
x9 = 66
x7 = 1066
x1 = 42
x2 = 186
x3 = 67
x4 = 20
x8 = 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 шт. Так же уменьшения производства мебели каждого типа, кроме книжных шкафов и столов (см. столбец «допустимое уменьшение»). Аналогично допустимое увеличение ресурсов и количества мебели.
При этом оптимальное решение таково:
X1 = 40, x2 = 186, x3 = 67, x4 = 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.
контрольная работа [32,5 K], добавлен 12.11.2014Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012