4769

Решение задач линейного программирования с помощью инструмента Поиск решения

Контрольная

Информатика, кибернетика и программирование

Решение задач линейного программирования с помощью инструмента Поиск решения Рассмотрим следующую задачу распределения ресурсов. Для производства двух типов продукции (x1=Прод.1, x2=Прод.2) требуется два вида ресурсов количество которых ограничено...

Русский

2012-11-25

184 KB

8 чел.

Решение задач линейного программирования с помощью инструмента «Поиск решения»

Рассмотрим следующую задачу распределения ресурсов. Для производства двух типов продукции (x1=Прод.1, x2=Прод.2) требуется два вида ресурсов количество которых ограничено (Ресурс 1≤1700, Ресурс 1≤1600), причем для продукции первого типа  необходимо 3 единицы

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

Математическая формулировка поставленной задачи имеет следующий вид:

 F=2x1+4Nx2→max   (ЦФ)  - целевая функция

     3*Nx1+4x2≤1700     (ОГ)   - ограничения

     (2+N)x1+5x2≤1600

     x1≥0, x2≥0           (УН)  - условия неотрицательности.

На рабочем листе (Рис.1.1), соответствующем рассматриваемой задаче, в ячейки В5:С5 введены коэффициенты целевой функции, а в ячейки В8:С9 – коэффициенты ограничений. Искомым значениям Прод.1, Прод.2 соответствуют изменяемые ячейки B3:C3, а целевой функции – целевая ячейка D3, в которую введена формула =СУММПРОИЗВ(B3:C3,В5:С5), позволяющая вычислять значение целевой функции при заданных значениях Прод.1, Прод.2. В ячейки B8,B9

введены формулы =СУММПРОИЗВ(B3:C3,В8:С8), =СУММПРОИЗВ(B3:C3,В9:С9), позволяющие вычислять значения левых частей ограничений (ОГ), правым частям которых соответствуют ячейки F8,F9.

 

    Рис. 1.1

Для ввода формулы, например,  в целевую ячейку D3 необходимо после установки курсора в этой  ячейке щелкнуть мышью по кнопке Мастер функций, выбрать в категориях – математические функции и функцию – СУММПРОИЗВ, в появившемся диалоговом окне (Рис.1.2) в массив 1 ввести B3:C3, а в массив 2 ввести B5:C5, после чего нажать  кнопку Готово.  Во все диалоговые окна адреса ячеек удобно вводить протаскивая мышь по ячейкам, чьи адреса следует ввести. Что бы ввести соответствующие формулы в ячейки B8,   B9 достаточно скопировать в них  целевую ячейку.

    Рис. 1.2

В диалоговом окне Поиск решения (Рис.1.3) в поле Установить целевую ячейку введен адрес целевой ячейки $D$3, выделен переключатель Максимальному значению, в окне Изменяя ячейки введены адреса изменяемых ячеек $B$3:$C$3, в окне Ограничения введены ограничения $B$3:$C$3>=0, $D$8:$D$9<=$F$8:$F$9, соответствующие (УН), (ОГ). Ввод ограничений осуществляется после нажатия кнопки Добавить, в окне  диалога Добавить ограничения (Рис.1.4).

    Рис. 1.3

    Рис. 1.4

    Рис. 1.5

После установки в диалоговом окне Параметры поиска решения (Рис.1.5) флажка Линейная модель, обеспечивающего применение симплекс метода, определение задачи с помощью инструмента Поиск решения завершено. На (Рис.1.6) показано диалоговое окно Результаты поиска решения и приведены результаты решения исходной задачи, в соответствии с которыми оптимальным значениям Прод.1=300, Прод.2 =200 соответствует максимальное значение целевой функции равное 1400.

    Рис. 1.6

2. Анализ решения задачи линейного программирования

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

Целевая ячейка (Макс)

Ячейка

Имя

Исходно

Результат

$D$3

Значения ЦФ

0

1400

Изменяемые ячейки

Ячейка

Имя

Исходно

Результат

$B$3

Значения Прод. 1

0

300

$C$3

Значения Прод. 2

0

200

Ограничения

Ячейка

