183660 (596698), страница 5

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

Текст из файла (страница 5)

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

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

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

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

Оценка линейная - выберите этот переключатель для работы с линейной моделью.

Оценка квадратичная - выберите этот переключатель для работы с нелинейной моделью.

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

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

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

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

В результате исследования основных алгоритмов решения задач ЛП, было принято решение поставленную задачу планирования производства решать симплекс методом. Это обусловлено тем, что симплекс метод является эффективным алгоритмом и наиболее универсальным методом, которым можно решить любую задачу линейного программирования. В качестве вспомогательного средства, для составления конкретной задачи планирования производства (подбора таких значений, чтобы задача имела решение) было использовано средство «Поиск решения» в MS Excel.

3. Задача планирования производства

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

3.1 Постановка задачи планирования производства в общем случае

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij – количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij 0 (i=1,…,m; j=1,…,n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj – планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

(1)

Кроме того, имеем следующее ограничение: xj 0; j=1,…,n. (2)

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

Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

3.2 Математическое описание поставленной задачи планирования симплекс методом

Пусть некоторое предприятие производит 5 видов продукции A, B, C, D и E, затрачивая при этом 5 типов ресурсов. На производство продукции типа A требуется следующее количество имеющихся на предприятии ресурсов (дается количество каждого ресурса, необходимого для производства единицы продукции типа A): 1 – количество ресурса 1, 4 – количество ресурса 2, 2 – количество ресурса 3, 1 – количество ресурса 4, 3 – количество ресурса 5. На производство единицы продукции типа B требуется (в условных единицах): 2 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа C требуется (в условных единицах): 4 – количество ресурса 1, 1 – количество ресурса 2, 3 – количество ресурса 3, 1 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа D требуется (в условных единицах): 3 – количество ресурса 1, 2 – количество ресурса 2, 4 – количество ресурса 3, 2 – количество ресурса 4, 1 – количество ресурса 5. На производство единицы продукции типа E требуется (в условных единицах): 1 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 4 – количество ресурса 5.

Допустим, что запас ресурса 1 на предприятии составляет 600 условных единиц, запас ресурса 2 – 590 условных единиц, запас ресурса 3 – 750 условных единиц, запас ресурса 4 – 670 условных единиц и запас ресурса 5 – 495 условных единиц.

Цена единицы продукции типа A равна 60 рублям, цена единицы продукции типа B равна 50 рублям, цена единицы продукции типа C равна 37 рублям, цена единицы продукции типа D равна 45 рублям, а единица продукции типа E – 56 рублям.

Нужно спланировать такой набор производимой продукции x=(x1, x2, x3, x4, x5), при котором суммарные затраты каждого вида ресурса не превосходят его запаса, т.е.

x1+4x2+2x3+1x4+3x5 600;

2x1+2x2+x3+4x4+2x5 590;

4x1+x2+3x3+x4+2x5 750;

3x1+2x2+4x3+2x4+x5 670;

x1+2x2+x3+4x4+4x5 495;

и при этом должны выполняться следующие ограничения: x1, x2, x3, x4, x5 0. Спланированный набор производимой продукции x=(x1, x2, x3, x4, x5) должен обеспечить максимум стоимости данного набора

{60x1+50x2+37x3+45x4+56x5} max.

Таким образом, мы получим однокритериальную задачу, которая является задачей линейного программирования (ЗЛП). Она сводится к поиску экстремума линейной функции (данная функция называется либо критерием, либо целевой функцией)

f(x)=60x1+50x2+37x3+45x4+56x5

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

x1+4x2+2x3+1x4+3x5 600;

2x1+2x2+x3+4x4+2x5 590;

4x1+x2+3x3+x4+2x5 750;

3x1+2x2+4x3+2x4+x5 670;

x1+2x2+x3+4x4+4x5 495;

x1, x2, x3, x4, x5 0.

3.3 Решение поставленной задачи планирования производства

Описание метода решения задачи.

Процедура решения ЗЛП начинается с приведения ее к канонической форме, то есть к стандартной форме задания, ориентированной на разработанный именно для этой формы метод решения. Задача линейного программирования в канонической форме имеет смысл при условии n>m. В этом случае полностью описывается область допустимых решений (ОДР) ЗЛП, геометрически являющуюся выпуклым многогранником в евклидовом пространстве Rn[1]. Выпуклая фигура, как известно, характеризуется тем свойством, что, если две точки X1 и X2 принадлежат этой фигуре, то и весь отрезок X1X2 принадлежит ей. Кроме того, доказано, что оптимальное решение ЗЛП всегда лежит на границе ОДР. Поэтому справедлив вывод о том, что, по крайней мере, одна из угловых (опорных) точек выпуклого многогранника ОДР является точкой оптимума. Для того, чтобы определить координаты опорной точки, все множество переменных X={xj}, j= необходимо разделить на два подмножества

:

подмножество базисных переменных , при этом число m базисных переменных равно числу уравнений (ограничивается) при условии, что уравнения являются линейно-независимыми; подмножество остальных n-m свободных (внебазисных) переменных {xj}, j Б[1].

Количество возможных вариантов разделения переменных на базисные и свободные (число базисов) равно .

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

В основе симплекс-метода лежит подход, включающий:

выбор опорной точки, принадлежащей ОДР (выбор начального допустимого базиса);

проверку опорной точки на оптимальность;

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

Приведение исходной задачи к каноническому виду.

Имеем исходную ЗЛП:

{60x1+50x2+37x3+45x4+56x5} max.

x1+4x2+2x3+x4+3x5 600;

2x1+2x2+x3+4x4+2x5 590;

4x1+x2+3x3+x4+2x5 750;(4)

3x1+2x2+4x3+2x4+x5 670;

x1+2x2+x3+4x4+4x5 495;

x1, x2, x3, x4, x5 0.

Приведем ЗЛП к канонической форме. Приведение системы ограничений, заданных в форме неравенств, к канонической форме равенств осуществляется посредством соответствующего увеличения размерности вектора X=(x1, x2, x3, x4, x5) с учетом обязательной неотрицательности всех его составляющих.

Таким образом, ЗЛП в канонической форме имеет вид:

max {60x1+50x2+37x3+45x4+56x5};

(5)

Поиск допустимого базиса.

Заполнение симплекс-таблицы.

ЗЛП в канонической форме можно записать в матричном виде:

(6)

b=(600, 590, 750, 670, 495)T,

X=(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)T,

C=(60,50,37,45,56,0,0,0,0,0),

A= .

Поиск допустимого базиса начинается с анализа столбцов матрицы A=(A1, A2,…, A10), используемой в записи ограничения (6) канонической формы ЗЛП. В качестве базисных следует выбирать такие 5 переменных, которым соответствует набор столбцов, позволяющих составить единичную матрицу P=(Aj1, Aj2, Aj3, Aj4, Aj5).

Если ОДР исходной ЗЛП задана в форме неравенств типа (как в нашем случае), то начальный базис может быть сформирован из дополнительных переменных x6, x7, x8, x9, x10, вводимых в систему ограничений с целью приведения ее к канонической форме равенств. В этом случае матрица P будет единичной.

Характеристики

Список файлов ВКР