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.  


 

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

48659. СПОСОБИ ПОЛІПШЕННЯ ТЕПЛОІЗОЛЯЦІЇ БУДІВЕЛЬ СТАРОЇ ЗАБУДОВИ 565 KB
  Метою цієї роботи є визначення порядку чергування огороджувальних шарів стіни несуча та теплоізолююча частина що забезпечить найменші темп та швидкість її охолодження з метою вибору оптимальних варіантів енергозберігаючих рішень по утепленню житлових приміщень старої забудови постійного та періодичного опалення. У роботі проведено розрахунок розподілу температури по шарах для різних конструкцій утеплених стін визначено кількість теплоти що треба витратити на кожен квадратний метр поверхні стіни аби температура у приміщенні стала...
48660. История политических и правовых учений 688.6 KB
  История политических и правовых учений – юридическая наука и учебная дисциплина исторического профиля. В то же время, как и юриспруденция в целом, она относится к числу гуманитарных (социально-гуманитарных) наук. В этом качестве она взаимодействует с другими гуманитарными науками, но прежде всего и главным образом с философией.
48662. Державні запозичення та фінансова безпека держави 268.5 KB
  Зумовили досить стрімке накопичення боргу та концентрацію платежів щодо його обслуговування у вузькому часовому інтервалі. Недаремно на суспільно психологічному й емоційному рівнях сприймання державних запозичень варіює від апокаліпсичного образу смертоносної проблеми до чудодійного засобу вирішення всіх проблем що знайшло своє відображення в науково теоретичних уявленнях про природу державного боргу. Функціонування державного кредиту можливе при таких суспільно економічних умовах: матеріально майновому розшаруванні й соціальній...
48663. Методи розрахунку новітніх макроекономічних показників 156 KB
  Із нових макроекономічних показників ми розглянемо індекс людського розвитку індекс економічної свободи та рівень глобалізації. Актуальність даної теми дослідження полягає в тому що новітні макроекономічні показники дають змогу комплексно охарактеризувати стан економіки та рівень життя тієї чи іншої країни. Розвиток всього суспільства здійснюється надзвичайно швидкими темпами тому необхідно покращувати методику розрахунку цих показників враховувати нові чинники та фактори що впливають на їх рівень. Обєктом дослідження є індекс...
48665. Найти полосу пропускания сигнала и частоту следования передаваемых импульсов, если на экране телевизора при этом наблюдается 120 чередующихся черно-белых полос (вертикальных) 107 KB
  Ответ: На рисунке 2 приведен вариант комплектации АФТ системы в которой реализуется частотный план. При этом многократное использование АФТ достигается на основе применения всех известных способов селекции радиоволн: по частоте по поляризации и по направлению распространения трехступенчатая схема разделения. Рисунок 2 структурные схемы АФТ Элементами структурной схемы на рисунке 2 являются: приемопередающая антенна А; переход П обеспечивающий согласование фидеров различной конструкции в данном случае согласование антенны с...
48666. Проектирование схем энергоснабжения промышленного предприятия 440 KB
  Расчет электрических нагрузок низшего напряжения цехов предприятия Расчетные нагрузки цехов определяются по средней мощности с учетом корректирующего коэффициента . Расчетные нагрузки на напряжение ниже 1000 В определяются следующими выражениями: 1. Силовые нагрузки на напряжение 16 кВ Рр.2 где Руст установленная мощность силового оборудования цеха кВт; Ки коэффициент использования;  корректирующий коэффициент; tg соответствует характерному для данного цеха коэффициенту мощности нагрузки.
48667. Eкспортно-імпортної політики України в умовах світової економічної кризи 817 KB
  Вона складається з ввозу імпорту і вивозу експорту товарів. До експорту відносять: товари вироблені вирощені чи добуті в країні; товари раніше ввезені зза кордону що були перероблені а також товари переробка яких здійснювалась під митним контролем. Оскільки основна частка товарів в міжнародній торгівлі перевозиться морським транспортом за основу розрахунку цін експорту та імпорту береться транспортування морем. В результаті відмінності в базі розрахунків сукупна вартість світового експорту статистично буде завжди менше вартості...