Затраты на одно изделие
ЦЕНТРАЛЬНЫЙ МЕЖРЕГИОНАЛЬНЫЙ ТЕХНИКУМ ОТРАСЛЕВЫХ ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛЬСТВА
Утверждаю Зам. директора по учебной части
« » 200 г. ЗАДАНИЕ на курсовое проектирование по предмету «Математические методы»
Студенту: Сергееву Евгению Анатольевичу. Тема проекта: «Линейное программирование, решение задач симплексным методом».
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Введение Теоретическая часть Практическая часть Задачи и их решение:
Задача первая: Решить задачу симплекс методом:
X1+3X2≤300 X1+X2≤150 X1≥0 X2≥0
F = 2X1+3X2 → max
3.1.2 Задача вторая:
Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у. е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице:
Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
3.1.3. Задача третья:
На предприятии выпускают 3 вида изделий, при этом используют 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:
Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
3.1.4. Задача четвертая:
Для изготовления 4 видов продукции используются 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:
Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
Заключение Список литературы Председатель цикловой комиссии /Баранов В.А. Руководитель курсового проекта /Карпушкин А.Г.
Дата выдачи задания: Срок окончания: « » 2007 г. « » 2007 г.
СИМПЛЕКСНЫЙ МЕТОД
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым Л В.Канторовичем. Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную. Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных элемента: • способ определения какого-либо первоначального допустимого базисного решения задачи; • правило перехода к лучшему (точнее, не худшему) решению; • критерий проверки оптимальности найденного решения. Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
Обыкновенные жордановы исключения
Рассмотрим систему из m линейных уравнений с n неизвестными
a11x1 + a12x2 + … + a1nxn = b1, …………… am1x1 + am2x2 + … + amnxn = bm.
Запишем эту систему в виде таблицы
Шагом обыкновенного жорданова исключения (ОЖИ), произведенным над данной таблицей с разрешающим элементом aij ≠ 0 с I разрешающей строкой и j разрешающим столбцом, назовем операцию решения уравнения
bi = ai1x1 + ai2x2 + … + aijxj + … + ainxn
относительно xj, подстановки этого решения в исходную систему и записи вновь полученной системы в виде новой таблицы. Нетрудно проверить, что новая таблица будет иметь вид
: aij, где brs = arsaij - arjais (i ≠ r, j ≠ s),
причем все элементы таблицы нужно разделить на aij. Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил: 1) разрешающий элемент заменяется единицей 2) остальные элементы разрешающего столбца j остаются без изменения. 3) остальные элементы разрешающей строки i меняют лишь свои знаки. 4) остальные элементы brs вычисляются по формуле brs = arsaij - arjais 5) все элементы новой таблицы делятся на разрешающий элемент aij.
Пример 1. Для таблицы
один шаг жорданова исключения с разрешающими 2-й строкой и 3-м столбцом приводим к таблице
: 2 Жордановы исключения позволяют от случайно взятой декартовой системы координатных плоскостей перейти к новой системе, в которой координатами точек являются их уклонения от более интересной для той или другой задачи системы плоскостей.
Модифицированные жордановы исключения Если исходную систему уравнений ai1x1 + ai2x2 + … + ainxn = bi, где i = 1,m,
записать в виде –ai1(-x1) – ai2(-x2) - … - ain (-xn) = bi
и составить таблицу
то в этих случаях вместо ОЖИ пользуются МЖИ. Один шаг МЖИ с разрешающим элементом “-ars”, означает переход к новой таблице
: (-ars) которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями: 1) остальные элементы разрешающей строки остаются без изменения 2) остальные элементы разрешающего столбца меняют лишь свои знаки Рассмотрим систему
2X1 + 3X2 – 5X3 = 16 = b1, 3X1 - 2X2 + 4X3 = 36 = b2, 5X1 + 7X2 – 11X3 = 44 = b3.
Запишем ее в виде таблицы
и произведем один шаг МЖИ с разрешающим элементом “2”
: 2 Экстремумы линейной функции
Пусть рассматривается общая задача линейного программирования. Воснове вычислительных методов ЛП лежит следующая фундаментальная теорема. Теорема. Если задача линейного программирования имеет оптимальное решение (в ограниченной области всегда, а в неограниченной области в зависимости от ограниченности функции Z), то оно совпадает по крайней мере с одним из опорных решений системы ограничительных уравнений. Согласно этой теореме вместо исследования бесконечного множества допустимых решений с целью нахождения среди них искомого оптимального решения, необходимо исследовать лишь конечное число опорных решений. Данная теорема утверждает, что существует по крайней мере одно опорное оптимальное решение, однако, в задачах могут встретиться несколько опорных оптимальных решений (альтернативный оптимум). Следовательно, принципиальная схема решения задач линейного программирования следующая:
1. С помощью ЖИ найдем все опорные решения системы.
a11x1 + a12x2 + … + a1nxn = b1, ……................... ak1x1 + ak2x2 + … + aknxn = bk, ak+1,1x1 + ak+1,2x2 + … + ak+1nxn ≤ bk+1, ……................... am1x1 + am2x2 + … + amnxn ≤ bm.
2. Вычислим для каждого из них значение функции Z, определяемое соотношением.
Z = c1x1 + c2x2 + … + cnxn.
3. Выберем из них экстремальное Z.
Следует отметить, что может оказаться очень большое число опорных решений, поэтому нужно производить упорядоченный перебор опорных решений, добиваясь на каждом шаге монотонного изменения функции Z. Такая идея последовательного улучшения решения и заложена в основном вычислительном методе решения задач линейного программирования, получившим название симплексного метода.
Симплексный метод на основе полных таблиц
Постановка задачи об определении оптимального ассортимента продукции
Предприятие может производить два вида изделий А и В, располагая для их изготовления ограниченными ресурсами материала чугуна и стали соответственно в количествах 350 и 392 кг и оборудования в количестве 408 станко-часов. Данные, представленные в виде таблицы, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия А и В. Требуется определить сколько изделий А и В должно производить предприятие, чтобы достичь наибольшей прибыли.
Виды ресурсов |
Объем ресурсов
|
Затраты на одно изделие | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
А | В | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Чугун | 350 | 14 | 5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Сталь | 392 | 14 | 8 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Оборудование | 408 | 6 | 12 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Прибыль в руб. | 10 | 5 |
Введем искомые неизвестные Х1 и X2, обозначающие число изделий А и В, которые должно производить предприятие.
Тогда математически задачу можно сформулировать следующим образом.
Среди множества неотрицательных решений системы неравенств
14X1 + 5Х2 ≤ 350, (1.1)
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
найти такое решение, для которого функция
Z = 10 Х1 + 5 Х2
достигает наибольшего значения.
Геометрическое решение задачи
Прежде всего, построим область допустимых решений, соответствующую системе неравенств.
Для этого, заменив каждое из неравенств равенством
14Х1 + 5Х2 = 350, (1-я прямая),
14X1 + 8Х2 = 392, (2-я прямая),
6Х1 + 12Х2 = 408, (3-я прямая),
строим граничную линию. Учитывая, что Х1 ≥ 0 и Х2 ≥ 0, получаем заштрихованную часть плоскости, образующую многоугольник решений OABCD (рис.1).
Затем строим линию уровня 10Х1 + 5Х2 = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линейной функции.
Действительно
Z0 = 10X10 + 5Х20 = 10 * 0 + 5 * 0 = 0,
ZА = 10X1A + 5Х2A = 10 * 0 + 5 * 34 = 170,
ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 и т. д.
Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает min значение функции Z, а другая проходит через точку С и функция Z для нее принимает mах значение. Эти линии уровня называются опорными.
Рис. 1
Точка C образована первой и второй прямыми. Следовательно, решая систему уравнений
14Хl + 5Х2 = 350,
14Х1 + 8Х2 = 392,
найдем координаты точки C
Х1 = 20, Х2 = 14,
при этом Zmax = 10 * 20 + 5 * 14 = 270 руб.
Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изделий вида В.
Отыскание максимума линейной функции
В основе симплексного метода решения задач линейного программирования лежит с некоторыми дополнениями разобранный ранее метод последовательных исключений, представляющий собой совокупность удобных вычислительных алгоритмов, построенных на последовательном применении тождественных (симплексных) преобразований системы уравнений.
Добавляя к левой части неравенств
14X1 + 5Х2 ≤ 350,
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
некоторую неотрицательную величину Yj ≥ 0 (i = 1, 2, 3), (1.2)
называемую выравнивающей или базисной переменной, превратим их в уравнения:
14 | Х1 + 5Х2 + У1 | = 350, | ||
14 | Х1 + 8Х2 | + У2 | = 392, | |
6 | X1 + 12Х2 | + У3 | = 408, | |
-10 | X1 - 5Х2 | + Z = 0. | ||
(1.3)
При этом можно показать, что каждому решению системы неравенств (1.1) соответствует единственное решение системы уравнений (1.3) и неравенств (1.2) и наоборот.
Каждая из переменных Y1, У2, У3 входит только в одно уравнение и зависит от переменных Х1 и X2, которые мы называем свободными.
Системе (1.3) соответствует исходное допустимое базисное решение X1 = X2 = 0;
Y1 = 350; Y2 = 392; Y3 = 408 и Z = 0.
Выполняем первое тождественное преобразование системы уравнений (1.3). Выбираем разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z строке, ибо теоретически установлено, что при этом можно ожидать при прочих равных условиях большего увеличения функции Z. Правую часть уравнений делим на элементы разрешающего столбца и выбираем наименьшее положительное отношение, соответствующее разрешающей строке (уравнению). На пересечении выделенных столбца и строки стоит разрешающее число.
Первое уравнение делим на разрешающее число и выписываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):
X1 + | 5/14 | X2 + 1/4 Y1 = 25, | ||
| 3 | Х2 – Y1 + Y2 | = 42, | |
| 138/14 | X2 – 6/14 Y1 + У3 | = 258, | |
-20/14 | X2 + 10/14 Y1 | + Z = 250. | ||
(1.4)
Подобное тождественное преобразование, при котором выбор разрешающего числа производится по указанному правилу, будем называть симплексным преобразованием.
Таким образом, симплексное преобразование выполняется по следующему правилу:
1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z - строке.
2. Выбирается разрешающая строка, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца. На пересечении разрешающего столбца и разрешающей строки стоит разрешающее число.
3. Элементы разрешающей строки делятся на разрешающее число.
4. Вычисляются элементы всех остальных строк по формуле:
Новые эл-ты | = | Старые эл-ты |
_ | соответствующее число в разрешающей строке
| * | соответствующее число в разрешающем столбце | |||
разрешающее число
| |||||||||
| |||||||||
Из системы (1.4) находим второе допустимое базисное решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, которому соответствует новое увеличенное значение функции Z = 250.
Таким образом, процесс последовательных симплексных преобразований является процессом последовательного улучшения решения. При этом:
1. Если в Z - строке найдется хотя бы один отрицательный элемент и
а) в разрешающем столбце найдется хотя бы один положительный элемент, то можно улучшить решение;
б) если же разрешающий столбец не содержит положительных элементов, то функция Z неограниченно возрастает.
2. Если все элементы в Z - строке неотрицательны, то достигнуто оптимальное решение.
Это и есть достаточные условия существования оптимального плана решения.
В системе (1.4) коэффициент при Х2 в Z - строке отрицательный, поэтому второй столбец будет разрешающим. Находим, что вторая строка будет разрешающей. Далее производим симплексное преобразование системы (1.4) согласном указанному правилу:
X1 + 8/42 Y1 – 5/42 Y2 = 20,
X2 – 1/3 Y1 + 1/3 Y2 = 14,
20/7 Y1 – 23/7 Y2 + Y3 = 120,
10/42 Y1 + 20/42 Y2 + Z = 270, (1.5)
Так как в Z - строке все элементы неотрицательны, то данный план является оптимальным. При этом Yl = Y2 = 0; X1 = 20; Х2 = 14 и Zmax = 270.
Выполнение симплексных преобразований связано с кропотливыми и часто довольно громоздкими вычислениями. Эти вычисления можно в значительной степени упростить, используя для решения задач так называемые симплексные таблицы.
Каждое симплексное преобразование системы сводится к переходу от одной симплексной таблицы к другой.
Соответственно исходной системе уравнений (1.3) составляем первую симплекс-таблицу (табл. 1.1).
X1 | X2 | Y1 | Y2 | Y3 | контр. столбец | ||
Y1 | 350 | 14 | 5 | 1 | 0 | 0 | 370 |
Y2 | 392 | 14 | 8 | 0 | 1 | 0 | 415 |
Y3 | 408 | 6 | 12 | 0 | 0 | 1 | 427 |
Z | 0 | -10 | -5 | 0 | 0 | 0 | -15 |
Таблица 1.1
Первый столбец - это столбец базисных переменных, во втором столбце стоят свободные коэффициенты правой части уравнений (1.3), в первой строке располагаются все переменные, последний столбец - это контрольный столбец и коэффициенты в нем равны сумме всех коэффициентов по строке.
Из табл. 1.1 имеем первое допустимое решение системы (1.3) Х1 = Х2 = 0, Y1 = 350,
Y2 = 392, Y3 = 408, Z = 0, которое соответствует вершине О (0,0) многоугольника допустимых решений OABCD (рис.1).
Переход ко второй симплекс-таблице (табл. 1.2) выполняется согласно указанному в этом пункте правилу для симплексных преобразований систем уравнений, при этом разрешающая переменная Х1 идет в базис вместо разрешающей переменной Y1 Получаем табл. 1.2.
X1 | X2 | Y1 | Y2 | Y3 | контр. столбец | ||
X1 | 25 | 1 | 5/14 | 1/14 | 0 | 0 | 370/14 |
Y2 | 42 | 0 | 3 | -1 | 1 | 0 | 45 |
Y3 | 258 | 0 | 138/14 | -6/14 | 0 | 1 | 3758/14 |
Z | 250 | 0 | -20/14 | 10/14 | 0 | 0 | 3490/14 |
Таблица 1.2
После заполнения табл. 1.2 следует проверить правильность ее заполнения, для чего суммируем коэффициент по строкам и эта сумма должна быть равна коэффициентам, стоящим в соответствующих клетках контрольного столбца. Из табл. 1.2 второе допустимое решение будет Х1 = 25, Х2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250.
Нетрудно видеть, что эта таблица соответствует системе (1.4), а опорное решение
Х1 = 25, Х2 = 0 соответствует вершине D(25,0) многоугольника решений.
Так как в Z - строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. 1.3.
X1 | X2 | Y1 | Y2 | Y3 | контр. столбец | ||
X1 | 20 | 1 | 0 | 4/21 | -5/42 | 0 | 295/14 |
X2 | 14 | 0 | 1 | -1/3 | 1/3 | 0 | 15 |
Y3 | 120 | 0 | 0 | 20/7 | -23/7 | 1 | 844/7 |
Z | 270 | 0 | 0 | 5/21 | 10/21 | 0 | 1895/7 |
Таблица 1. 3
* Примечание. Для простоты вычислений следует помнить, что в новой таблице на месте элементов разрешающего столбца (кроме разрешающего элемента) стоят нули. Если в разрешающей строке стоят нули, то в новую таблицу соответствующие столбцы переносятся без изменения:
Так как в Z - строке нет отрицательных элементов, то данное решение будет оптимальным.
Табл. 1.3 соответствует системе уравнений (1.5) и оптимальному решению Х1 = 20,
Х2 = 14 и Zmax = 270 и вершине С (20,14) многоугольника допустимых решений OABCD.
Подобные удлиненные таблицы, содержащие в первой строке все переменные, благодаря наличию контрольного столбца позволяют контролировать правильность заполнения таблиц и избежать арифметических ошибок.
2019-12-29 | 176 | Обсуждений (0) |
5.00
из
|
Обсуждение в статье: Затраты на одно изделие |
Обсуждений еще не было, будьте первым... ↓↓↓ |
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы