35171

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

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

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

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

Русский

2015-01-19

23.52 KB

41 чел.

Лабораторная работа №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 с выполненной работой.


 

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

65733. ФУНКЦІЇ ОРГАНІВ ДОСУДОВОГО СЛІДСТВА В КРИМІНАЛЬНОМУ ПРОЦЕСІ УКРАЇНИ 182 KB
  У науці кримінального процесу концепція щодо визначення кримінальнопроцесуальних функцій має більш як сторічну історію. Це пояснюється насамперед тим що правильне визначення кримінально-процесуальних функцій та їх...
65734. Активізація залучення прямих іноземних інвестицій в економіку України в умовах глобальної конкуренції 265.5 KB
  В умовах глобальної конкуренції роль прямих іноземних інвестицій ПІІ полягає в залученні не лише необхідних обсягів капіталу а й сучасних технологій методів управління та висококваліфікованих менеджерів. Разом з тим глобалізація світогосподарських взаємин за участю прямих іноземних інвестицій...
65735. Удосконалення розрахунку напружено-деформованого стану мостових конструкцій з урахуванням динамічного впливу вантажних поїздів 697.5 KB
  Штучні споруди є невідємною та важливою складовою транспортної системи країни однак до цього часу в Україні відсутні рекомендації з визначення швидкісних режимів руху поїздів мостами. Більш ніж 10 залізничних мостів в Україні внаслідок наявності дефектів є барєрними обєктами що призводить...
65736. ЖАНРОВІ МОДИФІКАЦІЇ В ПОЕЗІЇ В. СКОТТА ТА ПОЕТІВ-«ЛЕЙКІСТІВ» 139.5 KB
  Скотта і поетів лейкістів яких обєднували схожі світоглядні позиції та напрямки естетичних пошуків ще недостатньо повно висвітлені в науці особливо в аспекті засвоєння народних традицій що вплинули на картину світу британського романтизму на його ранньому етапі й зумовили подальші художні відкриття.
65737. МОДЕЛЮВАННЯ І ПРОГНОЗУВАННЯ ДІЇ НЮХОВОГО НАНОБІОСЕНСОРА НА ОСНОВІ МОЛЕКУЛИ БІЛКА ТИПУ GPCR 481.5 KB
  Причинами цього є поперше те що сучасна кремнієва електроніка досягає межі мініатюризації і для виведення її на якісно новий рівень розвитку створення так званого квантового комп'ютера необхідна нова фізична елементна база з елементами розміру порядку нанометра тобто розміру молекули.
65738. Робота та розрахунок сталевих нагельних з’єднань дерев’яних конструкцій за повторних навантажень 1.33 MB
  Велике значення мають дослідження міцнісних і деформативних характеристик нагельних з'єднань дерев'яних елементів при одноразових та повторних навантаженнях оскільки при експлуатації значна кількість дерев'яних конструкцій знаходяться саме в таких умовах.
65739. ПРАВОВЕ РЕГУЛЮВАННЯ ПРОТИДІЇ ІНФОРМАЦІЙНИМ ВІЙНАМ В УКРАЇНІ 155.5 KB
  Незважаючи на надзвичайну важливість забезпечення належного функціонування всіх сфер життєдіяльності людини суспільства та держави необхідність ефективного забезпечення інформаційної безпеки держави зокрема шляхом вироблення надійного механізму протидії інформаційним війнам...
65740. СТАН АНТИОКСИДАНТНОЇ СИСТЕМИ ТА НЕСПЕЦИФІЧНА РЕЗИСТЕНТНІСТЬ У ТВАРИН ЗА ДІЇ ПРОБІОТИКІВ БПС 44 ТА БПС Л 227.5 KB
  Мета роботи: зясувати вплив пробіотичних препаратів БПС44 та БПСЛ на стан антиоксидантної системи та неспецифічну резистентність молодняку великої рогатої худоби ВРХ та свиней; встановити фактори антагоністичної дії штамів бактерій компонентів пробіотиків.
65741. ЗАБЕЗПЕЧЕННЯ ЯКОСТІ ПОСЛУГ ПЕРЕДАЧІ МУЛЬТИМЕДІА МЕРЕЖАМИ НОВОГО ПОКОЛІННЯ 1.25 MB
  Даний процес може сприяти виникненню проблем які повязані із гарантуванням рівня якості обслуговування мереж передачі мультимедійної інформації. Передплатники цих систем передачі мультимедійної інформації вимагають надання нових послуг які можуть бути доступними в будь якому місці...