. Алгоритм симплекс-метода
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
Решение:
I итерация:
х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:
Приведем целевую функциюк следующему виду:
На основе полученной задачи сформируем исходную симплекс-таблицу:
Таблица 5.3
Исходная симплекс-таблица
Оценочные отношения |
||||
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
6 этап: проверка оптимальности.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
Таблица 5.4
Исходная симплекс-таблица
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.
9.1. Преобразование разрешающего элемента.
Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:
Полученный результат вписываем в аналогичную клетку таблицы 5.5.
9.2. Преобразование разрешающей строки.
Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.
9.3. Преобразование разрешающей колонки.
Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.
9.4. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:
«х3 »: .
Аналогично преобразуются значения других клеток:
«х3 х1 »: ;
«х4
»: 
;
«х4 х1 »: ;
«х6
»: 
;
«х6 х1 »: ;
«»: 
;
«х1
»: 
.
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
II итерация:
1 этап: составление симплекс-таблицы.
Таблица 5.5
Симплекс-таблица II итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):
Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.6
Симплекс-таблица II итерации
Оценочные отношения |
||||
3/1=3 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.
III итерация
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.7
Симплекс-таблица III итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.8, минимальным является отношение, соответствующее строке «х4 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.8
Симплекс-таблица III итерации
Оценочные отношения |
||||
5/5=1 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.
IV итерация
1 этап: построение новой симплекс-таблицы.
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.9
Симплекс-таблица IV итерации
Оценочные отношения |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.9) нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
7 этап: проверка альтернативности решения.
Найденное решение является единственным, так как в строке целевой функции (таблица 5.9) нет нулевых элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.
Пример 5.2. Решить вышеприведенную задачу линейного программирования при условии, что целевая функция минимизируется:
Решение:
I итерация:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.
Размер: px
Начинать показ со страницы:
Транскрипт
1 Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Ecel ЗАДАНИЕ. Предприятие выпускает два вида продукции: Изделие и Изделие. На изготовление единицы Изделия требуется затратить a кг сырья первого типа, a кг сырья второго типа, a кг сырья третьего типа. На изготовление единицы Изделия требуется затратить a кг сырья первого типа, a кг сырья второго типа, a кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве b кг, b кг, b кг соответственно. Рыночная цена единицы Изделия составляет c тыс. руб., а единицы Изделия - c тыс.руб. Требуется:) построить экономико математическую модель задачи;) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс метода решения задачи линейного программирования. 4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL. РЕШЕНИЕ.) Математическая модель задачи. Переменные задачи В задаче требуется определить оптимальное число изделий каждого вида, обеспечивающее максимальную прибыль от их реализации, а значит, переменными задачи являются количество каждого вида изделий: количество изделий вида; количество изделий вида.
2 Целевая функция Критерием эффективности служит параметр прибыли, который должен стремиться к максимуму. Чтобы рассчитать величину прибыли от реализации изделий, необходимо знать: выпускаемое количество изделий каждого вида, т.е. и; прибыль от их реализации согласно условию, соответственно и тыс. руб. Таким образом, прибыль от реализации выпускаемых изделий вида равна тыс.руб., а от реализации изделий вида тыс.руб. Поэтому запишем ЦФ в виде суммы прибыли от продажи каждого из видов изделий: Z () = + Ограничения Возможное оптимальное количество изделий каждого вида и ограничивается следующими условиями: Заданными ресурсами -, и, которые используются на выпуск каждого вида изделия, не могут превышать общего запаса ресурсов; количество каждого вида изделия не может быть отрицательным. Запишем эти ограничения в математической форме: по расходу ресурса: по расходу ресурса: + 00, по расходу ресурса: + не отрицательность количества выпускаемых костюмов задаётся так:,). Таким образом, математическая модель этой задачи имеет вид Z () = ; + 00; + ; 0; 0. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ Так как переменные задачи и входят в целевую линейную функцию и ограничения задачи линейны, то соответствующая задача оптимизации задача линейного программирования. Построим в декартовой системе координат X OX многоугольник решений, или допустимых планов, который является пересечением полуплоскостей - решений каждого из неравенств системы ограничений.
3 (): Сначала строится разделяющая прямая + 7 = 60. Для этого находим две точки, через которые она проходит: Подставим точку (0;0) в неравенство (): верно, поэтому стрелки указывают на полуплоскость к нулю. (): Разделяющая прямая + 00, найдём точки: = Подставим точку (0;0) в неравенство (): верно, поэтому стрелки указывают на полуплоскость к нулю. (): +. Разделяющая прямая +, найдём точки: = 0 66,4 0 Подставим точку (0;0) в неравенство (): 0 - верно, поэтому стрелки указывают на полуплоскость к нулю. Находим многоугольник, в котором пересекаются, накладываются друг на друга все построенные полуплоскости. Многоугольник допустимых решений заштриховывается.
4 Построим градиент и линию уровня функции цели: Z(X) = + g(;). Градиент всегда изображается с началом в т.(0;0). Любая линия уровня перпендикулярна градиенту. Удобно построить линию уровня Z = 0, также проходящую через начало координат: + = 0. Перемещаем мысленно или с помощью линейки линию уровня так, чтобы найти угловые точки многоугольника допустимых планов, координаты которых доставляют максимальное значение функции цели. В данной задаче линия уровня перемещается в направлении за градиентом, поэтому её значения будут увеличиваться от линии к линии. Следовательно, в точке А будет наибольшее значение. Найдём координаты точки А, как точки пересечения разделяющих прямых: + + Второе уравнение умножим на (-): = 00 = + = 00 = 996 сложим уравнения 4
5 = 8 = 696 = = 8 = 4 Следовательно, A (8;4), Z (8;4) = = Ответ: изделия вида необходимо выпускать в количестве 8 единиц, а изделия вида в количестве 4 единицы. При этом прибыль от их реализации максимальная и составит 4660 тыс. руб.) СИМПЛЕКС МЕТОД Приводим задачу к каноническому виду, для этого в каждое неравенство вводим дополнительную переменную со знаком плюс:, 4,. Z () = = 60; = 00; + + = ; 0; 0. Дальнейшее решение будем вести в симплекс таблицах. Таблица Так как задача на нахождение максимального значения, то в индексной строке выбираем наибольшую по модулю отрицательную оценку это столбец с переменной (таблица). Выделяем его. Далее находим оценочные отношения, путём деления столбца С на столбец D, которые записываем в предпоследний столбец таблицы, из которых выбираем наименьшее из них это 66,4 третья строка. Выделяем её. В последнем столбце запишем пересчитывающие коэффициенты: 0,4; = 0,6 =, которые необходимы при пересчёте всех невыделенных элементов. Третью строку делим на. Из базиса выводим переменную,
6 при этом в базис вводим переменную. Все невыделенные элементы пересчитываем по методу Гаусса, например для первой строки: 60 0,4 = 47, 0,4 = 0 и так все элементы. В результате перейдём к таблице. Таблица Так как в индексной строке присутствует отрицательная оценка, план не оптимален. Требуется улучшение плана. Выделяем столбец с переменной. Далее находим оценочные отношения делением столбца С на столбец Е, среди которых наименьшее 4 - вторая строка. Выделяем её. Элементы строки делим на,4. Из базиса выводим переменную 4, при этом в базис вводим переменную. Получим таблицу. Таблица Так как в индексной строке все оценки положительные или равны нулю, план оптимален: Z (8;4) = 4660, ответ такой же как и при решении графическим методом. 4) ПРИМЕНЕНИЕ НАДСТРОЙКИ «ПОИСК РЕШЕНИЯ» MS EXCEL Для решения рассмотренной задачи в среде Ecel заполним ячейки исходными данными (в виде таблицы) и формулами математической модели. Ecel позволяет получить оптимальное решение без ограничения размерности системы неравенств и целевой функции. 6
7 Таблица в режиме чисел Таблица в режиме формул Здесь: В9:С9 результат (оптимальное количество изделий каждого вида); В6:С6 коэффициенты целевой функции; В0 значение целевой функции; В:С коэффициенты ограничений; D:D4 правая часть ограничений; B:B4 вычисляемые (фактические) значения левой части ограничений. Решим задачу с помощью команды меню Сервис / Поиск решения. Итак, делаем активной ячейку B0. Выполняем команду Сервис / Поиск решения. На экране появляется диалоговое окно Поиск решения. 7
8 В поле Установить целевую будет показана ссылка на активную ячейку, то есть на B0. Причём эта ссылка абсолютная (мы видим $B$0). В секции Равной: устанавливаем переключатель максимальному значению. Можно задать не только максимальное/минимальное значения, но и любую произвольную величину, введя её в специальное поле значению в секции Равной:. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения. В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение: указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем для следующего ограничения. После ввода всех ограничений следует щёлкнуть кнопку ОК. Так как все переменные несут условие не отрицательности, то их положительность задаём через кнопку Параметры в окне диалога Поиск решения. После щелчка на ней, на экране окно Параметры поиска решения. 8
9 Устанавливаем флажки Линейная модель и Неотрицательные значения, соглашаясь с остальными установками по умолчанию. Щёлкаем на кнопке ОК. После этого произойдёт переключение в окно Поиск решения, в котором необходимо щёлкнуть кнопку Выполнить для решения поставленной задачи. Ecel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения. Если вычисления оказались успешными, Ecel предъявит следующее окно итогов. Их можно сохранить или отказаться (Восстановить исходные значения). Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность. После найденного решения, в ячейках В9:С9 количество изделий каждого вида. Покажем это. появится оптимальное 9
10 При сохранении отчёта выбрали вид отчёта Отчёт по результатам. Из отчёта видно, что ресурс не используется полностью на 0 кг, а ресурсы и используются полностью. Получили оптимальный план, при котором изделий первого вида необходимо выпустить в количестве 8 шт., а изделий второго вида в количестве 4 шт. При этом прибыль от их реализации максимальная и составит 4660 тыс.руб. 0
Линейное программирование Задача 1... 2 Задача 2... 3 Задача 3... 5 Задача 4... 7 Задача 5... 10 Задача 6... 12 Задача 7... 15 Задача 8... 19 Задача 9... 21 Задача 10... 24 Задача 11... 27 Задача 1. Составить
Задача распределения ресурсов предприятия Содержательная постановка задачи Фабрика выпускает сумки: женские, мужские, дорожные. Данные о материалах, используемых для производства сумок и месячный запас
1 Лабораторная работа 3 Решение задач. Подбор параметров, поиск решения 1. Реализация математической модели в Excel Математическая модель это описание состояния поведения некоторой реальной системы (объекта,
Решить задачу линейного программирования, где 3x12x2 8 x14x2 10 x1 0 x 2 0 LX3x14x2 max а) геометрическим способом, б) перебором базисных решений, в) симплекс-методом. Графическое решение задачи L X 3x14
ЛАБОРАТОРНАЯ РАБОТА СРЕДСТВА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ КАК ФУНКЦИИ EXCEL Команда Подбор параметра Задание 1. Рассмотрим задачу, составленную на основании задачи по использованию функции ЧПС. Вас просят
Линейная производственная задача. Предприятие может выпускать четыре вида продукции, используя при этом три вида ресурсов. Известны технологическая матрица A затрат 7 8 ресурсов на производство единицы
1 Симплексный метод решения ЗЛП Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений). Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем
Линейная алгебра 08.12.2012 Линейные модели в экономике Линейное программирование Линейная алгебра (лекция 13) 08.12.2012 2 / 25 Задача линейного программирования: F (x 1, x 2,..., x n) = n c j x j max(min),
) Задача о планировании производства. Производственному участку может быть запланировано к изготовлению на определённый плановый период времени два вида изделий: A и B. На производство единицы изделия
Контрольная работа Задача 5 На предприятии имеется сырье видов 1, 2, 3 Из него можно изготавливать изделия типов А и В Пусть запасы видов сырья на предприятии составляют b 1, b 2, b 3 ед соответственно,
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ Московский государственный университет путей сообщения Императора
Задача. Решить графически ma F Находим точки пересечения прямых определяющих неравенства. Отсюда Точка пересечения не принадлежит области. Построим область допустимых решений. Построим вектор направления
ВАРИАНТ 5 Для изготовления различных изделий А, В, С предприятие использует различных вида сырья. Используя данные таблицы: Вид сырья Нормы затрат сырья Кол-во сырья А В С I II III 18 6 5 15 4 12 8 540
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ имени
Лабораторная работа 4 Тема работы: Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры Поиск решения Microsoft Excel. Цель работы: Научиться использовать
АНО ВПО «Региональный финансово-экономический институт» ИТОГОВЫЙ ЭКЗАМЕН по учебной дисциплине «Методы оптимальных решений» http://elearning.rfei.ru 1 Уважаемые студенты! Итоговым контролем изученного
УДК 518.85 НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДРОБНО-ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В.В. Листопад Национальный университет пищевых технологий, г. Киев, Украина, [email protected] В докладе приведены три способа
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
Практическая работа 8 Решение задач линейного программирования графическим методом. Цель работы: Научиться решать задачи линейного программирования графическим методом. Содержание работы: Основные понятия.
Князева А., Лыкова Н.П. ГОУ ВПО «Российский государственный гуманитарный университет» Филиал в г. Самаре ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ РЕШЕНИЕ С ПОМОЩЬЮ MS EXCEL Временем рождения линейного
ЗАДАНИЕ ПРАКТИЧЕСКОЙ РАБОТЫ 4 И ПРАКТИЧЕСКОЙ РАБОТЫ 5 Задачи линейной оптимизации Построение экономико-математических моделей (ЭММ). Решение задач линейной оптимизации с использованием информационных технологий.
Лабораторная работа Тема: Построение графиков функций Цель работы: Изучение графических возможностей пакета Ms Ecel Приобретение навыков построения графика функции на плоскости средствами пакета Задание
Рассмотрим первый способ решения СЛУ по правилу Крамера для системы трех уравнений с тремя неизвестными: Ответ рассчитывается по формулам Крамера: D, D1, D2, D3 это определители Определителем третьего
8. Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю): Общие сведения 1. Кафедра М и ММЭ 2. Направление подготовки 01.03.02 (010400.62) Прикладная математика
АНАЛИЗ ДАННЫХ В MS EXCEL Гедранович Валентина Васильевна 27 июня 2012 г. Аннотация Глава 11 из УМК: Гедранович, В.В. Основы компьютерных информационных технологий: учеб.-метод. комплекс / В.В. Гедранович,
ПРИМЕНЕНИЕ MS EXCEL ПРИ РЕШЕНИИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Сулейманова И.И., Сагадеева Э.Ф. ФГБОУ ВО Башкирский ГАУ MS EXCEL APPLICATION IN SOLVING LINEAR PROGRAMMING PROBLEMS Suleymanova I.I., Sagadeeva
Лекции Глава Функции нескольких переменных Основные понятия Некоторые функции многих переменных хорошо знакомы Приведем несколько примеров Для вычисления площади треугольника известна формула Герона S
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра ИНФОРМАТИКИ И МЕТОДИКИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Государственное образовательное учреждение высшего профессионального образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» Институт экономики
Федеральное агентство железнодорожного транспорта Уральский государственный университет путей сообщения Кафедра высшей математики П. И. Гниломедов И. Н. Пирогова П. П. Скачков ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Практическая работа 13 Тема: ЗАДАЧИ ОПТИМИЗАЦИИ (ПОИСК РЕШЕНИЯ) В MICROSOFT EXCEL Цель занятия. Изучение технологии поиска решения для задач оптимизации (минимизации, максимизации). Задание 13.1. Минимизация
Глава 8 Уравнение линии в пространстве Как на плоскости, так и в пространстве, любая линия может быть определена как совокупность точек, координаты которых в некоторой выбранной в пространстве системе
Тема. Определители. Решение систем линейных уравнений по формулам Крамера При умножении определителя на число на это число умножаются все элементы определителя первые две строки все элементы какой-нибудь
ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Отделение корней Пусть дано уравнение f (0, () где функция f (C[ a; Определение Число f () 0 x называется корнем уравнения () или нулем функции f (,
8 Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю): Общие сведения 1 Кафедра Математики и математических методов в экономике 2 Направление подготовки 380301
УЧЕБНОЕ ИЗДАНИЕ В ЭЛЕКТРОННОМ ВИДЕ С.Ю. Белецкая, В.Н. Фролов МЕТОДИЧЕСКИЕ УКАЗАНИЯ к практическим занятиям по дисциплине «Методы оптимизации и математическое программирование» для аспирантов направления
Анализ «Что если» СПбГУ, ЭФ каф. ИСЭ Порошин А.Н. Анализ "что-если" Анализ "что-если" это процесс поиска ответов, например, на следующие вопросы: "Что будет, если процентная ставка кредита поднимется с
ФОНД ОЦЕНОЧНЫХ СРЕДСТВ ДЛЯ ПРОВЕДЕНИЯ ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ) Общие сведения. Кафедра Информатики, вычислительной техники и информационной безопасности. Направление
Вычисляемые поля и вычисляемые элементы в Excel 2013 В процессе анализа данных с использованием сводных таблиц часто возникает потребность во включении в отчет значений, полученных в результате вычислений,
18.1. Общая формулировка проблемы оптимизации Предположим, что мы стоим на склоне холма и должны найти самую нижнюю точку: это наша целевая функция. Предполагается, что есть несколько заборов, которые
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский ядерный университет
Ускоренное освоение методов линейного программирования в режиме диалога с программой, выполняющей арифметические операции Богомазов Р. Ю., Беседин Н. Т. Юго-западный государственный университет 1. Цель
1. Введение Лабораторная работа 3 Подбор параметров При решении различных задач часто приходится заниматься проблемой подбора одного значения путем изменения другого. Для этой цели весьма эффективно используется
Г р а ф и ч е с кое решение систем уравнений Аналитическая геометрия изучает геометрические объекты по их уравнениям. MS Excel предоставляет широкие возможности визуализации различных уравнений. В Excel
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Федеральное Государственное Бюджетное Образовательное Учреждение Высшего Профессионального Образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное автономное образовательное учреждение высшего профессионального образования «Казанский (Приволжский) федеральный университет»
Вопрос. Неравенства, система линейных неравенств Рассмотрим выражения, которые содержат знак неравенства и переменную:. >, - +х -это линейные неравенств с одной переменной х.. 0 - квадратное неравенство.
«MICROSOFT OFFICE EXCEL» Дисциплина «Программные средства профессиональной деятельности» Лектор: Ст. преподаватель кафедры «Электропривода и электрооборудования» Воронина Наталья Алексеевна Назначение
В программе Calc предусмотрена возможность присвоения ячейкам и диапазонам ячеек специальных имен, то есть кратких осмысленных обозначений, которые могут участвовать в создании формул вместо адресов ячеек,
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Ивановский государственный политехнический университет» Институт
ЛАБОРАТОРНЫЕ РАБОТЫ ПО MS EXCEL 2007 ЛАБОРАТОРНАЯ РАБОТА 1.... 1 ЛАБОРАТОРНАЯ РАБОТА 2... 3 ЛАБОРАТОРНАЯ РАБОТА 3... 4 ЛАБОРАТОРНАЯ РАБОТА 4... 7 ЛАБОРАТОРНАЯ РАБОТА 5... 8 ЛАБОРАТОРНАЯ РАБОТА 6... 10
Раздел 7. УРАВНЕНИЯ ПРЯМОЙ И ПЛОСКОСТИ В ПРОСТРАНСТВЕ Лекция 4. Тема: Уравнения прямой и плоскости в пространстве 7. Система координат в пространстве Рассмотрим прямоугольную декартову систему координат
4 Методы нахождения первоначальной крайней точки 4. Переход к решению двойственной задачи Рассмотрим метод решения задач линейного программирования путем перехода к двойственной задаче и решения полученной
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА «ИНФОРМАТИКА» РЕАЛИЗАЦИЯ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ В СРЕДЕ EXCEL Методические указания к проведению лабораторных
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
NovaInfo.Ru - 58, 2017 г. Физико-математические науки 1 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛП Голубцова Владислава Олеговна Графический метод довольно прост и нагляден для решения задач линейного программирования
Кафедра математики и информатики Элементы высшей математики Учебно-методический комплекс для студентов СПО, обучающихся с применением дистанционных технологий Модуль 6 Элементы линейного программирования
Работа со списками в MS EXCEL Цель: Приобрести навыки поиска и агрегирования данных в списке. Краткая теория Компьютерные информационные технологии широко используются для анализа данных и подготовку управленческих
При каких значениях ранг матрицы равен двум? Решение: Ранг матрицы равен порядку базисного минора. Поскольку требуется, чтобы ранг матрицы был равен двум, то базисным должен быть какой-либо минор второго
Образцы базовых задач по ЛА Метод Гаусса Определенные системы линейных уравнений Решите систему линейных уравнений методом Гаусса x 6 y 6 8, 6 x 6 y 6 Решите систему линейных уравнений методом Гаусса 6
Практическая работа 3.7. Использование мастера функций MS Excel. Построение диаграмм Цель работы. Выполнив эту работу, Вы научитесь: вводить формулы в ячейки таблицы; использовать Мастер функций MS Excel
Глава 8 Базы данных в OpenOffice.org Calc В этой главе мы изучим возможности пакета OpenOffice.org Calc при работе с базами данных. Довольно часто возникает необходимость хранить и обрабатывать данные
ОБРАЗЕЦ ОФОРМЛЕНИЯ ОТЧЕТА Разработчик доц., к.ф.-м.н. Манита Л.А. Московский институт электроники и математики НИУ ВШЭ Отчет студентов группы МЭ-63 Воробьянинова Ипполита Матвеевича, Изнуренкова Авессалома
Число газет Лабораторно-практическая работа ТЕМА: «MS Excel. Построения, форматирования и редактирования диаграмм, графиков». ЦЕЛЬ УРОКА: научиться строить, форматировать и редактировать диаграммы, графики.
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНО ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ Кафедра нелинейного анализа и аналитической экономики В. И. БАХТИН, И. А. ИВАНИШКО, А. В. ЛЕБЕДЕВ, О. И. ПИНДРИК ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем
Урок 1. Решение задачи линейного программирования в Excel с помощью надстройки "Поиск решения"
Экономико-математические методы и модели. Задача распределения ресурсов. Классический пример и решения задачи линейного программирование. Описание как пользоваться надстройкой Поиск решения в Excel. Условие задачи здесь - , еще примеры решения задач по ЭМММ -#ЭМММ #Excel #Матпрограммирование #ПоискРешения #Easyhelp
Решение задачи линейного программирования при помощи надстройки Поиск решения
Использование надстройки Поиск решения для решения задач линейного программирования. Поставьте класс, если видео оказалось Вам полезно.Простая задача линейного программирования №2. Симплекс-метод для поиска максимума.
Решение простой задачи линейного программирования симплекс-методом для поиска максимума. Для более детального пояснения доступны субтитры.
.
Простая задача линейного программирования №1. Симплекс-метод для поиска минимума.
Решение простой задачи линейного программирования симплекс-методом для поиска минимума. Для дополнительного пояснения доступны субтитры.
- Простая задача линейного программирования №3. Симплекс-метод для поиска минимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений
Лекция 2: Задача линейного программирования. Задача о ресурсах
Рассматривается решение задачи линейного программирования симплекс-методом.Лекция и тесты в НОУ ИНТУИТ
Линейное программирование
Решение задачи линейного программирования с помощью Поиск решения MS ExcelТекстовый материал на сайте находится по адресу:
Урок 2. Решение двойственной задачи линейного программирования в Excel
Анализ устойчивости для прямой и двойственной задач линейного программирования в Excel. Условие задачи смотрите здесь - , еще примеры решений задач здесь -#Excel #матпрограммирование #easyhelp
Симплекс-метод Excel VBA (Решение задачи линейного программирования с помощью макросов)
Демонстрация работы макроса в Excel. Решение задачи линейного программирования Симплекс-методом.Заказать макрос - [email protected]
Решение лабораторных работ в Excel на заказ
Симплексный метод решения задач линейного програмирования
линейное программирование. Симплексная таблица. Разрешающий элемент. Разрешающая строка. Разрешающий столбец. Симплексное отношениеГрафический метод решения задач оптимизации.
Программа, реализующая симплекс-метод
Программа доступна по ссылке ниже:Решение транспортной задачи в Excel с помощью надстройки "Поиск решения"
Задача линейного программирования. Транспортная задача. Решение в Excel, анализ устойчивости. Условие задачи здесь - , еще примеры решения задач по мат.программированию здесь -#excel #матпрограммирование #ТранспортнаяЗадача #ЛинейноеПрограммирование #ПоискРешения #easyhelp #АнализУстойчивости
Двойственный метод
Методы оптимизации 12. Линейное программирование, симплекс-метод
Вирішуємо симплекс-метод вручну
Вирішуємо симплекс-метод вручнуПростая задача линейного программирования №3. Симплекс-метод для поиска минимума.
Очень подробное решение простой задачи линейного программирования симплекс-методом для поиска минимума.Простая задача линейного программирования №1. Симплекс-метод для поиска минимума.
- Простая задача линейного программирования №2. Симплекс-метод для поиска максимума.
- Решение задачи линейного программирования алгоритмом двойственного симплекс-метода
- Решения прямой, двойственной задач ЛП, построение двойственной задачи ЛП.
- Решение задачи линейного программирования с неоднотипными неравенствами симплекс-методом
- Задача линейного программирования с системой уравнений
Решение задачи линейного программирования графическим методом
Построив в предыдущем видеоуроке модель задачи линейного программирования, необходимо найти ее решение. Одним из самых распространенных методов оптимизации является графический метод. Он может использоваться, если число неизвестных переменных Х не превышает двух. К достоинствам метода относится его простота, к недостаткам - точность полученного решения зависит от того, насколько правильно мы соблюдали масштаб при построении. Наш видеоурок научит вас этому.Если данное видео принесло вам реальную пользу и вы хотите отблагодарить автора:
WMR: R370550256930
WMZ: Z939960413056
В нашей подборке вы можете найти больше видеоуроков по работе с электронными таблицами Microsoft Excel:
Еще больше других обучающих видеоуроков вы сможете найти на нашем сайте:
Решение задач линейного программирование с помощью Excel
Задачи оптимизации, задачи линейного программирования, динамическое программирование - решение с помощью электронных таблицОтправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Решение задачи с помощью Excel и симплекс-методом
Задача (распределительная)
Симплекс-метод
Решение задачи с помощью Excel
Задача (распределительная)
Задача 1 (распределительная)
На предприятии 4 вида продукции могут вырабатываться на 3 отдельных взаимозаменяемых машинах.
Известны:
· Производственное задание по выпуску продукции разных видов в планируемом периоде
· Фонд эффективного рабочего времени оборудования в планируемом периоде - ;
· Нормы затрат машинного времени на изготовление единицы продукции - ;
· Прибыль в руб. от реализации единицы продукции, выработанной на том или ином оборудовании - .
Исходная информация отображается в таблице следующей формы.
Таблица 1. Исходные данные
|
Фонд эф. раб. врем. - |
Нормы затрат врем. на ед. продукции - прибыль на ед. продукции - |
||||
В задаче требуется найти план распределения производственного задания по выпуску продукции между исполнителями
при котором задание было бы выполнено с максимальной суммарной прибылью от реализации продукции.
РЕШЕНИЕ
Разработка экономико - математической модели.
Искомые переменные - характеризуют объём выпуска й продукции м исполнителем.
Тогда матрица искомых переменных
характеризует план распределения производственного задания по выпуску продукции между исполнителями.
Целевая функция
характеризующая суммарную прибыль от реализации всей продукции, должна быть максимизирована.
Ограничения по наличию и использованию эффективного рабочего времени исполнителей примут вид системы линейных неравенств (2):
Эта система ограничений характеризует условие, что суммарные затраты эффективного рабочего времени каждым исполнителем в планируемом периоде на выпуск всех видов продукции не должны превышать фонда времени. Таким образом, в результате решения задачи каждый исполнитель получит своё задание, исходя из его возможностей. Если в решении задачи какая - то уравновешивающая переменная и примет значение, - она будет характеризовать недоиспользованное эффективное рабочее время у того или иного исполнителя, которое в производственных условиях может быть использовано на выпуск продукции сверх задания.
Следующий блок ограничений должен отражать условие обязательного выполнения общего производственного задания по выпуску продукции по видам и будет представлен системой линейных уравнений (3):
Условие не отрицательности переменных:
Приведём задачу к каноническому виду, для этого в неравенства (2) добавим переменные, а в равенства (3) добавим 4 искусственных базиса. В результате запишем математическую модель задачи в каноническом виде:
Симплекс-метод
Решим данную задачу симплекс - методом, заполнив таблицу. Решение проходит за несколько итераций. Покажем это.
Таблица 1
В самой верхней строке таблицы заносятся коэффициенты целевой функции, вторая строка - это наименование всех неизвестных, входящих в симплексные уравнения. В первый столбец слева записывают коэффициенты, целевой функции, которые соответствуют базисным неизвестным, вошедшим в исходную программу (записанным в столбце). Следующий, третий по счёту, столбец в первой симплексной таблице - заполняется значениями базисных неизвестных. Далее идут столбцы, которые представляют векторы условий. Количество их равно 19. В следующем, первым по счёту после матрицы условий столбце - записываются суммы всех элементов по строкам. В столбце записываются частные от деления элементов итогового столбца В на элементы некоторого столбца, матрицы условий. Так как у нас есть искусственный базис, то в индексной строке будет вести два подсчёта, в первой из них, учитывая переменные, а во втором только искусственный базис. Так как у нас задача максимизации, то необходимо выводить из базиса искусственные базисы. В индексной второй строке выбираем наибольшую положительную оценку. У нас - это первый столбец. Найдём оценочные отношения
и. Из этих отношений выбираем наименьшее, у нас это четвёртая строка, для неё оценочное отношение равно 1300. Выделяем строку. Последний столбец - это коэффициент, на который умножается каждый элемент строки при пересчёте. Он получается делением элементов выделенного столбца на ключевой элемент, который находится на пересечении выделенного столбца и строки, у нас это 1. Пересчёт делаем для всех невыделенных элементов, который осуществляется следующим образом: от пересчитываемого элемента вычитаем элемент ключевой строки, умноженный на пересчитываемый коэффициент строки: и так все элементы. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Последние две строки - индексные строки, где пересчитываются значения целевой функции, а также вся индексная строка, когда все элементы будут положительными или нулевыми - задача будут решена.
Покажем это.
Таблица 2
Выделим столбец с переменной. Находим оценочные отношения, из которых выбираем наименьшее - это 550. Из базиса выводим искусственную переменную, при этом в базис вводим переменную. Когда выводится искусственный базис из базиса, соответствующий столбец убираем.
Таблица 3
Выделим столбец. Наименьшее оценочное отношение 600, находится в шестой строке. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Таблица 4
Выделим столбец с переменной. Наименьшее оценочное отношение 28,57, находится в первой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 5
Выделим столбец с переменной. Наименьшее оценочное отношение 407,7, находится в третьей строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 6
Выделим столбец с переменной. Наименьшее оценочное отношение 344,3, находится в седьмой строке. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Таблица 7
Выделим столбец с переменной. Наименьшее оценочное отношение 3,273, находится во второй строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 8
Выделим столбец с переменной. Наименьшее оценочное отношение 465, находится в седьмой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 9
Выделим столбец с переменной. Наименьшее оценочное отношение 109, находится в третьей строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 10
Выделим столбец с переменной. Наименьшее оценочное отношение 10, находится в первой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 11
Выделим столбец с переменной. Наименьшее оценочное отношение 147, находится во второй строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 12
Выделим столбец с переменной. Наименьшее оценочное отношение 367, находится в пятой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 13
Выделим столбец с переменной. Наименьшее оценочное отношение 128, находится в четвёртой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 14
Так как в индексной строке нет отрицательных оценок, получен оптимальный план, при котором объём выпуска продукции представлен матрицей
при этом прибыль максимальная и составляет 17275,31 руб.
Решение задачи с помощью Excel
Математическую модель задачи необходимо перенести в ЭТ EXCEL. Для этого:
· Продумать организацию исходных данных модели (коэффициенты целевой функции и ограничения), снабдив понятными названиями.
· Зарезервировать в отдельных ячейках независимые переменные математической модели.
· В одной из ячеек создать формулу, определяющую целевую функцию.
· Выбрать ячейки и поместить в них формулы, соответствующие левым частям ограничений.
· Войти в пункт меню "Поиск решения", ввести необходимые данные и получить оптимальное решение задачи.
· Проанализировать полученное решение и отчёты.
Рассмотрим последовательность действий по реализации этих этапов решения задачи с помощью EXCEL.
Создадим таблицу для ввода исходных данных.
В созданную форму введём исходные данные.
Коэффициенты целевой функции, выражающие прибыль, от производства единицы продукции каждого вида (единичная прибыль), записаны в ячейки В6:M6.
Коэффициенты ресурсных ограничений, определяющие потребность в каждом из видов ресурсов для производства единицы продукции, размещены в ячейках В9:M15. В ячейках P9:P15 записаны правые части ограничений на ресурсы. Для независимых переменных задачи - искомых объёмов производства продукции зарезервированы ячейки В3:M3.
В ячейку N7 вводим формулу для целевой функции, применив команду вставки функции СУММПРОИЗВ:
А также заполняем ограничения правой части.
После этого можно приступать к поиску решения. Для решения оптимизационных задач в EXCEL используется команда ПОИСК РЕШЕНИЯ меню СЕРВИС.
Эта команда оперирует с тремя основными компонентами построенной в ЭТ оптимизируемой модели:
· Ячейкой, содержащей целевую функцию задачи.
· Изменяемыми ячейками, содержащими независимые переменные.
· Ячейками, содержащими левые части ограничений на имеющиеся ресурсы, а также простые ограничения на независимые переменные.
Рассмотрим последовательность ввода этих компонентов.
Курсор в ячейку N7 и команда СЕРВИС - Поиск решения. На экране появится диалоговое окно.
В окне заполняем поле Установить целевую ячейку, в котором должен стоять адрес $N$7. Далее устанавливаем кнопку на поиск максимального значения. В поле Изменяя ячейки введём адреса искомых переменных $B3:$M3. Затем следует ввести ограничения, путём кнопки Добавить.
Теперь, когда все ограничения для поиска оптимального решения заданы можем нажать кнопку:
После этого получим решение задачи.
Если вычисления оказались успешными, после завершения поиска решения значения будут вставлены в таблицу, а также можно указать Тип отчёта - Результаты, в результате которого можем получить следующий отчёт. рабочий время оборудование прибыль
Следовательно, решение в EXCEL такое же, как и при СИМПЛЕКС методе, а это значит, что рассматриваемая задача, решена, верно.
Размещено на Allbest.ru
...Подобные документы
Определение оптимального объема выпускаемой продукции математическим методом, симплекс-методом и с помощью Excel. Решение задачи по оптимальному распределению инвестиций с использованием прикладной программы Excel. Составление оптимальной схемы перевозок.
курсовая работа , добавлен 10.09.2012
Планирование прибыли при производстве двух видов топлива. Составление оптимального плана выпуска продукции для получения максимальной прибыли от ее реализации. Определение опорного плана перевозок грузов методом минимальной стоимости и с помощью Excel.
контрольная работа , добавлен 12.11.2014
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа , добавлен 21.03.2012
Определение с помощью симплекс-метода плана выпуска продукции для получения максимальной прибыли, чтобы сырьё II вида было израсходовано полностью. Решение задач линейного программирования средствами табличного процессора Excel, составление алгоритма.
курсовая работа , добавлен 30.09.2013
Исследование математико-экономической модели компании с целью выработки оптимального решения по выпуску продукции для получения максимальной прибыли и минимизации затрат с помощью методов оптимизации и программы MS Excel и инструментального пакета Matlab.
дипломная работа , добавлен 15.06.2014
Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа , добавлен 21.11.2013
Определение количества и вида тракторных и автомобильных глушителей, которые следует изготовить предприятию, чтобы прибыль была максимальной. Решение задачи линейного программирования графическим и симплекс-методом, с помощью табличного редактора Excel.
курсовая работа , добавлен 09.04.2013
Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа , добавлен 04.02.2011
Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат , добавлен 21.08.2008
Определение количества закупаемого сырья на выпуск продукции по месяцам, в течении года и за год в целом. Алгоритм необходимых действий, представление результатов в графическом виде. Решение задачи в табличном процессоре Excel и с помощью средств VBA.
Для решения задач линейного программирования симплекс-методом в среде MS Excel заполняются ячейки исходными данными в режиме чисел и формулами математической модели.
MS Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств целевой функции.
Решим задачу о выпускаемых изделиях симплекс-методом применяя надстройку «Поиск решения» в MS Excel.
1. Заполните таблицу Excel в режиме чисел (рис.1)
2. Заполните таблицу Excel в режиме формул (рис.2)
Рис.1 Таблица в режиме чисел
Рис.1 Таблица в режиме формул
Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);
В6:С6 – коэффициенты целевой функции;
В10 – значение целевой функции;
В3:С5 – коэффициенты ограничений;
D12:D14 – правая часть ограничений;
B12:B14 – вычисляемые (фактические) значения левой части ограничений.
Решим задачу с помощью команды Данные/Поиск решения. На экране появляется диалоговое окно Поиск решения.
В поле Установить целевую функция будет показана ссылка на активную ячейку, т.е. на В10. Причем эта ссылка абсолютная. В секции Равной устанавливаем переключатель Максимальному (минимальному) значению в зависимости от целевой функции. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения.
В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем до следующего ограничения. После ввода всех ограничений нажимаем ОК.
Так как все переменные несут условия неотрицательности, то их положительность задается через кнопку Параметры в окне диалога Поиск решения. После щелчка по ней, на экране окно Параметры поиска решения.
Устанавливаем флажок Сделать переменные без ограничений неотрицательными и выбрать Метод решения Поиск решения линеных задач симплекс-методом. Щёлкаем на кнопке Найти решение.
Excel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения.
Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться. Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.
После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида.
При сохранении отчета выберите – Отчет по результатам (рис.3).
Из отчета видно, что ресурс 1 не используется полностью на 150 кг, а ресурс 2 и 3 используется полностью.
В результате получен оптимальный план, при котором изделий 1 вида необходимо выпустить в количестве 58 шт., а изделий 2 вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составляет 4660 тыс.руб.
Рис.3 Отчет по результатам
1. Со станции формирования ежедневно отправляются пассажирские и скорые поезда, составленные из плацкартных, купейных и мягких вагонов. Число мест в плацкартном вагоне – 54, в купейном – 36, в мягком – 18. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.
Решение транспортных задач
Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.
| b 1 | b 2 | … | b k | … | b g | |
| a 1 | } Больше информации по теме
|
