Как решить задачу симплекс методом в excel

Skip to content

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:

Если данная команда отсутствует в списке, необходимо выполнить команду Сервис / Надстройки

Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.

MS Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:

1. Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях.
2. Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
3. Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.

Пример. В библиотеке работают 6 пожилых уборщиц. Каждая из них по своим физическим возможностям и состоянию здоровья может выполнять только определенные виды работ, причем с определенной производительностью. Площадь каждой из работ известна. Нужно добиться минимума времени на уборку помещений.

Пример.На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов.

Для упрощения процесса вычислений при решении ЗЛП симплекс-методом можно использовать Microsoft Excel.

Найдем решение нашей задачи симплекс-методом с помощью Microsoft Excel.

Запустите Excel и подготовьте начальную симплекс таблицу по образцу:

Вычислим значение и запишем результат в ячейку D7. Известно, что значение в начальной симплекс таблице определяется по формуле:

Для вычисления скалярного произведения двух векторов используется функция

СУММПРОИЗВ(массив1, [массив2], [массив3]. ),

В ячейку D7 вводится формула, вычисляющая значение :

Для вычисления оценок используется формула .

Выделите ячейку D7 и введите формулу:

Аналогично вычислите значения других оценок.

Определим разрешающий столбец – столбец с наибольшей по модулю отрицательной оценкой и найдем отношение элементов столбца к положительным элементам выбранного столбца для определения разрешающей строки. Для этого выделите ячейку K4 и введите формулу:

Скопируйте формулу на диапазон K4 : K6

Таким образом, разрешающий столбец – столбец и разрешающая строка –

Создайте вторую симплекс-таблицу (скопируйте предыдущую и удалите все ненужно). Произведите замену в базисе вектора (разрешающий столбец) на вектор (разрешающая строка):

Выделите диапазон D12:I15 и укажите смените формат числовых данных на дробный

Вычислите новые элементы разрешающей строки: разделить элементы разрешающей строки на разрешающий элемент.

В ячейку D14 введите формулу

Скопируйте формулу на диапазон E14 : I14:

В ячейку D12 введите формулу: =D14*(-$F$4)+D4 Скопируйте формулу на диапазон E12:I12. В ячейку D13 введите формулу: =D14*(-$F$5)+D5 Скопируйте формулу на диапазон E13:I13. В ячейку D15 введите формулу: =D14*(-$F$5)+D5 Скопируйте формулу на диапазон E15:I15.

Так как строка оценок содержит отрицательное число, и соответствующий столбец содержит положительные числа, то план можно улучшить.

Выбираем разрешающую строку и разрешающий столбец:

Строим новую симплекс-таблицу и заменяем вектор (разрешающая строка) на вектор (разрешающий столбец). Заполняем таблицу аналогично предыдущей итерации:

Так как строка оценок не содержит отрицательных значений, то полученный план оптимален и имеет вид:

при плане

Ответ: при плане

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9622 — | 7515 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Для решения задач линейного программирования симплекс-методом в среде 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. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.

Решение транспортных задач

Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.

Если закрытая модель транспортной задачи

Переменные должны удовлетворять условиям

Суммарные затраты на перевозки

Решение такой задачи разбивается на два этапа:

1. Определение опорного (базисного) решения;

2. Построение последовательных итераций, т.е. приближение к оптимальному решению.

Для каждого из этих этапов существует несколько методов.

Для построения опорного решения чаще всего используют метод «северо-западного угла» и метод минимальных тарифов.

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.

Папиллярные узоры пальцев рук — маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

Цель
работы.

Освоение
технологии решения задач линейного
программирования симплекс-методом в
табличном процессоре Excel.

Содержание
лабораторной работы.

Дана
задача линейного программирования.
Требуется найти решение ЗЛП в табличном
процессоре EXCEL
симплекс – методом.

Задание
на лабораторную работу.

Вариант
6.

Задача:

На
арендном предприятии для изготовления
двух типов кабеля Аи В выполняется пять
технологических операций. Нормы затрат
времени на изготовление1000 м кабеля
каждого вида по каждой операции, доход
от реализации 1000 м кабеля, а также общий
фонд рабочего времени по каждой операции
приведены в табл. 4.5. Определить оптимальный
выпуск продукции, при котором будет
получен наибольший доход.

Таблица
1.

Построим
модель:

→max

Избавимся
от неравенств в ограничениях, введя в
ограничения неотрицательные балансовые
переменные, и перейдём к каноническому
виду:

→max

,

Составим
опорный план

Рис.
1

Теперь
выберем разрешающий столбец. В нашем
случае это столбец С, поскольку в нём
находится наибольшее положительное
значение целевой функции. После этого
выбираем разрешающий элемент( min
{b_i/a_ij}),
в нашем случае это элемент С7.

Рис.
2

Далее
составляем новую симплекс – таблицу,
в которой элементы разрешающей строки
делятся на разрешающий элемент. Элементы
разрешающей строки и столбца становятся
равны 0, кроме разрешающего элемента.
Остальные элементы определяются по
правилу прямоугольника (сумма произведений
главной и побочной диагонали делить на
разрешающий элемент).

Рис.
3

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

х₁
= 2,3; х₂
= 0; х₃
= 9,71; х₄
= 13,29; х₅
= 8,29; х₆
= 22; x₇
= 0; F_max
= 29,71

Ответ:
для достижения максимального дохода,
который составит 26 ед. необходимо
выпустить 2 единицы изделий типа А и
отказаться от выпуска изделий типа В.

Ответы
на контрольные вопросы.

1.
Как построить первоначальный опорный
план задачи линейного программирования?

Для
построения опорного плана необходимо
построить модель ЗЛП в каноническом
виде и преобразовать её в симплекс –
таблицу для дальнейших преобразований.

2.
Перечислите условия оптимальности
опорного плана.

План
считается оптимальным, если в строке
целевой функции симплекс – таблицы все
элементы равны нулю или меньше него.
Если есть положительные числа, то
необходимо перейти к новому опорному
плану, который даст более оптимальное
значение.

3.
Как определяется вектор для включения
в базис, если первоначальный план
неоптимальный?

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

4.
Когда линейная функция не ограничена
на многограннике решений?

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

5.
Как определить вектор, подлежащий
исключению из базиса?

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

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

6.
Какой метод решения систем линейных
уравнений лежит в основе симплексного
метода?

В
основе решения задач линейного
программирования лежит метод замещения
одного опорного плана другим, в котором
целевая функция достигает своего
оптимального значения. Указанное
замещение возможно, если известен
некоторый исходный опорный план.

7.
Какую простейшую геометрическую
интерпретацию можно дать симплексному
методу?

Геометрической
интерпретацией симплексного метода
является выпуклый многогранник.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #