42054

Информационные технологии при решении целочисленной задачи линейного программирования

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

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

Информационные технологии при решении целочисленной задачи линейного программирования Цель работы изучить возможности табличного процессора MS Excel для решения задач целочисленного линейного программирования ЦЛП. Задача целочисленного линейного программирования Задачи оптимизации в результате решения которых искомые значения переменных должны быть целыми числами называются задачами моделями целочисленного дискретного программирования: Если то задачу называют полностью целочисленной; если же то имеем частично целочисленную...

Русский

2013-10-27

231.5 KB

44 чел.

Лабораторная работа 1_2. Информационные технологии при решении целочисленной задачи линейного программирования

Цель работы - изучить возможности табличного процессора MS Excel для решения задач целочисленного линейного программирования (ЦЛП).

Краткие теоретические сведения.

Задача целочисленного линейного программирования

Задачи оптимизации, в результате решения которых искомые значения переменных должны быть целыми числами, называются задачами (моделями) целочисленного (дискретного) программирования:

Если , то задачу называют полностью целочисленной; если же , то имеем частично целочисленную задачу.

Наиболее часто используемым методом решения задач дискретного программирования является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Excel. Целочисленная оптимизация проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных  (при этом в режиме Параметры устанавливается тип задачи – линейная или нелинейная). Для этого

  •  В окне «Поиск решения» нажать кнопку «Добавить» и в появившемся окне «Добавление ограничений» ввести ограничения следующим образом:

- в поле «ссылка на ячейку» ввести адреса ячеек переменных задачи;

- в поле ввода знака ограничения установить «целое»

- подтвердить ввод ограничения нажатием кнопки «OK» (см. Рис.2.1).

  Рис.2.1. Ввод условия целочисленности всех (части) переменных

В случае целочисленной оптимизации возможен вызов только одного Отчета по результатам.

Достаточно часто при моделировании используется особый случай дискретности  задачи - булевость переменных, т.е. переменные могут принимать значения 0 или 1. Характерный пример этого случая – задача о назначениях.

Пример задачи целочисленного линейного программирования

Задача. Организация арендует баржу грузоподъемностью 200 т. На ней предполагается перевозить груз 4 типов. Вес и стоимость единицы груза равны соответственно

20, 15, 20, 14  - вес единицы груза, и

100, 80, 40, 30 – стоимость единицы груза.

Необходимо погрузить на баржу груз максимальной стоимости.

Решение. Пусть  - число предметов j-ого типа, которое следует погрузить на баржу. Тогда математическая модель задачи имеет вид:

      - целые неотрицательные.

 Текстовая форма-таблица для ввода условий задачи и исходных данных имеет вид:

 Диалоговое окно Поиск решения имеет вид:

Диалоговое окно Параметры поиска решения имеет вид:

Вид окна с окончательным решением имеет вид:

Контрольные упражнения. Варианты.

 I. Составить математические модели следующих задач при условии, что искомые неизвестные величины должны быть целочисленными.

1.В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3 м2 площади. На приобретение оборудования предприятие может израсходовать 10 тыс. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 1 тыс. руб. и требует для установки 2 м2 площади; II вида – 3 тыс. руб. и 1 м2 площади.  Приобретение одного комплекта оборудования  I вида позволит увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида – на 4 ед. Требуется определить, какое количество дополнительного оборудования позволит максимально увеличить выпуск продукции.

2. Три типа самолетов следует распределить между 4 авиалиниями. В таблице 1 задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы. Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Таблица 1

Тип самолета

Число самолетов

Месячный объем перевозок одним самолетом по авиалиниям

Эксплуатационные расходы на один самолет по авиалиниям

I

II

III

IV

I

II

III

IV

1

50

15

10

20

50

15

20

25

40

2

20

30

25

10

17

70

28

15

45

3

30

25

50

30

45

40

70

40

65

II. Найти решение задач целочисленного линейного программирования. Варианты.

1. 

2.

3.

4.

5.

6.

7.

8.

9.

10.

 

11.

12.

13.

14.  


 

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

10368. Регионализация образования. Состояние и развитие Тульской областной системы образования. Региональная программа развития образования 38 KB
  Регионализация образования. Состояние и развитие Тульской областной системы образования. Региональная программа развития образования. Основные направления экспериментальной инновационной работы в учреждениях образования Тульской области. Регионализация системы ...
10369. Шпаргалка по педагогике (для педагогов) 1.87 MB
  Шпаргалка по педагогике для педагогов 1. Понятие педагогики и этапы ее развития Слово педагогика греческого происхождения. В дословном переводе означает детовождение. В современном понимании педагогика представляет собой совокупность знаний и умений по...
10370. АВГУСТИН Блаженный (Augustinus Sanctus) Аврелий 45.72 KB
  АВГУСТИН Блаженный Augustinus Sanctus Аврелий 13.11.354 Тагаст Сев. Африка Нумидия 28.8.430 Гишюн Сев. Африка христ. теолог представитель зап. патристики. Прошёл через увлечение манихейством и скептицизмом в 387 принял крещение. С 395 епископ Гиппона. Онтология А. и его уч...
10371. АДЛЕР (Adler) Альфред 33.73 KB
  АДЛЕР Adler Альфред 7.2.1870 Вела 28.5.1937 Абердин Шотландия австр. врач и психолог создатель индивидуальной психологии. Примыкал сначала к сторонникам 3. Фрейда затем основал собств. школу получившую наибольшее влияние в 20х гг. с созданием Междунар. ассоциации инд
10372. ФОМА АКВЙНСКИЙ, (Thomas Aquinas) 47.64 KB
  ФОМА АКВЙНСКИЙ Thomas Aquinas 1225 или 122i замок Роккасекка близ Акуино Юж. Италия 7. 3. 1274 монастырь Фоссануова Юж. Италия ср.век философ и теолог систематизатор ортодоксальной схоластики основатель томизма; монахдоминиканец с 1244. В 1567 признан пятым учителем ...
10373. Предмет и задачи политологии. Методы изучения политических явлений 55.5 KB
  Предмет и задачи политологии. Методы изучения политических явлений. Политология это наука о политической власти и управлении о закономерностях развития политических отношений и процессов функционирования политических систем и институтов политического поведения и...
10374. Основные понятия категории науки о политике 61.5 KB
  Всякий раз, когда мы ставим перед собой задачу вычленить какую-либо научную дисциплину из всей совокупности научных дисциплин, мы сталкиваемся с вопросом о ее понятийно-категоричном аппарате. Политика зачастую представляет собой не только четко очерченную, раз и навсегда...
10375. Место политологии среди других обществоведческих дисциплин 29 KB
  Место политологии среди других обществоведческих дисциплин. Политики представляя собой очевидную сторону общественной жизни детерминируется множеством явных и скрытых от глаз мене ощутимых факторов и процессов в совокупности составляющих ее социологические основ...
10376. История развития политической мысли. Основные тенденц 35.5 KB
  История развития политической мысли. Основные тенденции. Чрезвычайно огромный объём материалов по истории развития политической мысли включающий в себя исторические правовые политические географические философские и другие источники не позволяют авторам подробн