35171

Линейное программирование, задачи линейного программирования

Лабораторная работа

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

Программное обеспечение Microsoft Excel Методические указания Рассмотрим решение задач линейного программирования средствами Excel на примере следующей задачи. Нормы затрат каждого сырья на единицу продукции заданы таблицей...

Русский

2015-01-19

23.52 KB

36 чел.

Лабораторная работа №9

Линейное программирование

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

F(X) = C1x1 + C2x2 + ... + Cnxn

при ограничениях:

a11x1 + a12x2 + … + a1nxn ≤ b1;

a21x1 + a22x2 + … + a2nxn ≤ b2;

am1x1 + am2x2 + … + amnxn ≤ bm;

xj ≥ 0, j =1,2,..., l; l ≤ n.

Решение X = (x1, x2 ,..., xn) данной системы ограничений, при котором функция F(X) принимает максимальное (минимальное) значение, называется оптимальным планом задачи линейного программирования. Все остальные решения системы ограничений называются допустимыми планами. Функция F(X) называется целевой функцией. Ограничения называются основными.

Программное обеспечение

Microsoft Excel

Методические указания

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

Предприятие выпускает 2 вида продукции. Цена единицы 1 вида продукции - 25 000, 2 вида продукции – 50 000. Для изготовления продукции используются три вида сырья, запасы которого 37, 57,6 и 7 условных единиц. Нормы затрат каждого сырья на единицу продукции заданы таблицей:

Ресурс 1

Ресурс 2

Ресурс 3

Продукт 1

1,2

2,3

0,1

Продукт 2

1,9

1,8

0,7

Требуется определить плановое количество выпускаемой продукции таким образом, чтобы стоимость произведенной продукции была максимальной

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

Целевой функцией, отражающей максимизацию прибыли предприятия, в данном случае будет:

F = 25000x1 + 50000x2max.

Где неизвестные x1 и  x2 – количество единиц первого и второго вида продукции.

Основными ограничениями, исходя из условий задачи, будут следующие неравенства:

1,2x1 + 1,9x2 ≤ 37;

2,3x1 + 1,8x2 ≤ 57,6;

0,1x1 + 0,7x2 ≤ 7.

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

x1 ≥ 0; x2 ≥ 0;

x1, x2 – целые числа.

Завершив составление неравенств, можно приступить к решению задачи в Excel. Для этого, следует воспользоваться подпунктом Поиск решения... пункта меню Сервис.

Предварительно введём в ячейку А3 формулу целевой функцию в следующем виде: «=25000*A1+50000*A2».

Значения в ячейках А1 и А2 отведём под значения переменных x1 и x2 соответственно. Числовые значения переменных x1 и x2 в эти ячейки будут введены автоматически в процессе решения задачи.

В ячейки В1, В2 и В3 введём математические формулы ограничений:

в В1: «=1,2*А1+1,9*А2»;

в В2: «=2,3*А1+1,8*А2»;

в В3: «=0,1*А1+0,7*А2».

Затем введём в ячейки С1, С2 и С3 значения 37, 57,6 и 7 соответственно, ограничивающие численные значения переменных задачи.

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

Теперь воспользуемся подпунктом меню Excel Поиск решения...

В появившемся окне, в поле «Установить целевую ячейку» указываем ячейку А3. Решение ищем для максимального значения, что указывается переключателем поля «Равной», установленным на записи со словами «максимальному значению».

В поле «Изменяя ячейки» указываем диапазон изменения ячеек от А1 до А2, а именно $A$1:$A$2.

Для приведения в рабочее состояние математической программы поиска оптимального решения заданной задачи необходимо установить ограничения, учитываемые при её решении. Для этого нажимаем на кнопку «Добавить», расположенную справа от поля «Ограничения». В появившемся окне, для добавления первого ограничения, необходимо, в поле «Ссылка на ячейку» указать ячейку В1, затем в списке, расположенном посередине, выбрать знак «<=» и в поле «Ограничение» указать ячейку С1. После этого следует нажать на кнопку «Добавить». Аналогично добавляются остальные ограничения задачи, при этом в качестве ограничения, могут выступать адреса ячеек, численные константы или типы переменных.

После указания всех ограничений, следует нажать на кнопку «Выполнить» и на кнопку «ОК» в появившемся окне «Результаты поиска решения». В результате, в ячейках, отведённых для записи решения задачи, появятся числа.

В ячейке А3 находим значение целевой функции F, соответствующее найденному решению. В ячейках А1 и А2 указаны соответствующие значения переменных x1, x2.

Для решаемой нами задачи оптимальное решение имеет следующий вид:

F = 825000, x1 = 19, x2 = 7.

