Пример решения задачи симплексным методом в Excel. Преобразование Жордана-Гаусса и симплекс-метод в Excel

Поиск решения - это надстройка Microsoft Excel, с помощью которой можно найти оптимальное решение задачи с учетом заданных пользователем ограничений.

Поиск решения будем рассматривать в (эта надстройка претерпела некоторые изменения по сравнению с предыдущей версией в .
В этой статье рассмотрим:

• создание оптимизационной модели на листе MS EXCEL
• настройку Поиска решения;
• простой пример (линейная модель).

Установка Поиска решения

Команда Поиск решения находится в группе Анализ на вкладке Данные .

Если команда Поиск решения в группе Анализ недоступна, то необходимо включить одноименную надстройку.
Для этого:

• На вкладке Файл выберите команду Параметры , а затем - категорию Надстройки ;
• В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти;
• В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

Примечание . Окно Надстройки также доступно на вкладке Разработчик . Как включить эту вкладку .

После нажатия кнопки Поиск решения в группе Анализ, откроется его диалоговое окно.

При частом использовании Поиска решения его удобнее запускать с Панели быстрого доступа, а не из вкладки Данные. Чтобы поместить кнопку на Панель, кликните на ней правой клавишей мыши и выберите пункт Добавить на панель быстрого доступа .

О моделях

Этот раздел для тех, кто только знакомится с понятием Оптимизационная модель.

Совет . Перед использованием Поиска решения настоятельно рекомендуем изучить литературу по решению оптимизационных задач и построению моделей.

Ниже приведен небольшой ликбез по этой теме.

Надстройка Поиск решения помогает определить лучший способ сделать что-то :

• "Что-то" может включать в себя выделение денег на инвестиции, загрузку склада, доставку товара или любую другую предметную деятельность, где требуется найти оптимальное решение.
• "Лучший способ" или оптимальное решение в этом случае означает: максимизацию прибыли, минимизацию затрат, достижение наилучшего качества и пр.

Вот некоторые типичные примеры оптимизационных задач:

• Определить , при котором доход от реализации произведенной продукции максимальный;
• Определить , при которой общие затраты на перевозку были бы минимальными;
• Найти , чтобы общие затраты на производство продукции были бы минимальными;
• Определить минимальный срок исполнения всех работ проекта (критический путь).

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

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

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

Подготовка оптимизационной модели в MS EXCEL

Поиск решения оптимизирует значение целевой функции. Под целевой функцией подразумевается формула, возвращающая единственное значение в ячейку. Результат формулы должен зависеть от переменных модели (не обязательно напрямую, можно через результат вычисления других формул).
Ограничения модели могут быть наложены как на диапазон варьирования самих переменных, так и на результаты вычисления других формул модели, зависящих от этих переменных.
Все ячейки, содержащие переменные и ограничения модели должны быть расположены только на одном листе книги. Ввод параметров в диалоговом окне Поиска решения возможен только с этого листа.
Целевая функция (ячейка) также должна быть расположена на этом листе. Но, промежуточные вычисления (формулы) могут быть размещены на других листах.

Совет . Организуйте данные модели так, чтобы на одном листе MS EXCEL располагалась только одна модель. В противном случае, для выполнения расчетов придется постоянно сохранять и загружать настройки Поиска решения (см. ниже).

Приведем алгоритм работы с Поиском решения , который советуют сами разработчики (www.solver.com ):

• Определите ячейки с переменными модели (decision variables);
• Создайте формулу в ячейке, которая будет рассчитывать целевую функцию вашей модели (objective function);
• Создайте формулы в ячейках, которые будут вычислять значения, сравниваемые с ограничениями (левая сторона выражения);
• С помощью диалогового окна Поиск решения введите ссылки на ячейки содержащие переменные, на целевую функцию, на формулы для ограничений и сами значения ограничений;
• Запустите Поиск решения для нахождения оптимального решения.

Проделаем все эти шаги на простом примере.

Простой пример использования Поиска решения

Необходимо загрузить контейнер товарами, чтобы вес контейнера был максимальным. Контейнер имеет объем 32 куб.м. Товары содержатся в коробках и ящиках. Каждая коробка с товаром весит 20кг, ее объем составляет 0,15м3. Ящик - 80кг и 0,5м3 соответственно. Необходимо, чтобы общее количество тары было не меньше 110 штук.

Данные модели организуем следующим образом (см. файл примера ).

Переменные модели (количество каждого вида тары) выделены зеленым.
Целевая функция (общий вес всех коробок и ящиков) – красным.
Ограничения модели: по минимальному количеству тары (>=110) и по общему объему (<=32) – синим.
Целевая функция рассчитывается по формуле =СУММПРОИЗВ(B8:C8;B6:C6) – это общий вес всех коробок и ящиков, загруженных в контейнер.
Аналогично рассчитываем общий объем - =СУММПРОИЗВ(B7:C7;B8:C8) . Эта формула нужна, чтобы задать ограничение на общий объем коробок и ящиков (<=32).
Также для задания ограничения модели рассчитаем общее количество тары =СУММ(B8:C8) .
Теперь с помощью диалогового окна Поиск решения введем ссылки на ячейки содержащие переменные, целевую функцию, формулы для ограничений и сами значения ограничений (или ссылки на соответствующие ячейки).
Понятно, что количество коробок и ящиков должно быть целым числом – это еще одно ограничение модели.

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

Резюме

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

Поиску решения не удалось найти решения (Solver could not find a feasible solution)

Это сообщение появляется, когда Поиск решения не смог найти сочетаний значений переменных, которые одновременно удовлетворяют всем ограничениям.
Если вы используете Симплекс метод решения линейных задач , то можно быть уверенным, что решения действительно не существует.
Если вы используете метод решения нелинейных задач, который всегда начинается с начальных значений переменных, то это может также означать, что допустимое решение далеко от этих начальных значений. Если вы запустите Поиск решения с другими начальными значениями переменных, то, возможно, решение будет найдено.
Представим, что при решении задачи нелинейным методом, ячейки с переменными были оставлены не заполненными (т.е. начальные значения равны 0), и Поиск решения не нашел решения. Это не означает, что решения действительно не существует (хотя это может быть и так). Теперь, основываясь на результатах некой экспертной оценки, в ячейки с переменными введем другой набор значений, который, по Вашему мнению, близок к оптимальному (искомому). В этом случае, Поиск решения может найти решение (если оно действительно существует).

Примечание . О влиянии нелинейности модели на результаты расчетов можно прочитать в последнем разделе статьи .

В любом случае (линейном или нелинейном), Вы должны сначала проанализировать модель на непротиворечивость ограничений, то есть условий, которые не могут быть удовлетворены одновременно. Чаще всего это связано с неправильным выбором соотношения (например, <= вместо >=) или граничного значения.
Если, например, в рассмотренном выше примере, значение максимального объема установить 16 м3 вместо 32 м3, то это ограничение станет противоречить ограничению по минимальному количеству мест (110), т.к. минимальному количеству мест соответствует объем равный 16,5 м3 (110*0,15, где 0,15 – объем коробки, т.е. самой маленькой тары). Установив в качестве ограничения максимального объема 16 м3, Поиск решения не найдет решения.

При ограничении 17 м3 Поиск решения найдет решение.

Некоторые настройки Поиска решения

Метод решения
Рассмотренная выше модель является линейной, т.е. целевая функция (M – общий вес, который может быть максимален) выражена следующим уравнением M=a1*x1+a2*x2, где x1 и x2 – это переменные модели (количество коробок и ящиков), а1 и а2 – их веса. В линейной модели ограничения также должны быть линейными функциями от переменных. В нашем случае ограничение по объему V=b1*x1+b2*x2 также выражается линейной зависимостью. Очевидно, что другое ограничение - Максимальное количество тары (n) – также линейно x1+x2 Линейные задачи обычно решаются с помощью Симплекс метода. Выбрав этот метод решения в окне Поиска решения можно также проверить на линейность саму модель. В случае нелинейной модели Вы получите следующее сообщение:

В этом случае необходимо выбрать метод для решения нелинейной задачи. Примеры нелинейных зависимостей: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, где x – переменная, а V – целевая функция.

Кнопки Добавить, Изменить, Удалить
Эти кнопки позволяют добавлять, изменять и удалять ограничения модели.

Кнопка Сбросить
Чтобы удалить все настройки Поиска решения нажмите кнопку Сбросить – диалоговое окно очистится.

Эта опция удобна при использовании разных вариантов ограничений. При сохранении параметров модели (кнопка Загрузить/ Сохранить, далее нажмите кнопку Сохранить ) предлагается выбрать верхнюю ячейку диапазона (столбца), в который будут помещены: ссылка на целевую функцию, ссылки на ячейки с переменными, ограничения и параметры методов решения (доступные через кнопку Параметры ). Перед сохранением убедитесь в том, что этот диапазон не содержит данных модели.
Для загрузки сохраненных параметров нажмите сначала кнопку Загрузить/ Сохранить , затем, в появившемся диалоговом окне кнопку Загрузить , после чего задайте диапазон ячеек, содержащих сохраненные ранее настройки (нельзя указывать только одну верхнюю ячейку). Нажмите кнопку OK. Подтвердите сброс текущих значений параметров задачи и их замену на новые.

Точность
При создании модели исследователь изначально имеет некую оценку диапазонов варьирования целевой функции и переменных. Принимая во внимание вычислений в MS EXCEL, рекомендуется, чтобы эти диапазоны варьирования были значительно выше точности вычисления (она обычно устанавливается от 0,001 до 0,000001). Как правило, данные в модели нормируют так, чтобы диапазоны варьирования целевой функции и переменных были в пределах 0,1 – 100 000. Конечно, все зависит от конкретной модели, но если ваши переменные изменяются более чем на 5-6 порядков, то возможно следует «загрубить» модель, например, с помощью операции логарифмирования.

Решение ЗЛП симплексным методом с использованием таблиц EXCEL

Пусть исходная ЗЛП приведена к каноническому виду, а ее система ограничений имеет предпочтительный вид. Например, для “Задачи об использовании сырья” математическая модель соответствующего вида будет такова:

Первая симплексная таблица на рабочем листе EXCEL будет иметь вид (рис. 10):

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

Этап 1. Выбрать разрешающие столбец и строку и выделить разрешающий элемент (см. рис. 11).

Этап 2. Заменить в новой таблице столбцы “Базис” и ”С б ” согласно правилам их заполнения.

Элементы разрешающей строки делятся на разрешающий элемент и записываются в соответствующей по номеру строке новой таблицы:

, при i = r . (*)

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

, при i ≠ r (**)

где - элемент новой симплекс-таблицы, a ij , - элемент предыдущей симплекс-таблицы, a rk - разрешающий элемент, a ik - элемент разрешающего столбца, a rj - элемент разрешающей строки.

Примечание . Для использования возможности EXCEL копирования формул с модификацией адресов входящих в них ячеек целесообразно программировать формулы (*) и (**) только для ячеек столбца ”В”, поставив не изменяющимся ячейкам абсолютные адреса. Затем данные формулы копируются во все оставшиеся ячейки каждой строки новой таблицы.

Этап 4. Элементы последней строки новой таблицы заполняются или по формулам (**), или по правилу заполнения данной строки.

Результаты расчетов в таблицах EXCEL для нашего примера приводятся на рис 11, а формулы, использовавшиеся при данных расчетах – на рис. 12.

Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. - М.: Высш. шк., 1986.-319с., ил.

Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

Таха Х. Введение в исследование операций: в 2-х книгах. Кн.1. Пер. с англ. – М.: Мир, 1985.-479с., ил.

Методические указания к практическим занятиям по дисциплине «Математическое программирование» (линейное программирование) для студентов экономических специальностей / Сост. Туровцев Г.В., Нудный И.П. – Запорожье, ЗГИА, 1984.-31с.

Математическое программирование. Конспект лекций для студентов экономических специальностей дневного и заочного отделений /Глущевский В.В., Исаенко А.Н. – Запорожье: ЗГИА, 2003. – 150с.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на 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.

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

Решение задачи симплекс методом

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Урок 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

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