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.  


 

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

9754. Осложнения аварий при бурении скважин 108.72 KB
  Осложнения аварий при бурении скважин. Под осложнением понимается, прерывание. Нормального процесса бурения при выполнении проектных условий, принятие неотложных мер. Поглощение промывочной жидкости. Нарушение устойчивости стенки скважин...
9755. Принципы разработки приложений в среде визуального программирования 3.35 MB
  Принципы разработки приложений в среде визуального программирования Разработка компьютерной программы - длительный и трудоемкий процесс. Чтобы окончательный вариант программы работал правильно и содержал как можно меньше ошибок, программисты придерж...
9756. Изучение принципов функционирования отладчика среды 6.08 MB
  Цель лекции: Изучить состав и структуру приложения. Изучить принципы функционирования отладчика среды. Учебные вопросы: 1. Состав и структура приложения. Файл проекта. Модуль формы. Разделы модуля формы. Связи между файлами проекта. 2. О...
9757. Биполярные транзисторы. Вольт-амперные характеристики транзистора 354.93 KB
  Биполярные транзисторы Биполярный транзистор представляет собой систему двух взаимодействующих p-n-переходов. В биполярном транзисторе физические процессы определяются носителями зарядов обоих знаков - основными и неосновными.
9758. Характеристики биполярного транзистора 50.62 KB
  Отчёт по лабораторной работе №2 Характеристики биполярного транзистора 1. Цель работы Экспериментальное определение вольт-амперных характеристик биполярного транзистора в схеме с общим эмиттером при нормальной и повышенной температурах, опре...
9759. Факторы среды жилого помещения, влияющие на здоровье человека 42.54 KB
  Оглавление. Введение. Основная часть. Глава. Факторы среды жилого помещения, влияющие на здоровье человека. Глава. Практическая часть...
9760. Характеристики и параметры полевых транзисторов с управляющим p-n-переходом 27.05 KB
  Дисциплина - Электроника Отчёт по лабораторной работе №3 Характеристики и параметры полевых транзисторов с управляющим p-n-переходом. Цель работы Исследование статических характеристик полевого транзистора с управляющим p-n-переходом и опред...
9761. Характеристики и параметры полевых транзисторов с управляющим P-N-переходом 96.37 KB
  Характеристики и параметры полевых транзисторов с управляющим P-N-переходом 1. Цель работы Исследование статических характеристик полевого транзистора с управляющим p-n-переходом и определение его основных параметров. 2. Схема проведения измер...
9762. Реконструкция жилого дома с перепрофилированием первого этажа в нежилой 44.76 KB
  Оглавление Объемно-планировочное решение. Конструктивное решение. Реконструкция Технический паспорт дома...