Задание на лабораторную работу

1. Дана следующая задача:

На складах имеется груз, количество которого определяется в следующей таблице:

Склад 1

Склад 2

Склад 3

Запас груза

19

76

33

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

Пункт 1

Пункт 2

Потребность в грузе

47

81

Стоимость перевозок определяется таблицей:

Пункт 1

Пункт 2

Склад 1

19

8

Склад 2

13

15

Склад 3

11

10

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

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

Отчет

Файл .xls с выполненной работой.


 

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

84065. Органы и функции органов пищеварительной системы 42.71 KB
  Они располагаются на границах пищевода и желудка кардиалъный сфинктер желудка и двенадцатиперстной кишки пилорический сфинктер а также в месте перехода подвздошной кишки в слепую и вокруг анального отверстия. Внутренний листок брюшины покрывает большую часть органов пищеварительного канала: желудок и весь кишечник кроме прямой кишки. Эти влияния осуществляются биологически активными веществами образующимися в слизистой оболочке двенадцатиперстной кишки и желудка а также различными пищевыми веществами всосавшимися в кровь из...
84066. Регуляция процесса пищеварения 31.89 KB
  В системе пищеварения происходят три взаимосвязанных процесса секреция моторная функция и всасывания. Конечным результатом деятельности системы пищеварения являются поступления во внутреннюю среду организма питательных веществ воды витаминов электролитов и микроэлементов. Натощак в состоянии покоя органов пищеварения возникает периодическая их деятельность что проявляется сокращением желудка и кишок выделением небольшого количества желудочного сока желчи сока поджелудочной железы и кишечника.
84067. Особенности пищеварительной системы детей раннего возраста 24.75 KB
  Для детей первых месяцев жизни имеют определяющее значение питательные вещества которые поступают с молоком матери и перевариваются за счет веществ содержащихся в самом женском молоке. Всасывание пищевых ингредиентов у детей раннего возраста имеет свои особенности. Расщепление молочного сахара у детей происходит в кайме кишечного эпителия.
84068. Питание детей первого года жизни, грудное молоко как источник питательных и защитных веществ для ребенка 29.6 KB
  Идеальным питанием для ребенка в первые месяцы жизни является грудное молоко поскольку в нем содержатся все необходимые для развития и роста ребенка пищевые вещества. Именно грудное молоко – источник всех необходимых для роста и развития ребенка пищевых веществ: белков жиров углеводов витаминов и минералов. Кроме того грудное молоко является источником таких важных компонентов как ферменты иммуноглобулины гормоны что так же жизненно необходимо для гармоничного развития ребенка для его защиты от различных инфекционных заболеваний.
84069. Сердечнососудистая (циркуляторная) система (типы сосудов, круги кровообращения) 29.83 KB
  Кровь в них движется от сердца. Через тонкие стенки капилляров происходит обмен между кровью и тканями транскапиллярный обмен. Кровь в них движется от органов и тканей к сердцу. В капиллярах кровь отдает кислород и питательные вещества а от них получает продукты метаболизма в том числе и углекислый газ.
84070. Сердце, особенности строения сердца, обеспечивающие выполнение его функций 29.57 KB
  Левая и правая части сердца разделены сплошной перегородкой. В левой части сердца клапан двустворчатый в правой трехстворчатый. Клапаны сердца обеспечивают движение крови только в одном направлении: из предсердий в желудочки и из желудочков в артерии.
84071. Регуляция работы сердца 28.54 KB
  Работа сердца регулируется нервной системой в зависимости от воздействия внутренней и внешней среды: концентрации ионов калия и кальция гормона щитовидной железы состояния покоя или физической работы эмоционального напряжения. Нервная и гуморальная регуляция деятельности сердца согласует его работу с потребностями организма в каждый данный момент независимо от нашей воли. Гуморальная регуляция деятельности сердца осуществляется с помощью имеющихся в крупных сосудах специальных хеморецепторов которые возбуждаются под влиянием изменений...
84072. Особенности сердечнососудистой системы у детей младшего возраста 31.68 KB
  Сердце и сосуды у детей значительно отличаются от сердечнососудистой системы взрослых. Рост сердца у детей идет во всех направлениях но неравномерно т. У новорожденных и детей первых 05 2 лет жизни сердце расположено поперечно и более высоко.
84073. Репродуктивная система человека 30.41 KB
  Репродуктивная система комплекс органов и систем которые обеспечивают процесс оплодотворения способствуют воспроизводству человека. Мужская репродуктивная система система органов расположенных снаружи тела около таза которые принимают участие в процессе репродукции. Репродуктивная система женщины состоит из органов расположенных преимущественно внутри тела в тазовой области.