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.  


 

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

54136. Решение логических, занимательных задач 43 KB
  Совершенствовать вычислительные навыки учащихся; способствовать развитию внимания, мышления, памяти, смекалки, познавательной и творческой активности учащихся; воспитывать трудолюбие, ответственность, интерес к изучению математики.
54137. Розв'язування вправ на всі дії з десятковими дробами. Урок-подорож сторінками Червоної книги України 36 KB
  Розповідь вчителя про Міжнародну Червону книгу та Червону книгу України слайд 12 ІІ. На мультимедійну дошку проектуються завдання: Сполучити між собою звичайні дроби та рівні їм десяткові слайд 3: 125 02 0013 05 002 2. Виконати запропоновані дії слайд 4 Кожна дія супроводжується формулюванням відповідного правила. Розгадати кросворд і у виділеному стовпці прочитати назву рослини занесеної до Червоної книги слайд 5 1.
54139. Разработка диверсификационной стратегии компании ООО «Гем» на рынках лабораторных расходных материалов 1.85 MB
  Подавляющее большинство компаний, вне зависимости от выбранной стратегии и масштаба деятельности рано или поздно ставит перед собой задачу роста. Эта задача может быть связана, как со стремлением бизнеса постоянно повышать свою капитализацию или увеличивать денежный поток, с целью генерирования прибыли, так и с возможным желанием владельцев удовлетворять свои амбиции
54140. З досвіду організації самостійної роботи студентів 85.5 KB
  Самостійна робота студентів є важливим фактором підвищення ефективності пізнавального процесу під час підготовки майбутніх фахівців. Це пов`язано з тим що тільки в процесі самостійної роботи студент одержує міцні знання розвиває вміння творчого мислення та використання знань у практичній діяльності. Форми самостійної роботи студентів та проблеми її організації дуже різноманітні. Основні напрями рішення цієї проблеми:...
54141. Означення квадратного рівняння. Неповні квадратні рівняння, їх розвязування 35.5 KB
  Мета: освітня: удосконалити знання учнів про означення квадратного рівняння; удосконалити вміння розвязувати неповні квадратні рівняння; розвиваюча: розвивати вміння вільно висловлюватися з теми відпрацьовувати вміння говорити коротко але по суті й переконливо; виховна: виховувати активність увагу...
54142. Загальна схема дослідження функції та побудова її графіка 624 KB
  Узагальнити та систематизувати знання студентів з теми Дослідження функції і побудова її графіка за допомогою похідної. Знайдемо стаціонарні точки функції. За допомогою другої похідної знаходимо напрямки опуклості і точки перегину графіка функції: критична точка другого роду.
54143. Додавання і віднімання десяткових дробів 44.5 KB
  Перевіримо чи всі документи готові для експедиції перевірка готовності робочих місць наявність домашнього завдання. Підготовка до експедиції. При виконанні завдань експедиції необхідно вміння перевіряти себе. До експедиції готові то ж у путь ІІІ.
54144. Степень с отрицательным целым показателем 295.5 KB
  Но дай срок обдумать ответ. Повелитель был ответ приказание твое исполняется. Повелитель ответили ему математики твои трудятся без устали и надеются еще до рассвета закончить подсчет. Ради этого я и осмелился явиться перед тобой в столь ранний' час ответил старик.