Анализ решения задачи планирования сборки изделий ПКФ «Альтаир» на основе теории двойственности

Следует отметить, что равенство (1.16) справедливо только в том случае, когда плановое задание Tk не нарушает номенклатуру остальных выпускаемых изделий, то есть, кроме “принудительно производимого” k-го изделия, ассортимент остальных выпускаемых “выгодных” изделий не изменится, а изменится только их количество. Определить предельную величину Tk, при которой равенство (1.16) справедливо, можно экспериментально.

     Анализ устойчивости оптимального решения. Основные исходные данные рассматриваемой задачи — это запасы ресурсов (bi, где i = 1, ..., m) и величина прибыли на одну единицу выпускаемой продукции (Cj, где j = 1, ..., n). Исследовать устойчивость — значит определить пределы изменения исходных данных, при которых не изменяется решение или же его структура. Отчет Excel по устойчивости дает допустимое увеличение и допустимое уменьшение по целевому коэффициенту Cj, при которых решение задачи остается прежним. Кроме того, в отчете по устойчивости приведены пределы увеличения и уменьшения правых частей ограничений bi, при которых прежней остается структура решения. Под неизменностью структуры решения понимается следующее: те ресурсы, которые были дефицитными в исходном решении, остаются дефицитными и в новом оптимальном решении, хотя само решение (количество выпускаемых изделий) и значение целевой функции могут изменяться.

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

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

Производственно-коммерческая фирма «Альтаир» осуществляет сборку трех видов изделий, располагая при этом комплектующими 4 типов А, Б, В и Г, соответственно в количествах 18, 16, 8 и 6 тыс. шт. Нормы затрат каждого вида комплектующих на 1 ед. изделия первого вида составляет соответственно 1, 2, 1, 0 тыс. шт.; второго вида – 2, 1, 1, 1 и третьего вида – 1, 1, 0, 1 тыс. шт. Прибыль от реализации 1 ед. изделия первого вида равна 3 тыс. у.е., второго – 4 тыс. у.е., третьего – 2 тыс. у.е.

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

В курсовой работе требуется:

1) Построить математическую модель задачи определения оптимального плана выпуска продукции, привести ее к канонической форме.

2) Построить математическую модель двойственной задачи и привести ее ограничения к виду равенства.

3) Решить исходную задачу с помощью надстройки MS Excel “Поиск решения” и получить отчеты по устойчивости и по результатам.

4) На основе анализа этих отчетов выписать оптимальные значения основных и дополнительных переменных исходной и двойственной задач и ответить на вопросы:

1.        Какие виды изделий и в каком количестве необходимо собирать фирме? Какой величины прибыль будет иметь ПКФ «Альтаир» при таком плане производства?

2.        Определите дефицитность комплектующих изделий.

3.        Какой из вариантов окажет большее влияние на изменение размера максимальной прибыли: а) закупить дополнительно 6 тыс.шт. комплектующих типа А; б) закупить дополнительно 3 тыс. шт. комплектующих типа Б; в) закупить дополнительно 2 тыс. ед. комплектующих типа В; или г) закупить дополнительно 2 тыс. ед. комплектующих типа Г?

4.        Фирме предлагают начать сборку нового (четвертого) вида изделия, нормы затрат на 1 ед. которого равны соответственно 1, 2, 2, 0 тыс. шт. комплектующих типа А, Б, В и Г, а прибыль составляет 15 тыс. у.е. за единицу. Целесообразно ли введение в план производства фирмы этого изделия?

5.        Цены на изделия фирмы могут колебаться в течение отчетного периода в связи с изменением спроса на рынке. Как повлияет на прибыль снижение цены на изделие первого вида на 0,5 тыс. у.е?

3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

1)                 Составим математическую модель задачи. Количество изделий I вида обозначим х1, II вид — х2, III вид – х3. Прибыль от реализации изделия  I вида составляет 3x1 усл. ед., товара II вида  — 4x2 усл. ед., III вида – 2х3 общая прибыль — соответственно:

                                                F=3000х1+4000х2+2000х3                                               (3.1)

Поскольку фирме «Альтаир» нужно получить наибольшую прибыль, то ставится задача максимизации целевой функции:

                               F=3000х1+4000х2+2000х3max                            (3.2)

Ресурс комплектующего А ограничен 18 тыс. шт., при этом его расходуется на реализацию товара I вида - 1x1 тыс. шт., товара II вида - 2x2, товара III вида - 1x2 тыс. шт. Поскольку количество израсходованного ресурса не должно превышать его запаса на предприятии, можно записать следующее ограничение:         

                                          x1+2x2+x3<=18                                              (3.3)

Аналогично записываются ограничения для других ресурсов:

                                           2x1+x2+x3<=16

                                          x1+x2<=8

                                          x2+x3<=6                                                         (3.4)

Так как количество изделий не может быть величиной отрицательной, то добавим еще ограничения x1  0 , x2  0 и x3  0. Таким образом, математическая модель задачи выглядит следующим образом (3.5):

                           F= 3000x1+4000x2+2000x3          max

x1+2x2+x3<=18

2x1+x2+x3<=16

x1+x2<=8

x2+x3<=6

                                 x1, x2, x3>=0                                                           (3.5)

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

