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.  


 

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

693. Отставание в психическом развитии 126.5 KB
  Оособенности мышления, речевого развития, игровой и учебной деятельности. Коррекционно-развивающее обучение детей с ЗПР. Олигофрения. Причины умственной отсталости. Обучение детей с умственной отсталостью.
694. Решение задачи коммивояжера 163.5 KB
  Описание реализация метода ветвей и границ и метода Монте-Карло при помощи средств объектно-ориентированного языка Java. Задача поиска кратчайшего гамильтонова цикла в полном графе. Процесс разбиения множеств на подмножества.
695. Кавказская война 1817-1864 годов 102.5 KB
  Деятельность А.П. Ермолова на Кавказе и формирование идеологии мюридизма. Основные этапы войны, имамат: военно-теократическое государство Шамиля. Завершающий этап Кавказской войны.
696. Заселение Северного Кавказа и политика Российской колонизации 103 KB
  Заселение земель Северного Кавказа калмыками и туркменами в 16-18 веках. Состояние горских обществ накануне российской колонизации: особенности феодальных отношений. Взаимоотношения народов Северного Кавказа с Россией в 16-17 веках, первые русские поселения. Политика России на Северном Кавказе в 18-первой половине 19 веков, возведение оборонительных линий и заселение казачеством северокавказских земель. Становление российской администрации на Северном Кавказе и добровольное присоединение северокавказских народов к России.
697. Использование графики в приложениях Windows Forms 108 KB
  Разработать приложение с графическим интерфейсом пользователя, которое позволяет рисовать заданную геометрическую фигуру в клиентской области главного окна, строит и отображает график заданной функции
698. Международная экономическая интеграция 66.5 KB
  Предпосылки и цели международной интеграции. Этапы международной интеграции. Типы интеграционных объединений. Результаты интеграции. Процесс экономического взаимодействия стран, приводящий к сближению хозяйственных механизмов, принимающий форму межгосударственных соглашений.
699. Получение запросов и отчетов в базе данных MS Access 52 KB
  освоение приемов работы с готовой базой данных по созданию простых и сложных запросов и отчетов. Использование связей между таблицами для получения информации из двух и более таблиц.
700. Общая характеристика WWW 124.5 KB
  История возникновения WWW, понятие гипертекста. Интерфейс Web-приложений при работе в сети Internet. Гипертекстовая информационная система World Wide Web. Базы данных Gopher и поисковая система Veronica.
701. Моделирование прохождения сигнала через некогерентный и когерентный приемные тракты 64.5 KB
  Формирование сигнала на выходе приемника с линейным детектором и с фазовым детектором. Наблюдение интерференции сигналов от целей, разделенных интервалом меньше длительности импульса. Оценка влияния длительности зондирующего импульса на разрешение сигналов по времени.