Имя

Значение

Формула

Состояние

Разница

$D$8

Ресурс 1 левая часть

1700

$D$8<=$F$8

связанное

0

$D$9

Ресурс 2 левая часть

1600

$D$9<=$F$9

связанное

0

$B$3

Значения Прод. 1

300

$B$3>=0

не связан.

300

$C$3

Значения Прод. 2

200

$C$3>=0

не связан.

200

    Рис. 2.1

Отчет по результатам (Рис.2.1) состоит из трех таблиц:

- таблица Целевая ячейка содержит сведения о целевой функции до начала вычисления     - (столбец Исходно) и после вычислений (столбец Результат);

- таблица Изменяемые ячейки содержит значения искомых переменных до начала вычисления (столбец Исходно) и после вычислений (столбец Результат);

- таблица Ограничения содержит информацию о выполнении ограничений (ОГ) и (УН).

Для ограничений в столбце Формула содержатся зависимости, введенные в диалоговом окне Поиск решения; в столбце Значение содержатся величины использованного ресурса; в столбце Разница содержатся величины неиспользованного ресурс; в столбце Состояние указывается статус ограничения. Если ограничение выполняется как равенство то оно – связанное, а если как неравенство то - несвязанное.

 Изменяемые ячейки

Результ.

Редуц.

Целевой

Допустимое

Допустимое

Ячейка

Имя

значение

стоимость

Коэффициент

Увеличение

Уменьшение

$B$3

Значения Прод. 1

300

0

2

1

0,4

$C$3

Значения Прод. 2

200

0

4

1

1,333333333

Ограничения

Результ.

Теневая

Ограничение

Допустимое

Допустимое

Ячейка

Имя

значение

Цена

Правая часть

Увеличение

Уменьшение

$D$8

Ресурс 1 левая часть

1700

0,285714286

1700

700

420

$D$9

Ресурс 2 левая часть

1600

0,571428571

1600

525

466,6666667

Отчет по устойчивости состоит из двух таблиц. В таблице Изменяемые ячейки содержатся следующие значения для переменных:

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

В таблице Ограничения содержатся следующие значения для ограничений:

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

Целевое

Ячейка

имя

Значение

$D$3

Значения ЦФ

1400

Изменяемое

Нижний

Целевой

Верхний

Целевой

Ячейка

имя

Значение

предел

результат

предел

Результат

$B$3

Значения Прод. 1

300

0

800

300

1400

$C$3

Значения Прод. 2

200

0

600

200

1400

    Рис. 2.3

Отчет по пределам (Рис.2.3) содержит информацию о том, в каких пределах может изменятся выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения:

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

Например, если Прод.1= 0 (нижний предел), то F=20+4200=800, а если Прод.1=300 (верхний предел) ), то F=2300+4200=1400.

3. Параметрический анализ

Под параметрическим анализом понимается решение задачи оптимизации при различных значениях того параметра, который ограничивает улучшение целевой функции. На Рис. 3.1 приведены результаты параметрического анализа при следующих значениях первого ресурса: 1280, 1500, 1700, 2000, 2400

Рис. 3.1

Структура сценария

Текущие значения:

Рес .1=1280

Рес.1=1500

Рес .1=1700

Рес.1=2000

Рес.1=2400

Изменяемые ячейки:

$B$3

800

0

157,1428571

300

514,2857143

800

$C$3

-1,77636E-14

320

257,1428571

200

114,2857143

-1,77636E-14

Ячейки результата:

$D$3

1600

1280

1342,857143

1400

1485,714286

1600

$D$8

2400

1280

1500

1700

2000

2400

$D$9

1600

1600

1600

1600

1600

1600

Примечания: столбец ''Текущие значения'' представляет значения изменяемых ячеек в

момент создания Итогового отчета по Сценарию. Изменяемые ячейки для каждого

сценария выделены серым цветом.

Рис. 3.2

 Результаты решения задачи при каждом значении изменяемого параметра можно сохранить как отдельный сценарий. Используя следующую последовательность команд  Сервис, Сценарии, Отчет, Структура, ОК, создается итоговый сценарий (Рис.3.2).

