Решение оптимизационных задач линейного программирования
Задачи линейного математического программирования. Построение базовой аналитической модели. Обоснование вычислительной процедуры. Решение задачи оптимизации на базе симплекс-метода. Анализ модели на чувствительность. Примеры решения оптимизационных задач.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 15.06.2020 |
| Размер файла | 1,0 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Решение оптимизационных задач линейного программирования
- СОДЕРЖАНИЕ
- Введение
1 Постановка задачи на проектирование
2 Построеник базовой аналитической модели
- 3 Обоснование вычислительной процедуры
- 4 Решение задачи оптимизации на основе симплекс-метода
5 Анализ базовой аналитической модели на чувствительность
- 5.1 Статус и ценность ресурсов
5.2 Анализ на чувствительность к изменениям поставок ресурсов
5.3 Анализ на чувствительность к изменениям минимально необходимого объема производства
5.4 Анализ на чувствительность к изменениям прибыли от продажи единицы продукции
- 6 Построение модифицированной аналитической модели и анализ результатов модификации
7 Примеры постановок и решения оптимизационных задач
- Заключение
- Список ипользованных источников
- Приложение А Рабочий лист MS Excel с результатами оптимизации на основе базовой модели
- Приложение Б Рабочий лист MS Excel с результатами оптимизации на основе модифицированной модели
ВВЕДЕНИЕ
- линейный программирование симплекс задача
- Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. До недавнего времени большинство таких задач решалось исходя из здравого смысла и опыта лиц, принимающих решения, или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант -- наилучший. При современных масштабах производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием -- математическое программирование [3].
- Математическое программирование -- область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
- Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель.
- Если целевая функция и функции, входящие в систему ограничений, линейны (первой степени) относительно входящих в задачу неизвестных х, то такой раздел математического программирования называется линейным программированием (ЛП). Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развитии и размещения производительных сил. баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.
- Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л.В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решении данного класса задач -- симплекс-метод. Термин «линейное программирование» впервые появился в 1951 г. в работах Дж. Данцига и Т. Купманса [6].
- Линейное программирование и межотраслевой баланс характеризуют линейные взаимосвязи элементов народного хозяйства.
- Однако при более глубоком исследовании в ряде задач появляются и связи нелинейного характера, когда с изменением одного элемента другие изменяются непропорционально первому. Поэтому вслед за разработкой моделей линейного программирования начались интенсивные исследования нелинейных моделей.
- Если в задаче математического программирования целевая функция и (или) хотя бы одна из функций системы ограничений нелинейна, то такой раздел называется нелинейным программированием (НЛП). Методы и модели нелинейного программирования получили широкое применение при расчете экономически выгодных партий запуска деталей в производство, при определении экономически выгодной партии поставки, поставочного комплекта, размеров запасов, распределении ограниченных ресурсов, размещении производительных сил. в тарном хозяйстве, при решении многих производственно-экономических задач и т. д.
- Если на все или некоторые переменные х наложено условие дискретности, например, целочисленности, то такие задачи рассматриваются в разделе математического программирования, называемом дискретным, в частности целочисленным (ЦП), программированием. Методами ЦП решается широкий круг задач оптимизации с неделимостями комбинаторного типа, с логическими условиями, с разрывной целевой функцией и т. д. В частности, задачи выбора (о назначениях), о контейнерных перевозках (о рюкзаке), о маршрутизации (коммивояжера), теории расписаний, комплектных поставок и комплектования, размещения производственно-складской структуры и т. л.
- Если параметры целевой функции и (или) системы ограничений изменяются во времени или целевая функция имеет аддитивный либо мультипликативный вид или сам процесс выработки решения имеет многошаговый характер, то такие задачи решаются методами динамического программирования (ДП).
- Методами ДП могут решаться задачи перспективного и текущего планирования, управления производством, поставками и запасами в условиях изменяющегося спроса, распределения ограниченных ресурсов, в частности размещения капитальных вложений, замены оборудования, обновления и восстановления элементов сложных человеко-машинных организационных систем и т, д.
- В перечисленных выше разделах математического программирования предполагается, что вся информация о протекании процессов заранее известна и достоверна. Такие методы оптимизации называются детерминированными или методами обоснования решений в условиях определенности.
- Если параметры, входящие в функцию цели, или ограничения задачи являются случайными, недостоверными величинами или если приходится принимать решения в условиях риска, неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а соответствующий раздел называется стохастическим программированием (СП). К нему в первую очередь следует отнести методы и модели выработки решений в условиях конфликтных ситуаций (математическая теория игр), в условиях неполной информации (экспертные оценки), в условиях риска (статистические решении) и др.
- Позднее появились другие типы задач, учитывающих специфику целевой функции и системы ограничений, в связи с чем возникли параметрическое, дробно-линейное, блочное, сетевое (потоковое), многоиндексное, булевское, комбинаторное н другие типы программирования. В случае нелинейностей специфика задач породила квадратичное, биквадратичное, сепарабельное, выпуклое и другие типы программирования. Появились численные методы отыскания оптимальных решений: градиентные, штрафных и барьерных функций, возможных направлений, линейной аппроксимации, случайного поиска и др.
- К математическому программированию относятся также методы решения экстремальных задач с бесконечным числом переменных --бесконечномерное программирование [2, 6].
- Задачи математического программирования с одной целевой функцией решаются методами скалярной оптимизации. Однако реальные ситуации настолько сложны, что нередко приходится одновременно учитывать несколько целевых функций, которые должны принимать экстремальные значения.
- Например, дать продукции больше, высокого качества и с минимальными затратами. Задачи, где находят решение по нескольким целевым функциям, относятся к векторной оптимизации -- это так называемые задачи многокритериального подхода.
1. ПОСТАНОВКА ЗАДАЧИ НА ПРОЕКТИРОВАНИЕ
Ткань трех артикулов (A1, A2, A3) производится на ткацких станках двух типов (СТ1 и СТ2). Фонд времени работы станков типа СТ1 составляет 50 тыс. ч, станков типа СТ2 - 30 тыс. ч. Производительность станков приведена в таблице 1.1.
Таблица 1.1 - Производительность станков
|
Станки |
Производительность, м/ч |
|||
|
А1 |
А2 |
А3 |
||
|
СТ1 |
10 |
6 |
20 |
|
|
СТ2 |
20 |
20 |
5 |
Для изготовления ткани используются пряжа и краситель. Предприятие имеет возможность использовать 60 т пряжи и 5 т красителя. Нормы расхода пряжи и красителя (в килограммах на 1000 м ткани) приведены в таблице 1.2.
Таблица 1.2 - Нормы расхода пряжи и красителя
|
Ресурс |
Расход, кг на 1000 м |
|||
|
А1 |
А2 |
А3 |
||
|
Пряжа |
140 |
100 |
200 |
|
|
Краситель |
5 |
5 |
8 |
Для выполнения заказов требуется выпустить не менее 5 тыс. м ткани артикула А2.
Прибыль предприятия от продажи 1 м ткани артикулов А1 или А3 составляет 15 ден.ед., от 1 м ткани артикула А2 - 10 ден.ед.
Составить план производства тканей, обеспечивающий предприятию максимальную прибыль.
2. ПОСТРОЕНИЕ БАЗОВОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ
В данной задаче требуется определить, сколько метров ткани каждого артикула требуется выпустить, чтобы получить максимальную прибыль.
Для построения математической модели задачи введем переменные. Обозначим через X1 выпуск ткани артикула А1, через X2 - выпуск ткани артикула А2, через X3 - выпуск ткани артикула А3 (в метрах).
В задаче имеются ограничения на использование времени работы станков - типа СТ1 и типа СТ2. Чтобы сформулировать их, используем показатели производительности станков для изготовления 1 м ткани. В данном случае необходимо будет перейти к емкостным показателям, которые измеряются количеством времени, затрачиваемым на единицу продукции.
Составим ограничение на использование фонда времени работы станка типа СТ1. На изготовление 1 м ткани артикула А1 будет расходоваться 1/10 ч, следовательно, для производства X1 м будет израсходовано (1/10)X1 ч. Аналогично, для производства X2 м ткани артикула А2 будет израсходовано (1/6)X2 ч, для производства X3 м ткани артикула А3 будет израсходовано (1/20)X3 ч. Так как фонд времени работы станка типа СТ1 составляет 50 тыс. ч, составим первое ограничение
(1/10)X1 + (1/6)X2 + (1/20)X3 ? 50000.
Аналогичным образом составим ограничение на использование фонда времени работы станка типа СТ2.
(1/20)X1 + (1/20)X2 + (1/5)X3 ? 30000.
В данной задаче имеются ограничения на расход ресурсов - пряжи и красителя. Чтобы сформулировать их, найдем расход каждого ресурса на выпуск единицы каждого вида продукции.
Составим ограничение на расход пряжи. На выпуск 1 м ткани артикула А1 расходуется 140/1000 кг пряжи; значит, расход пряжи на весь выпуск ткани артикула А1 составит (140/1000)X1 кг. На выпуск ткани артикула А2 будет израсходовано (100/1000)X2 кг, на выпуск ткани артикула А3 будет израсходовано (200/1000)X3 кг. Таким образом, общий расход пряжи составит (140/1000)X1 + (100/1000)X2 + (200/1000)X3 кг. Эта величина не должна превышать 60 т. Поэтому можно записать следующее ограничение:
(140/1000)X1 + (100/1000)X2 + (200/1000)X3 ? 60000.
Аналогично можно составить ограничение на расход красителя:
(5/1000)X1 + (5/1000)X2 + (8/1000)X3 ? 5000.
Имеется также ограничение на выпуск ткани артикула А2. Чтобы выполнить заказ, необходимо выпустить не менее 5 тыс. м ткани артикула А2:
X2 ? 5000.
Кроме того, переменные X1, X2 и X3 по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают выпуск ткани. Поэтому необходимо указать ограничения неотрицательности: Xi ? 0, i=1,…,3.
В данной задаче требуется определить план выпуска ткани, обеспечивающий получение максимальной прибыли.
Прибыль предприятия от продажи 1 м ткани артикулов А1 или А3 составляет 15 ден.ед., от 1 м ткани артикула А2 - 10 ден.ед. Так как прибыль предприятия от продажи 1 м ткани артикула А1 составляет 15 ден.ед., то прибыль от продажи X1 м составит 15X1 ден.ед. Рассуждая аналогичным образом, получим значение общей прибыли от производства тканей в ден.ед.
15X1 + 10X2 + 15X3.
Требуется найти такие значения переменных X1, X2, X3, при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:
F = 15X1+10X2+15X3 > max.
Приведем полную математическую модель рассматриваемой задачи:
(1/10)X1 + (1/6)X2 + (1/20)X3 ? 50000
(1/20)X1 + (1/20)X2 + (1/5)X3 ? 30000 (2.1)
(140/1000)X1 + (100/1000)X2 + (200/1000)X3 ? 60000
(5/1000)X1 + (5/1000)X2 + (8/1000)X3 ? 5000
X2 ? 5000
Xi ? 0, i=1,…,3.
F = 15X1+10X2+15X3 > max. (2.2)
При необходимости, если не будет получен целочисленный план, на переменные будут наложены ограничения целочисленности.
3. ОБОСНОВАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ
Все ограничения и целевая функция в данной задаче линейны, поэтому для ее решения можно использовать симплекс-метод.
В математической модели задачи имеется ограничение “больше или равно”. После приведения такого ограничения к стандартной форме в нем не содержится базисной переменной. Поэтому для решения задачи потребуется использовать один из методов искусственного базиса. В данном случае будет применен двухэтапный метод.
При необходимости применим методы целочисленного программирования [4, 5].
4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ СИМПЛЕКС-МЕТОДА
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Перейдем к канонической форме для построения первого опорного плана путем введения дополнительных переменных.
В 1-м неравенстве вводим базисную переменную x4. В 2-м неравенстве вводим базисную переменную x5. В 3-м неравенстве вводим базисную переменную x6. В 4-м неравенстве вводим базисную переменную x7 со знаком минус. В 5-м неравенстве вводим базисную переменную x8 со знаком минус.
1/10x1+1/6x2+1/20x3+x4 = 50000
1/20x1+1/20x2+1/5x3+x5 = 30000
7/50x1+1/10x2+1/5x3+x6 = 60000
1/200x1+1/200x2+1/125x3+x7 = 5000
x2-x8 = 5000
Введем искусственные переменные x: в 5-м равенстве вводим переменную x9.
1/10x1+1/6x2+1/20x3+x4 = 50000
1/20x1+1/20x2+1/5x3+x5 = 30000
7/50x1+1/10x2+1/5x3+x6 = 60000
1/200x1+1/200x2+1/125x3+x7 = 5000
x2-x8+x9 = 5000
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 15x1+10x2+15x3 - Mx9 > max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Из уравнения выражаем искусственную переменную: x9 = 5000-x2+x8, которую подставим в целевую функцию:
F(X) = (15)x1+(10+M)x2+(15)x3+(-M)x8+(-5000M) > max
Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7, x9. Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,50000,30000,60000,5000,0,5000). Базисное решение называется допустимым, если оно неотрицательно (таблица 4.1).
Таблица 4.1
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
x4 |
50000 |
1/10 |
1/6 |
1/20 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
x5 |
30000 |
1/20 |
1/20 |
1/5 |
0 |
1 |
0 |
0 |
0 |
0 |
|
|
x6 |
60000 |
7/50 |
1/10 |
1/5 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
x7 |
5000 |
1/200 |
1/200 |
1/125 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
x9 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
|
|
F(X0) |
-5000M |
-15 |
-10-M |
-15 |
0 |
0 |
0 |
0 |
M |
0 |
Переходим к основному алгоритму симплекс-метода. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai2 и выберем наименьшее: min (50000 : 1/6 , 30000 : 1/20 , 60000 : 1/10 , 5000 : 1/200 , 5000 : 1 ) = 5000. Следовательно, 5-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и строки (таблица 4.2).
Таблица 4.2
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
|
|
x4 |
50000 |
1/10 |
1/6 |
1/20 |
1 |
0 |
0 |
0 |
0 |
0 |
300000 |
|
|
x5 |
30000 |
1/20 |
1/20 |
1/5 |
0 |
1 |
0 |
0 |
0 |
0 |
600000 |
|
|
x6 |
60000 |
7/50 |
1/10 |
1/5 |
0 |
0 |
1 |
0 |
0 |
0 |
600000 |
|
|
x7 |
5000 |
1/200 |
1/200 |
1/125 |
0 |
0 |
0 |
1 |
0 |
0 |
1000000 |
|
|
x9 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
5000 |
|
|
F(X1) |
-5000M |
-15 |
-10-M |
-15 |
0 |
0 |
0 |
0 |
M |
0 |
Формируем следующую часть симплексной таблицы. Вместо переменной x9 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x9 плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы 4.3.
Таблица 4.3
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
50000-(5000 * 1/6):1 |
1/10-(0 * 1/6):1 |
1/6-(1 * 1/6):1 |
1/20-(0 * 1/6):1 |
1-(0 * 1/6):1 |
0-(0 * 1/6):1 |
0-(0 * 1/6):1 |
0-(0 * 1/6):1 |
0-(-1 * 1/6):1 |
0-(1 * 1/6):1 |
|
|
30000-(5000 * 1/20):1 |
1/20-(0 * 1/20):1 |
1/20-(1 * 1/20):1 |
1/5-(0 * 1/20):1 |
0-(0 * 1/20):1 |
1-(0 * 1/20):1 |
0-(0 * 1/20):1 |
0-(0 * 1/20):1 |
0-(-1 * 1/20):1 |
0-(1 * 1/20):1 |
|
|
60000-(5000 * 1/10):1 |
7/50-(0 * 1/10):1 |
1/10-(1 * 1/10):1 |
1/5-(0 * 1/10):1 |
0-(0 * 1/10):1 |
0-(0 * 1/10):1 |
1-(0 * 1/10):1 |
0-(0 * 1/10):1 |
0-(-1 * 1/10):1 |
0-(1 * 1/10):1 |
|
|
5000-(5000 * 1/200):1 |
1/200-(0 * 1/200):1 |
1/200-(1 * 1/200):1 |
1/125-(0 * 1/200):1 |
0-(0 * 1/200):1 |
0-(0 * 1/200):1 |
0-(0 * 1/200):1 |
1-(0 * 1/200):1 |
0-(-1 * 1/200):1 |
0-(1 * 1/200):1 |
|
|
5000 : 1 |
0 : 1 |
1 : 1 |
0 : 1 |
0 : 1 |
0 : 1 |
0 : 1 |
0 : 1 |
-1 : 1 |
1 : 1 |
|
|
(0)-(5000 * (-10-M)):1 |
(-15)-(0 * (-10-M)):1 |
(-10-M)-(1 * (-10-M)):1 |
(-15)-(0 * (-10-M)):1 |
(0)-(0 * (-10-M)):1 |
(0)-(0 * (-10-M)):1 |
(0)-(0 * (-10-M)):1 |
(0)-(0 * (-10-M)):1 |
(M)-(-1 * (-10-M)):1 |
(0)-(1 * (-10-M)):1 |
Получаем новую симплекс-таблицу (таблица 4.4).
Таблица 4.4
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
x4 |
147500/3 |
1/10 |
0 |
1/20 |
1 |
0 |
0 |
0 |
1/6 |
-1/6 |
|
|
x5 |
29750 |
1/20 |
0 |
1/5 |
0 |
1 |
0 |
0 |
1/20 |
-1/20 |
|
|
x6 |
59500 |
7/50 |
0 |
1/5 |
0 |
0 |
1 |
0 |
1/10 |
-1/10 |
|
|
x7 |
4975 |
1/200 |
0 |
1/125 |
0 |
0 |
0 |
1 |
1/200 |
-1/200 |
|
|
x2 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
|
|
F(X1) |
50000 |
-15 |
0 |
-15 |
0 |
0 |
0 |
0 |
-10 |
10+M |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (491662/3 : 1/20 , 29750 : 1/5 , 59500 : 1/5 , 4975 : 1/125 , - ) = 148750. Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1/5) и находится на пересечении ведущего столбца и ведущей строки (таблица 4.5).
Таблица 4.5
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
|
|
x4 |
147500/3 |
1/10 |
0 |
1/20 |
1 |
0 |
0 |
0 |
1/6 |
-1/6 |
2950000/3 |
|
|
x5 |
29750 |
1/20 |
0 |
1/5 |
0 |
1 |
0 |
0 |
1/20 |
-1/20 |
148750 |
|
|
x6 |
59500 |
7/50 |
0 |
1/5 |
0 |
0 |
1 |
0 |
1/10 |
-1/10 |
297500 |
|
|
x7 |
4975 |
1/200 |
0 |
1/125 |
0 |
0 |
0 |
1 |
1/200 |
-1/200 |
621875 |
|
|
x2 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
- |
|
|
F(X2) |
50000 |
-15 |
0 |
-15 |
0 |
0 |
0 |
0 |
-10 |
10+M |
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 2 войдет переменная x3. Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1/5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Таким образом, в новом плане 2 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы 4.6.
Таблица 4.6
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
491662/3-(29750 * 1/20):1/5 |
1/10-(1/20 * 1/20):1/5 |
0-(0 * 1/20):1/5 |
1/20-(1/5 * 1/20):1/5 |
1-(0 * 1/20):1/5 |
0-(1 * 1/20):1/5 |
0-(0 * 1/20):1/5 |
0-(0 * 1/20):1/5 |
1/6-(1/20 * 1/20):1/5 |
-1/6-(-1/20 * 1/20):1/5 |
|
|
29750 : 1/5 |
1/20 : 1/5 |
0 : 1/5 |
1/5 : 1/5 |
0 : 1/5 |
1 : 1/5 |
0 : 1/5 |
0 : 1/5 |
1/20 : 1/5 |
-1/20 : 1/5 |
|
|
59500-(29750 * 1/5):1/5 |
7/50-(1/20 * 1/5):1/5 |
0-(0 * 1/5):1/5 |
1/5-(1/5 * 1/5):1/5 |
0-(0 * 1/5):1/5 |
0-(1 * 1/5):1/5 |
1-(0 * 1/5):1/5 |
0-(0 * 1/5):1/5 |
1/10-(1/20 * 1/5):1/5 |
-1/10-(-1/20 * 1/5):1/5 |
|
|
4975-(29750 * 1/125):1/5 |
1/200-(1/20 * 1/125):1/5 |
0-(0 * 1/125):1/5 |
1/125-(1/5 * 1/125):1/5 |
0-(0 * 1/125):1/5 |
0-(1 * 1/125):1/5 |
0-(0 * 1/125):1/5 |
1-(0 * 1/125):1/5 |
1/200-(1/20 * 1/125):1/5 |
-1/200-(-1/20 * 1/125):1/5 |
|
|
5000-(29750 * 0):1/5 |
0-(1/20 * 0):1/5 |
1-(0 * 0):1/5 |
0-(1/5 * 0):1/5 |
0-(0 * 0):1/5 |
0-(1 * 0):1/5 |
0-(0 * 0):1/5 |
0-(0 * 0):1/5 |
-1-(1/20 * 0):1/5 |
1-(-1/20 * 0):1/5 |
|
|
(10+M)-(29750 * (-15)):1/5 |
(-15)-(1/20 * (-15)):1/5 |
(0)-(0 * (-15)):1/5 |
(-15)-(1/5 * (-15)):1/5 |
(0)-(0 * (-15)):1/5 |
(0)-(1 * (-15)):1/5 |
(0)-(0 * (-15)):1/5 |
(0)-(0 * (-15)):1/5 |
(-10)-(1/20 * (-15)):1/5 |
(10+M)-(-1/20 * (-15)):1/5 |
Получаем новую симплекс-таблицу (таблица 4.7).
Таблица 4.7
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
x4 |
250375/6 |
7/80 |
0 |
0 |
1 |
-1/4 |
0 |
0 |
37/240 |
-37/240 |
|
|
x3 |
148750 |
1/4 |
0 |
1 |
0 |
5 |
0 |
0 |
1/4 |
-1/4 |
|
|
x6 |
29750 |
9/100 |
0 |
0 |
0 |
-1 |
1 |
0 |
1/20 |
-1/20 |
|
|
x7 |
3785 |
3/1000 |
0 |
0 |
0 |
-1/25 |
0 |
1 |
3/1000 |
-3/1000 |
|
|
x2 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
|
|
F(X2) |
2281250 |
-111/4 |
0 |
0 |
0 |
75 |
0 |
0 |
-61/4 |
61/4+M |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (417291/6 : 7/80 , 148750 : 1/4 , 29750 : 9/100 , 3785 : 3/1000 , - ) = 3305555/9. Следовательно, 3-ая строка является ведущей. Разрешающий элемент равен 9/100 (таблица 4.8).
Таблица 4.8
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
|
|
x4 |
250375/6 |
7/80 |
0 |
0 |
1 |
-1/4 |
0 |
0 |
37/240 |
-37/240 |
10015000/21 |
|
|
x3 |
148750 |
1/4 |
0 |
1 |
0 |
5 |
0 |
0 |
1/4 |
-1/4 |
595000 |
|
|
x6 |
29750 |
9/100 |
0 |
0 |
0 |
-1 |
1 |
0 |
1/20 |
-1/20 |
3305555/9 |
|
|
x7 |
3785 |
3/1000 |
0 |
0 |
0 |
-1/25 |
0 |
1 |
3/1000 |
-3/1000 |
3785000/3 |
|
|
x2 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
- |
|
|
F(X3) |
2281250 |
-111/4 |
0 |
0 |
0 |
75 |
0 |
0 |
-61/4 |
61/4+M |
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 3 войдет переменная x1. Строка, соответствующая переменной x1 в плане 3, получена в результате деления всех элементов строки x6 плана 2 на разрешающий элемент РЭ=9/100. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Все остальные элементы нового плана 3 определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы 4.9.
Таблица 4.9
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
417291/6-(29750 * 7/80):9/100 |
7/80-(9/100 * 7/80):9/100 |
0-(0 * 7/80):9/100 |
0-(0 * 7/80):9/100 |
1-(0 * 7/80):9/100 |
-1/4-(-1 * 7/80):9/100 |
0-(1 * 7/80):9/100 |
0-(0 * 7/80):9/100 |
37/240-(1/20 * 7/80):9/100 |
-37/240-(-1/20 * 7/80):9/100 |
|
|
148750-(29750 * 1/4):9/100 |
1/4-(9/100 * 1/4):9/100 |
0-(0 * 1/4):9/100 |
1-(0 * 1/4):9/100 |
0-(0 * 1/4):9/100 |
5-(-1 * 1/4):9/100 |
0-(1 * 1/4):9/100 |
0-(0 * 1/4):9/100 |
1/4-(1/20 * 1/4):9/100 |
-1/4-(-1/20 * 1/4):9/100 |
|
|
29750 : 9/100 |
9/100 : 9/100 |
0 : 9/100 |
0 : 9/100 |
0 : 9/100 |
-1 : 9/100 |
1 : 9/100 |
0 : 9/100 |
1/20 : 9/100 |
-1/20 : 9/100 |
|
|
3785-(29750 * 3/1000):9/100 |
3/1000-(9/100 * 3/1000):9/100 |
0-(0 * 3/1000):9/100 |
0-(0 * 3/1000):9/100 |
0-(0 * 3/1000):9/100 |
-1/25-(-1 * 3/1000):9/100 |
0-(1 * 3/1000):9/100 |
1-(0 * 3/1000):9/100 |
3/1000-(1/20 * 3/1000):9/100 |
-3/1000-(-1/20 * 3/1000):9/100 |
|
|
5000-(29750 * 0):9/100 |
0-(9/100 * 0):9/100 |
1-(0 * 0):9/100 |
0-(0 * 0):9/100 |
0-(0 * 0):9/100 |
0-(-1 * 0):9/100 |
0-(1 * 0):9/100 |
0-(0 * 0):9/100 |
-1-(1/20 * 0):9/100 |
1-(-1/20 * 0):9/100 |
|
|
(61/4+M)-(29750 * (-111/4)):9/100 |
(-111/4)-(9/100 * (-111/4)):9/100 |
(0)-(0 * (-111/4)):9/100 |
(0)-(0 * (-111/4)):9/100 |
(0)-(0 * (-111/4)):9/100 |
(75)-(-1 * (-111/4)):9/100 |
(0)-(1 * (-111/4)):9/100 |
(0)-(0 * (-111/4)):9/100 |
(-61/4)-(1/20 * (-111/4)):9/100 |
(61/4+M)-(-1/20 * (-111/4)):9/100 |
Получаем новую симплекс-таблицу (таблица 4.10).
Таблица 4.10
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
|
x4 |
115250/9 |
0 |
0 |
0 |
1 |
13/18 |
-35/36 |
0 |
19/180 |
-19/180 |
|
|
x3 |
595000/9 |
0 |
0 |
1 |
0 |
70/9 |
-25/9 |
0 |
1/9 |
-1/9 |
|
|
x1 |
2975000/9 |
1 |
0 |
0 |
0 |
-100/9 |
100/9 |
0 |
5/9 |
-5/9 |
|
|
x7 |
8380/3 |
0 |
0 |
0 |
0 |
-1/150 |
-1/30 |
1 |
1/750 |
-1/750 |
|
|
x2 |
5000 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
|
|
F(X3) |
6000000 |
0 |
0 |
0 |
0 |
-50 |
125 |
0 |
0 |
M |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x5. Вычислим значения Di по строкам как частное от деления: bi / ai5 и из них выберем наименьшее: min (128055/9 : 13/18 , 661111/9 : 77/9 , - , - , - ) = 8500. Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен 77/9 (таблица 4.11).
Таблица 4.11
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
|
|
x4 |
115250/9 |
0 |
0 |
0 |
1 |
13/18 |
-35/36 |
0 |
19/180 |
-19/180 |
230500/13 |
|
|
x3 |
595000/9 |
0 |
0 |
1 |
0 |
77/9 |
-25/9 |
0 |
1/9 |
-1/9 |
8500 |
|
|
x1 |
2975000/9 |
1 |
0 |
0 |
0 |
-100/9 |
100/9 |
0 |
5/9 |
-5/9 |
- |
|
|
x7 |
8380/3 |
0 |
0 |
0 |
0 |
-1/150 |
-1/30 |
1 |
1/750 |
-1/750 |
- |
|
|
x |
Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009
