Решение задачи с помощью Excel и симплекс-методом

Размещено на http://www.allbest.ru/

Решение задачи с помощью Excel и симплекс-методом

Содержание

Задача (распределительная)

Симплекс-метод

Решение задачи с помощью Excel

Задача (распределительная)

Задача 1 (распределительная)

На предприятии 4 вида продукции могут вырабатываться на 3 отдельных взаимозаменяемых машинах.

Известны:

· Производственное задание по выпуску продукции разных видов в планируемом периоде

- ;

· Фонд эффективного рабочего времени оборудования в планируемом периоде - ;

· Нормы затрат машинного времени на изготовление единицы продукции - ;

· Прибыль в руб. от реализации единицы продукции, выработанной на том или ином оборудовании - .

Исходная информация отображается в таблице следующей формы.

Таблица 1. Исходные данные

В задаче требуется найти план распределения производственного задания по выпуску продукции между исполнителями

,

при котором задание было бы выполнено с максимальной суммарной прибылью от реализации продукции.

РЕШЕНИЕ

Разработка экономико - математической модели.

Искомые переменные - характеризуют объём выпуска й продукции м исполнителем.

Тогда матрица искомых переменных

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

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

(1)

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

Ограничения по наличию и использованию эффективного рабочего времени исполнителей примут вид системы линейных неравенств (2):

(2)

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

Следующий блок ограничений должен отражать условие обязательного выполнения общего производственного задания по выпуску продукции по видам и будет представлен системой линейных уравнений (3):

(3)

Условие не отрицательности переменных:

(4)

Приведём задачу к каноническому виду, для этого в неравенства (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 вводим формулу для целевой функции, применив команду вставки функции СУММПРОИЗВ:

Далее займёмся построением ограничений, снова ж таки при помощи функции, использованной выше. Заполним ячейки N9:N15.

А также заполняем ограничения правой части.

После этого можно приступать к поиску решения. Для решения оптимизационных задач в EXCEL используется команда ПОИСК РЕШЕНИЯ меню СЕРВИС.

Эта команда оперирует с тремя основными компонентами построенной в ЭТ оптимизируемой модели:

· Ячейкой, содержащей целевую функцию задачи.

· Изменяемыми ячейками, содержащими независимые переменные.

· Ячейками, содержащими левые части ограничений на имеющиеся ресурсы, а также простые ограничения на независимые переменные.

Рассмотрим последовательность ввода этих компонентов.

Курсор в ячейку N7 и команда СЕРВИС - Поиск решения. На экране появится диалоговое окно.

В окне заполняем поле Установить целевую ячейку, в котором должен стоять адрес $N$7. Далее устанавливаем кнопку на поиск максимального значения. В поле Изменяя ячейки введём адреса искомых переменных $B3:$M3. Затем следует ввести ограничения, путём кнопки Добавить.

Теперь, когда все ограничения для поиска оптимального решения заданы можем нажать кнопку:

.

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

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

Следовательно, решение в EXCEL такое же, как и при СИМПЛЕКС методе, а это значит, что рассматриваемая задача, решена, верно.

Размещено на Allbest.ru