42054

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

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

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

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

Русский

2013-10-27

231.5 KB

43 чел.

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


 

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

53187. Решение уравнений. Урок – игра математики в 6 классе 49.5 KB
  Многие задачи из жизни решаются на математическом языке с помощью уравнений. Поэтому очень важно, чтобы ваши знания и умения решать уравнения были прочны. Во время урока вам пригодятся находчивость, смекалка и сообразительность, потому что мы проведём наш урок в виде игры- соревнований.
53189. ГРА НА УРОЦІ АНГЛІЙСЬКОЇ МОВИ ЯК ЗАСІБ ПІДВИЩЕННЯ ПІЗНАВАЛЬНОЇ АКТИВНОСТІ ШКОЛЯРІВ 83 KB
  У школярів молодшого віку переважають ігрові інтереси, довільна поведінка, наочнообразне мислення, практичне ставлення до розвязування завдань. Зважаючи на все це, доцільно у роботі з ними на уроках іноземної мови систематично застосовувати елементи гри у поєднані з бесідою, елементами самостійної роботи.
53190. Інтерактивна ділова гра ток-шоу «Я так думаю» 37.5 KB
  Правила гри: Усі учасники мають рівні права; Кожен учасник має право висловити свою думку; Думка кожного має бути почута врахована та прийнята. Учасники ділової гри: всі педагогічні працівники. Загальний сценарій: учасники об’єднуються в чотири групи – Батьки Діти Педагоги та Експерти; ведучий роз’яснює мету гри загальний сценарій та правила гри; групова гра: розігрування ситуації відповідно до обраних ролей; міжгрупова дискусія керована ведучим; підсумок гри за допомогою експертів.
53191. Гра як засіб всебічного розвитку учнів 139.5 KB
  За її допомогою діти пізнають світ. В грі діти перевіряють свою силу і спритність у них виникають бажання фантазувати відкривати таємниці і прагнути чогось прекрасного. Захопившись грою діти не помічають що навчаються до активної діяльності залучаються навіть найпасивніші учні. Захопившись грою діти не помічають що навчаються.
53192. Гра не тільки розважає, а й здоров’я додає! 94.5 KB
  Від ставлення людини до особистого здоров’я залежить його збереження та зміцнення. Одне з найважливіших завдань сучасної школи – навчити дітей та їх батьків берегти і зміцнювати своє здоров’я. Вчитель повинен сформувати в учнів свідоме ставлення до свого здоров’я надати життєві навички здорового способу життя та безпечної для здоров’я поведінки.
53193. Літературна гра на тему: Шевченко - художник 32.5 KB
  Шевченка створена на тему його однойменної поеми Катерина Картина проектується на екран. На екран проектується репродукція картини Т.На екран проектується обкладинка першого видання Кобзаря. ВовчкуАвтопортрет зі свічкою Репродукція проектується на екран.
53194. Гра «Поле чудес» План-конспект узагальнюючого уроку на тему «Світлотінь» для 6 класу 308 KB
  Завдання можуть бути суто теоретичними а можуть чергуватися практичні та теоретичні питання. Нас чекають цікаві завдання відкриття призи. Познайомимося з умовами гри: Розподіл барабана на сектори: Кожен сектор має своє позначення: Намальований пензлик це означає що гравуць отримує практичне завдання виконати в кольорі аквареллю на папері пейзаж натюрморт розмивання набризк і т. Намальований олівець практичне завдання виконати простим олівцем малюнок геометричне тіло з світлотінню глечик вазу і т.
53195. Фізико-математична гра «Щасливий випадок» 241.5 KB
  Правила: В цьому раунді кожній команді буде задано деяку кількість простих запитань з математики, інформатики, фізики та астрономії за обмежений час (1 хв.) Кожна правильна відповідь оцінюється 1 балом. Приймаються лише перші відповіді команди. Якщо ніхто з учасників команди не знає відповіді на запитання, можна говорити «Пас» або «Далі». Очки при цьому не нараховуються.