42054

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

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

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

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

Русский

2013-10-27

231.5 KB

45 чел.

Лабораторная работа 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.  


 

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

23862. Сказание о Дракуле воеводе 16.23 KB
  который за свою жестокость имел прозвище ЦепешСажатель на кол и Дракула Дракон. Был на Мунгьянской земле область Румынии восточная часть Валахиивоевода христианин греческой веры имя его повалашски Дракулаа понашему Дьявол. Дракула спросил их почему так поступили такое бесчестье ему нанесли. Дракула воздал послу тому пышные почести показал ему своё богатство сказав что не только готов платить дань царюно со всем воинством готов пойти к нему на службу.
23863. Слово о походе Игоревом, Игоря, сына Святославова, внука Ольгова 17.03 KB
  В самом начале Игорева похода случилось затмение солнца но князь пренебрег этим дурным знамением: все превозмогла жажда искусить Дона Великого.И начали князья про малое говорить: Это великое и сами на себя крамолу ковать. Великая печаль настала по всей русской земле: Игорькнязь погубил то чего добился отец его Святослав Ольгович пленивший половецкого хана Кобяка. А киевский князь Святослав видел смутный сон: одевали его черным покрывалом на кровати тисовой черпали синее вино с горем смешанноесыпали пустыми колчанами крупный...
23864. Специфика древнерусской литературы (ДРЛ) и этапы развития. 11-17 века 34.5 KB
  Время перехода от средневекового типа литературы к новому. Характеризуется появлением новых жанров и нового понимания задач литературы. Условия возникновения письменной литературы: письменность крещение Руси.
23865. Хождение за три моря 16.74 KB
  Купцов предупреждают что караван подстерегают татары.Хасанбек дает подарки осведомителям чтобы они провели их безопасным путем. В Дербенте Афанасий просит помощи у Василия Панина который благополучно дошел до Каспия и Хасанбека чтоб заступились за людейзахваченных в плен и вернули товары. Считалось то что пришло с моря собственность владельца побережья.
23866. Основные особенности древне-русской литры 42 KB
  Литературный этикет слагается:из представлений о том как должен был совершаться тот или иной ход событийН: князь дб торжественен его конь не мб хромым он не может болетьиз представлений о том как дБ вести себя действующее лицо в соотв со своим положениемиз представлений о том какими словами должно описываться событие.Летопись дает историю госва содержит точные документальные сведения о князьях создает легитимность правомочность власти подтверждает власть.Легенда о призвании варягов: 3 брата старший Рюрик = все русские...
23867. История возникновения, создания Повести временных лет 24.5 KB
  История возникновения создания Повести временных лет Повесть временных лет составлена ок 1113 года монахом КиевоПечерского монастыря Нестором. В дальнейшем повесть временных лет включалась летописцами как начальная часть во вновь составлявшиеся летописные своды.
23868. «Поучение» Владимира Мономаха 35 KB
  Владимир Мономах Великий Князь Киевский был сыном Всеволода Ярославича и византийской царевны.Основные черты Поучения:1 Требование соблюдения норм христианской морали быть кротким слушать старейших и покоряться им не обижать сирот2 Основная мысль Поучении князь должен беспрекословно подчиняться старейшему жить в мире с другими князьями не притеснять младших князей и бояр. Князь так же должен избегать ненужного кровопролития быть радушным хозяином не предаваться лени не увлекаться властьюНо Мономах не ограничивается...
23869. Слово о законе и благодати митрополита Иллариона 31.5 KB
  Автор Слова Иларион первый митрополит из русских поставленный на киевскую митрополию из священников в 1051 г.Тема Слова тема равноправности народов резко противостоящая средневековым теориям богоизбранничества лишь одного народа теориям вселенской империи или вселенской церкви.Трехчастная композиция Слова подчеркнутая в названии позволяет органически развить основную тему Слова прославление Русской земли ее кагана Владимира и князя Ярослава.Основной пафос Слова в систематизации в приведении в иерархическую цепь фактов вселенской...
23870. Особенности передачи сигналов по линиям связи 48 KB
  Сеть - это совокупность каких-либо линий, расположенных по определенной системе (Толковый словарь русского языка. Под редакцией проф. Д.Н. Ушакова). Применительно к радиотехнической специальности в качестве такой совокупности будем рассматривать линии связи.