Лабораторная работа №10: Нахождение решения задач целочисленного программирования

Цель работы:

Научиться решать задачи целочисленного программирования.

Рекомендации по решению:

1. При решении задач линейного программирования средствами Microsoft Excel используется надстройка Поиск решения, которая позволяет найти оптимальные решения.

Задание к лабораторной работе:

Решить задачу симплекс-методом. После нахождения опорного плана, просмотреть его компоненты. Если среди компонент имеются дробные числа, то ввести дополнительное неравенство и найти решение задачи двойственным симплекс-методом. Решить графически в Microsoft Excel.

- преобразованные исходные величины.

- дробные части чисел.

F=2x₁+ 4x₂→max

при условиях:

и x₁, x₂, x_3,х₄≥0 целые

Вариант1

Вариант 2

Вариант 3

Вариант 4

при ограничениях:

х₁, x₂ – целые числа

Вариант 5

при ограничениях:

х₁, x₂– целые числа

Вариант 6

Турист готовится к длительному переходу в горах или в лесу. В рюкзаке он может нести груз, масса которого не должна превышать некоторого фиксированного значения. Для определённости предположим, что в качестве исходных видов предметов рассматриваются продукты питания: хлеб, сухари, тушёная говядина, лосось в масле, сыр, сушёные бананы, сахар рафинад (n=7), а в качестве их характеристики – масса продукта в кг (m=1). Субъективная ценность для туриста 1 экземпляра каждого из продуктов следующая: с₁=20, с₂=30, с₃=60, с₄=30, с₅=40, с₆=20, с₇=50. Масса 1 экземпляра каждого из продуктов следующая:

a₁=0,6 кг, a₂=0,5 кг, a₃=0,3 кг, a₄=0,6 кг, a₅=0,5 кг, a₆=0,1 кг, a₇=0,4 кг. Предполагается, что общая масса продуктов в рюкзаке не должна превышать b=7кг.

Вариант 7

Некоторое предприятие выпускает две марки элитных часов (n=2), которые имеют условные названия: «Банкир» и «Президент». Для изготовления часов «Банкир» требуется 50 г золота и 30 г платины, а для изготовления часов «Президент» требуется 40 г золота и 50 г платины (m=2). Предприятие продаёт часы «Банкир» по цене $ 1500 за 1 шт., а часы «Президент» – по цене $ 2100 за 1 шт. Запасы драгоценных металлов на складе предприятия ограничены следующими значениями: золота – 1,5 кг и платины – 1,8 кг. Требуется определить оптимальную партию часов «Банкир» и «Президент», которую может изготовить предприятие с целью получения максимальной прибыли.

Вариант 8