Моделирование оптимизационных экономико-математических задач линейного вида в компьютерной среде EXCEL

                                  (1.21)

Таким образом, если в задаче линейного программирования определяется минимум целевой функции, то такую задачу необходимо свести к определению максимума целевой функции, а все имеющиеся ограничения вида “” и “” привести к ограничениям-равенствам [8, стр.63].

В ограничениях задачи (1.18) все переменные можно разделить на две группы. Первая группа – основные (зависимые) переменные, число которых должно быть равно числу линейно независимых уравнений m, вторая – неосновные (независимые) переменные, число которых будет равно (n-m). Такое разделение не связывается с индексами (порядковыми номерами) переменных. Будем считать, что ограничения задачи (1.18), записанной в канонической форме путем последовательных элементарных преобразований могут быть приведены к виду:

                                                                          (1.22)

где .

В системе (1.11) коэффициенты при каждом неизвестном х1, х2,…, xm образуют единичные векторы

    …,

Совокупность единичных векторов Е1, Е2,...,Еm образует базис m-мерного пространства, а переменные х1, x2,...,xm называются базисными. Переменная является базисной, если она входит только в одно из уравнений системы с коэффициентом, равным единице. Все остальные переменные являются небазисными.

Частное решение, полученное путем приравнивания небазисных (независимых) переменных нулю и нахождения значений базисных (зависимых) переменных, называется базисным решением. Следовательно, если xm+1=0, хm+2=0,..., хn=0, то x1=, . Первое решение задачи, полученное таким образом, называется исходным базисным решением.

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

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

После приведения частной задачи, имеющей ограничения “” (1.18), к канонической форме (1.19) каждое уравнение будет содержать базисную переменную, а именно хn+1. хn+2,..., xn+m. Приравняв небазисные переменные к нулю: x1=0, x2=0,…,xn=0, получим допустимое базисное решение:

После приведения частной задачи, имеющей ограничения “” (1.20), к канонической форме (1.21) переменные xn+1, xn+2,…,xn+m не могут быть приняты в качестве базисных, так как они входят в уравнения с коэффициентом (-1). Поэтому для выделения базисных переменных и нахождения допустимого базисного решения используется метод искусственного базиса, который заключается в следующем.

В каждое ограничение задачи (1.20) вводятся соответственно искусственные неотрицательные переменные хn+m+1, xn+m+2,…, xn+m+m, которые принимаются в качестве базисных. Искусственные переменные входят в целевую функцию задачи с коэффициентом М, где М – большое положительное число, во много раз больше заданных в условии задачи. В целевую функцию приписывают для задач максимизации очень большие по модулю отрицательные коэффициенты (-М), где M>ci, (i = 1, 2, ..,m).

В случае решения задач минимизаци искусственные переменные вводят в целевую функцию с большими положительными коэффициентами (+М).

Искусственные переменные вводятся только с целью получения исходного базисного плана. Пока искусственная переменная является базисной, она будет принимать положительные значения (если соответствующие ей значения bi>0) и, следовательно, уменьшать значение целевой функции по сравнению с максимальным. Поскольку эти переменные имеют большие по абсолютной величине отрицательные коэффициенты (при решении задачи максимизации), в процессе решения задачи симплекс-методом они из числа базисных переводятся в небазисные. В силу того, что значения небазисных переменных при получении базисного решения приравниваются к нулю, искусственные переменные не будут оказывать влияния на значение целевой функции. Этот же метод используется для ограничений вида “=”.

Классификация задач оптимизации:

      Задача о рациональном питании (задача о пищевом рационе);

      Задача о планировании производства;

      Задача о загрузки оборудования;

      Задача о снабжении сырьём;

      Определение оптимального ассортимента;

      Оптимальное распределение взаимозаменяемых ресурсов;

      Задача о смесях;

      Задача о раскрое материалов;

      Оптимальные балансовые модели;

      Задача о диете;

      Задача о раскрое и т.д.

Глава 2. Решение задачи линейного вида в компьютерной среде EXCEL.

ПОСТАНОВКА ЗАДАЧИ:

              Предприятие производит две модели-А и В-сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3м2 досок, для изделия В требуется 4 м2. Предприятие может получить от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 минут машинного времени, модели В – 30 минут. В неделю можно использовать 160 часов машинного времени. Сколько изделий каждой модели следует предприятию выпускать в неделю, если каждое изделие модели А приносит 2 рубля прибыли, а каждое изделие модели В – 4 рубля прибыли?

Построение математической модели

              Обозначим через x1 количество, планируемое к выпуску за неделю полок модели А, а через x2 – количество, планируемое к выпуску модели В. Задача состоит  том, чтобы найти значения x1и x2, при которых полученная прибыль будет наибольшей. Согласно условиям задачи это прибыль Z выражается формулой

Z=2* x1+4* x2

              Поскольку x1 и x2 выражают еженедельный объем выпускаемых изделий, они не могут быть отрицательными, т.е.

                                          x1≥0; x2 ≥0;

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

                                          3* x1+4*x2 ≤1700

                                          0,2*x1+0,5*x2 ≤160

              Отметим, что 12мин.=1/5ч, 30мин.=1/2ч.

Итак, задача состоит в том, чтобы найти значения x1 и x2, удовлетворяющие условиям неотрицательности и ограничением типа неравенств и максимизирующие прибыль Z. В результате получим следующую математическую модель:

Максимизировать функцию

Z=2*x1+4* x2

При ограничениях

     3*x1+4*x2 ≤1700;

2*x1+5*x2 ≤160;

x1≥0, x2 ≥0

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

1.      Заполняем таблицу:

2. Выбираем меню Сервис, пункт Поиск решения программы Excel. Появляется следующее окно:

В нем устанавливаем целевую ячейку $D$6, равную максимальному значению. Изменяемые ячейки: $B$8:$B$9. Эти значения Поиск решения будет подбирать. Всего можно указать до 200  изменяемых ячеек.

Oграничения  в окно добавляем с помощью кнопки «Добавить»:

$D$8<=$D$3

$D$9<=$D$4

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

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

Для получения решения выбираем кнопку «Выполнить» и получаем:

Используемые формулы для целевой функции: =B6*B8+C6*B9

Для ограничений:

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

АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ И СОСТАВЛЕНИЕ ОТЧЕТА

По полученному решению составляется отчет: