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.  


 

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

12495. Определение показателя преломления стекол 89.5 KB
  PAGE 3 Определение показателя преломления стекол: методические указания по выполнению лабораторной работы № 63 по курсу Физика для студентов инженернотехнических специальностей / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библи...
12496. Определение радиуса кривизны линзы и длины световой волны с помощью колец ньютона 327 KB
  Определение радиуса кривизны линзы и длины световой волны с помощью колец ньютона: методические указания по выполнению лабораторной работы по оптике № 66 по курсу Физика / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библиогр.: с.7. Содержат све...
12497. Лесное хозяйство 84.5 KB
  Многие важнейшие элементы лесного хозяйства, включая охрану лесов, лесоустройство, учёт и инвентаризацию лесов, лесовосстановление, защитное лесоразведение, профилактическую работу с населением и лесную науку, или уже прекратили своё существование, или неизбежно перестанут существовать в течение одного-двух лет при сохранении существующих тенденций.
12498. Изучение внутреннего фотоэффекта 43 KB
  Изучение внутреннего фотоэффекта: методические указания по выполнению лабораторной работы № 83 по курсу Физика для студентов инженернотехнических специальностей / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библиогр.: с.7. Содержат сведения...
12499. Анализ фондового рынка Российской Федерации за 2009 -2014 года 4.01 MB
  Ведущим индикатором фондового рынка России является Индекс ММВБ. Кроме основного композитного индекса ММВБ, рассчитывается Индекс РТС. Основные индексы Московской Биржи (Индекс ММВБ и Индекс РТС)
12500. Определение показателя преломления, концентрации и дисперсии растворов сахара с помощью рефрактометра Аббе 302 KB
  Определение показателя преломления концентрации и дисперсии растворов сахара с помощью рефрактометра Аббе [Текст]: методические указания по выполнению лабораторной работы по оптике № 64 для студентов инженернотехнических специальностей / ЮгоЗап. гос. унт; сост.: А.А. Ро
12501. Изучение закона МалюсаИзучение особенностей интеллектуальной деятельности пожилых людей 1.34 MB
  На основе теоретического анализа описать основные характеристики интеллектуальной деятельности пожилых людей; Описать методы изучения интеллектуальной деятельности пожилых людей; Изучить особенности интеллектуальной деятельности пожилых людей; Разработать практические рекомендации по улучшению интеллектуальной деятельности пожилых людей...
12502. БАНК ВТБ24 178.5 KB
  Всем этим требованиям в полной мере отвечает один из лидеров национального банковского сектора России - банк ВТБ24. За всю историю своего существования ВТБ сумел занять прочные позиции на российском на всех сегментах рынка банковских услуг и добиться международного признания
12503. Финансы домохозяйств: состав и структура доходов и расходов, роль сбережений 349.5 KB
  Предметом исследования курсовой работы являются финансы домохозяйств, состав и структура доходов и расходов населения и роль сбережений. Объектом исследования будет выступать вся деятельность домашних хозяйств.