35171

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

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

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

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

Русский

2015-01-19

23.52 KB

37 чел.

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


 

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

52499. Як без зусилля запамятати неправильні дієслова 32 KB
  Кошка мышке telltoldtold: Дам тебе свой бутерброд. Мама Ване telltoldtold Ужинать не позовет. Наводжу приклади учнівських віршиків: Мама Коле telltoldtold: От конфет болит животâ€.
52500. Ефективність навчання 116.5 KB
  Працюючи в школі я впевнилась що особистісно–розвивальна спрямованість освіти реалізація якої є головним завданням сучасної школи неможлива без диференційованого навчання. Головне завдання вчителів початкової ланки – не забути жодної дитини дати можливість розкрити все краще закладене природою сім’єю школою.Сухомлинський: До кожного учня треба підійти побачити його труднощі кожному дати тільки для нього призначене завдання. Враховуючи те що рівень готовності учнів до навчальної діяльності різний необхідно...
52502. Доказывание в арбитражном процессе 341.04 KB
  Институт судебных доказательств относится к числу важнейших в тех отраслях российского права, которые регламентируют порядки отправления правосудия по гражданским, арбитражным, уголовным делам. Данному институту в целом и его отдельным аспектам посвящено неисчислимое количество монографий, статей, комментариев, диссертаций. Это вполне объяснимо, поскольку правильное использование доказательств в судебной практике гарантирует установление объективной истины:
52503. Диференціація – умова успішного навчання 95.5 KB
  Виконувати диференційовані завдання систематично майже на кожному уроці уникаючи стандарту. Добирати завдання з поступовим ускладненням для сильніших і зменшувати міру допомоги для слабших учнів. Диференціацію бажано застосовувати під час фронтальної роботи коли учні розв’язують загальні навчальні завдання. Добирати варіативні завдання що полегшують роботу вчителя і учнів в перевірці цих завдань.
52504. Практический материал для развития речевого дыхания при открытой ринолалии 75 KB
  Речевое дыхание характеризуется коротким вдохом и удлиненным выдохом. При проведении работы по нормолизации дыхания необходимо соблюдать ряд правил: заниматься только в проветренном помещении до еды; строго дозировать количество и темп упражнений при недомогании лучше отложить занятия не делать слишком большой вдох; следить чтобы ребенок не напрягал плечи шею; ребенок должен ощущать движения диафрагмы межреберные мышцы мышцы нижней части живота; движения необходимо производить плавно под счет тихо. Сделать полный...
52505. Значение дыхания. Строение и функции органов дыхания. Голосовой аппарат 378 KB
  Строение и функции органов дыхания. Разработка содержит: конспект урока с поэтапным описанием методов и форм работы учителя и учащихся продолжительностью этапов урока в виде таблицы и ожидаемыми результатами презентации: Строение органов дыхания Эрудицион созданы в PowerPoint видеофайл Строение органов дыхания формат МР4 аудиозапись отрывков из оперы Джузеппе Верди. Тема: Значение дыхания.
52506. Болезни органов дыхания. Профилактика. Вредное влияние курения, загрязнения окружающей среды 37.5 KB
  Взрослым и детям для предупреждения этой болезни делают прививки. Возбудитель попадает в организм воздушнокапельным путем может длительное время находиться в организме человека н вызывая болезни. Ее положительная реакция говорит о присутствии возбудители этой болезни в организме.
52507. Дихальні здоров’єзберігаючі технології на уроках читання 48 KB
  Технологія Стоніжка. Технологія Свічка. Технологія Проколотий м’яч. Технологія Передай звуками для очищення легенів.