2)            Приведем исходную задачу к каноническому виду. Введем три дополнительные балансовые переменные. Обозначим их у1, у2, у3, знаки неравенства меняем на знак равенства. В результате получим представление исходной задачи в канонической форме (3.6):

                            F=3000x1+4000x2+2000x3                  max

                                          x1+2x2+x3+y1=18

                                          2x1+x2+x3+y2=16

                                           x1+x2+y3=8

                                           x2+x3+y4=6

                                           x1, x2, x3>=0; y1, y2, y3>=0                                       (3.6)

где   y1- остаток комплектующего А;

        y2- остаток комплектующего Б;

                       y3- остаток комплектующего В;

                       y4- остаток комплектующего Г.

3) Построим математическую модель двойственной задачи (3.7):

                                   F=18z1+16z2+8z3+6z              min

z1+2z2+z3>=3000

2z1+z2+z3+z4>=4000

z1+z2+z4>=2000

z1, z2, z3, z4>=0                                                          (3.7)

где: z1- цена единицы комплектующего А;

      z2- цена единицы комплектующего Б;

       z3- цена единицы комплектующего В;

                 z4- цена единицы комплектующего Г.

Двойственные переменные zi — это оценки ресурсов задачи (теневые цены).

4) В двойственной задаче приведем ограничения к виду равенства (3.8), вычитая из левых частей ограничений дополнительные переменные (vj):

F=18z1+16z2+8z3+6z4                             min

                                              z1+2z2+z3-v1=3000

                                              2z1+z2+z3+z4-v2=4000

                                              z1+z2+z4-v3=2000

                                             z1, z2, z3>=0; v1, v2, v3>=0                                    (3.8)

где

      v1- потери при производстве I вида изделия;

      v2- потери при производстве II вида изделия;

                v3- потери при производстве III вида изделия.

4. РЕШЕНИЕ ЗАДАЧ В MS ЕХСEL

Заполним ячейки Excel соответствующими значениями (рис. 4.1).

Рисунок 4.1- Экран Excel для решения задачи линейного программирования

Ячейки А4:С4 отведены под значения переменных х1, х2 и х3. Этим ячейкам присваиваются начальные значения (0; 0; 0). После решения задачи Excel запишет в эти ячейки найденные оптимальные значения переменных х1, х2 и х3. Поэтому эти ячейки называются изменяемыми.

Далее нужно подготовить данные для задания ограничений задачи. В ячейки диапазона A7:С10 внесем коэффициенты при неизвестных в ограничениях. Вычислим значение левой части первого ограничения при начальных значениях переменных. Для этого введем в ячейку D7 формулу

=СУММПРОИЗВ($A$4:$С$4;A7:С7).

Ячейки D8:D10 заполняются формулами аналогично. Формулу ячейки D7 можно скопировать с помощью автозаполнения. Таким образом, ячейки D7:D10 содержат значения  использованных ресурсов (левые части ограничений). В ячейки E7:E10 внесем количество ресурса, имеющегося в наличии (правые части ограничений).

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

=СУММПРОИЗВ(A4:C4;A12:C12).

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

Экран Excel в режиме представления формул показан на (рис. 4.2).

Рисунок 4.2 - Экран Excel в режиме представления формул

=СУММПРОИЗВ($A$4:$C$4;A7:C7)

Чтобы начать процесс поиска решения, выполним команду Сервис / Поиск решения. На экране появится окно Поиск решения.

Установим курсор в поле Установить целевую ячейку и укажем ячейку модели, значение которой должно быть изменено (максимизировано, минимизировано или приравнено к какому-либо определенному указанному значению). В нашей модели целевой будет ячейка, содержащая формулу расчета прибыли А14 (рис. 4.3).

Рисунок 4.3 - Окно Поиск решения

Укажем  Параметры в окне диалога Поиск решения. На экране появится окно Параметры поиска решения (рис. 4.4).

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

Рисунок 4.4 – Параметры поиска решения

Затем активизируем процесс поиска и после его окончания в окне Результаты поиска решения выделим все три типа отчетов, используя клавишу Ctrl на клавиатуре (рис. 4.5).

Рисунок 4.5- Результаты решения

Нажатие кнопки OK приведет к созданию новых листов рабочей книги: “Отчет по результатам”, “Отчет по устойчивости” и “Отчет по пределам”. Результаты решения на исходном рабочем листе представлены в приложениях 1, 2, 3.

     Итак, нами получено следующее решение задачи: х1 = 5, х2 =3; х3 =3; Fmax = 33000. Таким образом, следует производить I вид изделия в количестве 5 тыс. ед., II и III вида – 3 тыс.ед. . При этом  прибыль будет наибольшей и составит 33000 условных единиц (усл. ед). Левые части ограничений представляют собой количество ресурсов, которые будут израсходованы при данном плане реализации товаров, а правые части — количество имеющихся в наличии ресурсов. Поэтому можно сделать вывод о том, какие ресурсы будут израсходованы полностью (левая часть равна правой), а каких ресурсов имеется остаток.

5        анализ решениЯ ЗАДАЧИ

Анализ отчетов и окна с результатами решения дает возможность ответить на поставленные вопросы следующим образом:

1.                  x1* =5; x2* = 3; x3* = 3. Эти значения появились в ячейках A4:С4 после окончания поиска. Также их можно увидеть во 2-м блоке отчета по результатам. Таким образом, наиболее выгодно производить продукцию I вида в количестве 5 тыс. ед. При таком плане производства будет получена максимальная прибыль F* = 33000.