35171

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

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

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

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

Русский

2015-01-19

23.52 KB

33 чел.

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


 

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

34010. Предмет и задачи этики. Основные этические системы 44 KB
  Вся совокупность проблем в той или иной мере посвященных изучению этих вопросов была представлена особой философской теорией получившей название философия морали нравственности или этика. Термин этика происходит от древнегреческого слова ethos этос подразумевавший пространство совместного проживания людей или животных дом звериное логово птичье гнездо и т. Поэтому термин этика также введенный в употребление Аристотелем изначально приобрел двоякую направленность: 1 обозначение совокупности добродетелей правил и норм...
34011. Основные этические системы 46.5 KB
  Остановимся на нескольких наиболее значительных и как нам представляется не утративших свое значение и по настоящее время именно в силу своей вневременной универсальной значимости для нравственного сознания человека: гедонизме стоицизме этике долга и этике любви. Именно такая постановка личности по Эпикуру порождает три степени свободы каждая из которых есть в сущности ничто иное как освобождение человека от тяжелых экзистенциальных переживаний сопровождающих его на протяжении всей жизни: от страха перед Богами от страха перед...
34012. Искусство как социокультурное явление.Эстетические основания и закономерности развития ис 45.5 KB
  Искусство это одна из форм культуры и сфера художественного творчества. философия исследует искусство в общем плане и в контексте жизни человека и общества. Искусство отражает и изображает жизнь в художественных образах которые позволяют человеку непосредственно в чувственном виде переживать то что в них заключил художник.
34013. Философское понимание культуры. Культура и цивилизация 26 KB
  Культура и цивилизация. Культура все созданное человеком; совокупность созданных и создаваемых человеком ценностей; качественная характеристика уровня развития ова. Там где есть человек его деятсть отношения между людьми там имеется и культура. Культура: материальная и духовная не противопоставлять.
34014. Филсофия Древней Индии 23 KB
  э Мир вечен никем никогда не был создан остоянно развивается делится на мир приоды и мир людей. Мир природы гормоничен и спокоен; мир людей мир страданий.э Мир вечен никем никогда не создан. Сущность мира изменеие развия.
34015. Философия русской культуры 110 KB
  Сущность любой культуры раскрывается в основополагающих ценностях: добре и зле свободе справедливости любви и т. Непосредственный объект любви в нем не человечество потому что вызвать любовь может только нечто наглядное; человечество просто карта которая разыгрывается им против того что ненавидят. Не уважая же никого перестает любить а чтобы не имея любви занять себя и развлечь предается страстям и грубым сладостям и доходит совсем до скотства в пороках своих а все от беспрерывной лжи и людям и себе самому. Однако...
34016. Общество как развивающаяся система 25 KB
  В западной социологии с основным классообразующим признаком, т.е. отношение к средствам производства, не согласна теория социальной стратификации. На этой основе она предлагает свои критерии...
34017. Основные модели общественного устройства 38.5 KB
  Современная форма либерализма как она утвердилась на Западе наиболее типичными здесь являются США теоретически оформилась и начала осуществляться на практике в Новое время и эпоху Просвещения. Основными посылками либерализма являются: 1. 'Lissez fire не мешайте действовать девиз классического либерализма. Идеал минимального государства характерная черта классического либерализма.
34018. Исторические формы общности людей 38.5 KB
  Историческими формами общности людей принято считать: род племя народность нацию. Это исторически восходящие формы объединения людей. Это связано с тем что в обществе где господствует коллективная собственность на средства производства и уравнительное распределение еще не дифференцировались интересы людей.