4. Решение транспортной задачи

Рассмотрим следующую транспортную задачу. В трех пунктах отправления (ПО1, ПО2,ПО3) имеются запасы однородного груза в количествах 210, 100, 600 единиц соответственно. Этот груз требуется перевести в пять пунктов назначения (ПН1, ПН2, ПН3, ПН4, ПН5) соответственно в количествах 150, 160, 200, 100, 300 единиц. Тарифы перевозок единицы груза указаны в ячейках C2:G5 (Рис.4.1). Например, стоимость перевозки единицы груза из ПО1 в ПН1 равна 6. Требуется найти минимальный по стоимости план перевозок, обеспечивающий вывоз имеющегося груза из всех пунктов отправления и доставку необходимого груза во все пункты назначения, причем обратные перевозки исключаются.

    Рис. 4.1

    Рис. 4.2

Искомым значениям соответствуют изменяемые ячейки С9:G11, целевой функции – ячейка H12 c формулой =СУМПРОИЗВ(С3:G5,C9:G11). Условиям баланса соответствуют ячейки B9:B11, C12:G12 в которые введены следующие формулы:

B9:    =СУМM(C9:G9)  D12:  =СУМM(D9:D11)

B10:  =СУМM(C10:G10)  E12:   =СУМM(E9:E11)

B11:  =СУМM(C11:G11)  F12:   =СУМM(F9:F11)

C12:  =СУМM(C9:C11)  G12:  =СУМM(G9:G11)

После ввода соответствующих ограничений в диалоговом окне Поиск решения (Рис.4.2) и выполнения Поиска решений получается окончательное решение задачи (Рис.4.3)


 

А также другие работы, которые могут Вас заинтересовать

26126. Учет затрат на производство и реализацию продукции 46 KB
  Учет затрат на производство и реализацию продукции. Себестоимость продукции работ услуг представляют собой стоимостную оценку использованных в процессе производства природных ресурсов сырья материалов топлива энергии основных средств трудовых ресурсов а так же других затрат на ее производство и реализацию. По способу включения в себестоимость отдельных видов продукции затраты делятся на прямые и косвенные. Прямые связаны с производством отдельных видов продукции и могут быть прямо включены в себестоимость отдельного вида продукции.
26127. Учет готовой продукции, ее реализации и финансовых результатов 33 KB
  Учет готовой продукции ее реализации и финансовых результатов. Структура ответа: Понятие готовой продукции. Виды оценки готовой продукции. Документальное оформление и отражение на счетах БУ реализации готовой продукции.
26128. Управленческий учет как элемент системы БУ 33.5 KB
  Одна из важнейших задач руководителя предприятия с максимальной отдачей использовать имеющиеся в распоряжении предприятия ресурсы. Это означает что деятельность по учету не разрывно связана с управление предприятия. При таком подходе УУ организуется исходя из потребностей управления и УУ это система сбора анализа информации об издержках предприятия система бюджетирования и система оценки деятельности как всего предприятия в целом так и его отдельных структурных подразделений. Это расширенная система организации учета для целей контроля...
26129. Сравнительная характеристика Финансового и управленческого учета 24.5 KB
  Предъявляются единые требования к первичным документам которые являются источником информации для Ф и У учета.пользователи информации Внешние пользователи Внутренние пользователи 4.базисная структура Балансовое управление: активы=капиталобязательства Структура информации зависит от запросов пользователей 5. бухгалтерские проводки делаются в учете после совершения операции Кроме исторической информации включаются оценки и планы на будущее 7.
26133. Нематериальные активы как объект учета, нормативное регулирование и учет их движения 21.54 KB
  НМА регламентируются ПБУ 14 2007Учет нематериальных активов. НМА – объекты не имеющие физически осязаемой формы но используемые организацией при прве продукции или управления процессом прва в течении срока превышающего 1 год. При принятии к бухгалтерскому учету активов в качестве НМА необходимо единовременное выполнение следующих условий: 1 отсутствие материальновещественной физической структуры; 2 возможность идентификации выделения отделения от другого имущества; 3 испие в прве продукции при выполнении работ или оказании...