Нахождение целочисленного решения задач линейного программирования.

Цель работы: Применение процедуры «Поиск ответа» для нахождения целочисленного ответа задач линейного программирования.

Содержание работы:

— отыскать целочисленное ответ заданной задачи линейного программирования.

— выяснить дефицитное сырье (сырье, которое в ходе работы употребляется всецело).

— определить зависимость целочисленного ответа задачи от количества дефицитного сырья.

— определить зависимость целочисленного ответа задачи от разработок (меняя величины затрат дефицитного материала на производство единицы продукции каждого вида).

Записываем данные (лаб. раб. №1 ):

А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия

По окончании введения формул для левых частей ограничений, целевой функции и остатков сырья (лаб. раб. №1 ) будем иметь:

А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия

Приводим к процедуре «Поиск ответа».Показываем,что целевая функция находится в ячейке F11 и что ее необходимо максимизировать.Кроме этого показываем на неотрицательность и целочисленность переменных. Записываем ограничения

F3 ? E3 , F4 ? E4 , F5 ? E5 , F6 ? E6

По окончании исполнения вичислений возьмём:

А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия

Наиболее дефицитным есть сырье 4-го вида. Находим ответ целочисленной задачи для значений М4 ={35; 56; 77; 98; 119; 140; 161}.

Поле исполнения вычислений возьмём:

А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия
Так, имеем связь стоимости между сырья и продукции 4-го вида (самоё дефицитного):
Сырье Х
Цена У

Узнаем степень влияния разработок на оптимальное ответ. Для этого поменяем величины затрат дефицитного материала :

А B C D E F G
Сырье Нормы затрат на ед. продукции Количество сырья Левая часть ограничений Остаток сырья
A B C
Цена ед. продукции
x1 x2 x3 Целевая ф-ия

Сравнивая полученное ответ с ответом исходной задачи, видим, что технологии очень сильно воздействуют на оптимальное ответ

Лабораторная работа № 4.

ТРАНСПОРТНАЯ ЗАДАЧА

Цель работы: Применение процедуры «Поиск ответа» для составления оптимального замысла перевозок.

Содержание работы:

ввод данных.

— запись формул целевой функции и ограничений для стандартной транспортной задачи.

— нахождение ответа стандартной транспортной задачи, применяя процедуру «Поиск ответа».

— ответ транспортной задачи при наличии дополнительных ограничений (ограничение количества транспортируемых изделий в определенном направлении, задание количества транспортируемых изделий в заданном направлении и т. д.)

Постановка задачи: Задана матрица С цен перевозки единицы товара, вектор производства а (количество товара, создаваемого каждым производителем), вектор потребления b(количество товара, потребляемого каждым потребителем ).

С= а=(30 ; 5; 45; 70) b=(10; 35; 16; 25; 35)

Разработать замысел перевозок, дабы суммарные транспортные затраты были минимальными.

Ответ.

Суммарное количество создаваемого товара равняется 150 . Суммарное количество потребляемого товара равняется 121 . Введем фиктивного потребителя с количеством потребления 150-121=29. Цена перевозки к фиктивному потребителю заберём больше каждый стоимости, к примеру, 10. Тогда данные запишутся:

С1= а=(30 ; 5; 45; 70) b1=(10; 35; 16; 25; 35; 29)

В Excel вводим данные , выделяем место для ответов (B10:G13),полагая начальные значения 0 либо каждые другие числа. Записываем в ячейку I10формулу для количества товара, вывезенного от 1-го производителя :

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
=cумм(B10:G10)
Завезено потребителям

По окончании ввода данной формулы (ENTER) и протаскиванию по ячейкам I11:I13возьмём

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям

В B15 записываем формулу для количества товара,завезенного 1-му потребителю:

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям =сумм (B10:B13)

По окончании протаскивания и введения формулы на ячейки C15:G15возьмём:

A B C D E на данный момент на данный момент H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям

В I15записываем формулу для целевой функции

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям Цел. ф-ия =суммпроизв(B2:F5;B10:F13)

Введя формулу, возьмём

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям Цел. ф-ия

Приводим к процедуре «Поиск ответа», показываем, что целевая функция обязана достигнуть минимума, что целевая функция находится в ячейке I17и что изменять необходимо ячейки B10:G10. Потом необходимо добавить ограничения неотрицательности и целочисленности ответов. Кроме этого добавим ограничения, показывающие, что целый товар дожжен быть вывезенным от производителей и завезен потребителям (включая фиктивные):

I10=H2

I11=H3

I12=H4

I13=H5

B15=B7

C15=C7

D15=D7

E15=E7

F15=F7

G15=G7

По окончании вычислений возьмём

A B C D E F G H I
Матр. цен Произво- дители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям Цел. ф-ия

Так как 6-ой потребитель есть фиктивным, то соответствующее количество товара будет не вывезено от производителей. Так, имеем следующий замысел перевозок:

Потребит. Создаёт. Остаток

Транспортные затраты составят 226 д.е.

Предположим сейчас, что от 3-го производителя в обязательном порядке необходимо вывезти не меньше 30 единиц товара. Тогда необходимо записать формулу для подсчета количества товара,вывезенного от 3-го производителя (не учитывая фиктивного потребителя )

A B C D E F G H I
Матр. цен Производители
Потребители
Матр. перевозок Вывезено от производителей
=сумм(B12: F12)
Завезено потребителям Цел. ф-ия

По окончании введения формулы возьмём

A B C D E F G H I
Матр. цен Производители
Потребители
Матр. перевозок Вывезено от производителей
Завезено потребителям Цел. ф-ия

Приводим к процедуре «Поиск ответов» .К прошлым ограничениям необходимо добавить

H12 ? 30. По окончании исполнения ответа возьмём

A B C D E F G H I
Матр. цен Произво- дители
Потреби- тели
Матр. перевозок Вывезено от производителей
Завезено потреби- телям Цел. ф-ия

Предположим сейчас, что от 3-го производителя к 4-му потребителю возможно завести лишь 10 единиц товара. Тогда к прошлым условиям необходимо добавить условие

E12 = 10

По окончании исполнения ответа возьмём:

A B C D E F G H I
Матр. цен Произво- дители
Потреби- тели
Матр. перевозок Вывезено от производителей
Завезено потреби- телям Цел. ф-ия

Лабораторная работа № 5.

Лекция 1 Графический способ ответа задач линейного программирования


Также читать:

Понравилась статья? Поделиться с друзьями: