42054

Информационные технологии при решении целочисленной задачи линейного программирования

Лабораторная работа

Информатика, кибернетика и программирование

Информационные технологии при решении целочисленной задачи линейного программирования Цель работы изучить возможности табличного процессора MS Excel для решения задач целочисленного линейного программирования ЦЛП. Задача целочисленного линейного программирования Задачи оптимизации в результате решения которых искомые значения переменных должны быть целыми числами называются задачами моделями целочисленного дискретного программирования: Если то задачу называют полностью целочисленной; если же то имеем частично целочисленную...

Русский

2013-10-27

231.5 KB

47 чел.

Лабораторная работа 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.  


 

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

69621. Управление временем выполнения проекта 374 KB
  Процедура сокращения времени. Косвенные издержки проекта. Прямые издержки проекта. Сокращение времени выполнения проекта. Построение графика стоимости времени выполнения проекта. Определение операций для сокращения времени их выполнения. Сценарии управления отклонениями.
69622. Формування матриці альтернатив, використання похідних критеріїв вибору 143 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Завдання Сформувати матрицю рішень відповідно до поставленої задачі. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають...
69624. Вирішення ЗПР за схемою «дерева рішень» 136.5 KB
  Мета: навчитись складати дерево цілей визначати найбільшу ефективність правильно вибирати рішення відносно дерева цілей. При виконанні індивідуального завдання необхідно: скласти дерево яке охоплює усі можливі варіанти подій; визначити найбільш ефективну послідовність дій...
69625. Визначення вартості достовірної інформації, графік корисності 102 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають 70 коп., а продають за 1,3 грн.
69626. Організаційна структура підприємства «Foot-service» 84 KB
  Foot-Service - динамічно розвивається компанія на взуттєвому ринку України, заснована в 2010 році. Основними напрямками компанії є виробництво та оптові продажі взуття. Мета компанії це: виведення на ринок сучасної, комфортної та якісної продукції.
69627. Теорія прийняття рішень в задачах управління та контролю 32 KB
  Торгівельна фірма що продає взуття оптовим покупцям на вітчизняному ринку повинна вирішити яку кількість пар потрібно виготовити щоб задовольнити попит покупців і отримати максимальний прибуток. Закупівельна ціна однієї пари взуття становить 95 якщо партія менша 1000 штук та 90 якщо...
69628. Формування матриці альтернатив, використання класичних критеріїв вибору 48.91 KB
  Мета: набути навиків у проведенні аналізів варіантів рішень та формуванні матриці альтернатив. Завдання Сформувати матрицю рішень відповідно до поставленої задачі. Задача №1 Завод випускає тонізуючий напій у 40-літрових бочках. Витрати на виробництво одного літра напою складають...
69629. МАІ – метод аналізу ієрархій. Метод Сааті 111 KB
  Побудувати дерево ієрархії відповідно до своєї теми, на якому вказати мету, критерії та альтернативи. Визначити експертів, які будуть оцінювати альтернативи за даними критеріями за 9 – ти бальною шкалою. Визначити пріоритети критеріїв, в які входять : компоненти власного вектору...