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.  


 

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

16074. Право пенсійного забезпечення в Україні 1.27 MB
  І.М. Сирота ПРАВО ПЕНСІЙНОГО ЗАБЕЗПЕЧЕННЯ в УКРАЇНІ Курс лекцій Київ Юрінком Інтер 1998 ББК 67.9 4УКР 305 С40 Рекомендовано вченою радою Юридичного інституту Одеського державного університету ім. 1.1. Мечникова Рецензент В.Т. УСЕНКО на
16075. Кримінально-виконавче право України 879 KB
  Кримінальновиконавче право України: Курс лекцій.Семаков Г. С Гель А. П. Київ 2000 [1] ВСТУП [2] ТЕМА 1 КРИМІНАЛЬНОВИКОНАВЧА ПОЛІТИКА І КРИМІНАЛЬНОВИКОНАВЧЕ ПРАВО. НОРМИ ТА ДЖЕРЕЛА ПРАВА. КРИМІНАЛЬНОВИКОНАВЧІ ПРАВОВІДНОСИНИ [3] ТЕМА 2 ...
16076. Мотив і мотивація злочину 928 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ ВНУТРІШНІХ СПРАВ УКРАЇНИ А. В. САВЧЕНКО МОТИВ І МОТИВАЦІЯ ЗЛОЧИНУ Київ Атіка 2002 ББК 67.94УКР308 С12 Рекомендовано до друку спеціалізованою Вченою радою Національної академії внутрішніх справ України Науковий редактор Коржанськи
16077. Держава і економіка. Адміністративно-правові аспекти взаємовідносин 1.62 MB
  МВС України Університет внутрішніх справ О.П.Рябченко Держава і економіка: адміністративноправові аспекти взаємовідносин За загальною редакцією доктора юридичних наук професора О.М. Бандурки Видавництво Університету внут...
16078. Державне управління 621 KB
  Глен Райт. Державне управління. К. 1994 Переклали з англійської Василь Івашко Олександр Коваленко Світлана Соколик київ основи Інститут державного управління та самоврядування при Кабінеті Міністрів України ББК 67.30165.050 Р18 У посібнику розг...
16079. Адміністративна деліктологія 317.5 KB
  Подлінув С.Д. Адміністративна деліктологія. Навчальнометодичний посібник призначений для самостійної роботи студентів які вивчають фундаментальну спеціальну дисципліну Адміністративна деліктологія. В посібнику розгляну...
16080. Аграрне право України О.О. Погрібного 2.85 MB
  У підручнику докладно розглянуті умови та порядок створення та функціонування субєктів аграрних правовідносин, питання права власності їх на землю, розкриті умови та порядок набуття і користування земельними ділянками, реалізації земельних прав і обмеження прав на землю. Підручник буде корисним для студентів, бакалаврів, спеціалістів, магістрів, аспірантів та викладачів правознавчих, аграрних, землевпорядних та економічних спеціальностей вищих навчальних закладів, а також широкому колу читачів, які цікавляться проблемами аграрного законодавства і права України.
16081. Порівняльне правознавство 1.71 MB
  ББК67 П41 Підручник підготовлений викладачами Національної юридичної академії України імені Ярослава Мудрого Гриф Затверджено Міністерством освіти і науки України як підручник для студентів юридичних спеціальностей вищих навчальних закладів надано 15.09.2003 рок
16082. Право інтелектуальної власності в Україні 1.26 MB
  О.А. Підопригора О.О Підопригора ПРАВО ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ УКРАЇНИ НАВЧАЛЬНИЙ ПОСІБНИК для студентів юридичних вузів і факультетів університетів Київ Юрінком Інтер 1998 Рекомендовано вченою радою юридичного факультету Київського ун